Ця стаття не містить . (3 березня 2021) |
Рішення задачі з кінця — алгоритм рішення, коли проводиться зворотний розрахунок для обчислення будь-яких невідомих даних на основі вже відомого кінцевого результату. «Невідомими даними» може бути набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі (тобто алгоритм). Підхід «з кінця» носить універсальний характер. Крім математики, такий підхід використовується при рішенні лінгвістичних та інших головоломок, шахових етюдів тощо.
Простий приклад
Треба знайти слово з 6 літер:
- на ньому можна спати,
- його можна готувати,
- його можна слухати.
Якщо прибрати першу літеру — вийде слово: це те, що кожен хоче, щоб він був у нього побільше.
Якщо прибрати другу — буде те, що багато хто мріє знайти.
третю — буде те, чого хочуть всі сім'ї.
четверту — буде місце, куди може потрапити душа після смерті.
Якщо починати з пошуку слова на 6 літер, буде дуже багато варіантів, які всі потрібно перевіряти послідовним відніманням літер.
Почнемо «з кінця» — місце попадання душі, за канонами релігії. Тут або вже рай, або ад. За кількістю букв підходить ад (дві літери).
Друге з кінця слово можна визначити навіть простим перебором приголосних. Але ближче до істини слово лад (воно з 3-х літер).
Далі намагаємося додати ще одну літеру. Підходить слово клад (4 літери).
Потім вже легко знайти ще одну літеру і слово. Це — оклад (5 літер).
Ну, і нарешті, знаходимо очевидне вихідне слово — доклад (6 літер).
Головоломки з монетами
Тип задач, в яких потрібно встановити той чи інший факт (виділити фальшиву монету серед справжніх, впорядкувати набір вантажів по зростанню ваги і т. ін.) за допомогою зважування на терезах.
Завдання відшукання однієї фальшивої монети, вага якої може бути більша або менша
Добре відома задача, в якій за три зважування потрібно знайти серед 12 монет фальшиву і визначити її відносну вагу.
Якщо перше зважування не викликає сумнівів: зазвичай це розбиття 12 монет на 3 купки і порівняння на терезах двох з них, — то вибірка другого зважування дуже напружує мізки. Це якщо перебирати всі варіанти для другого зважування.
Але якщо підійти «з кінця», то стають очевидними два варіанти, які після останнього третього зважування дозволять дати відповідь:
- або відома фальшива і порівняння її з напевно не фальшивою визначить її відносну вагу
- або відома відносна вага вибірки з трьох (двох) монет і порівнянням двох з них виначимо фальшиву. Хай, наприклад, вибірка легша за решту. Якщо останнє зважування покаже рівновагу двох (у вибірці з 3-х), то фальшива — третя, яка не приймала участі у зважуванні. Ну а якщо якась з двох виявилася легшою, то саме вона і є фальшивою.
Знаючи ці варіанти, мозок вже не напружується, залишаючи 3 монети на останнє зважування.
Розглянемо типовий випадок після першого зважування: 1, 2, 3, 4 > 5, 6, 7, 8
Відкладемо вбік 3 монети. Наприклад, 6, 7, 8.
Пррівняємо 1, 2, 5 і 3, 4, 9 (тобто не фальшива).
- Варіант А: 125 = 349. Останнє зважування — визначення легшої з відкладених 6, 7, 8.
- Варіант Б: 125 > 349. Останнє зважування — визначення важчої у вибірці 1 і 2.
- Варіант В: 125 < 349. Останнє зважування — визначення важчої у вибірці 3 і 4 (якщо рівновага, то 5 легша за решту).(рос.)
Підхід «з кінця» у фізиці
Підхід «з кінця», аналіз розмірності — метод, який використовується фізиками для побудови обґрунтованих гіпотез про взаємозв'язок різних розмірних параметрів складної фізичної системи. Іноді аналіз розмірності можна використовувати для отримання формул (з точністю до безрозмірнісної константи). Суть методу полягає в тому, що з параметрів, що характеризують систему, складається вираз, що має потрібну розмірність.
При аналізі розмірностей формул розмірність лівої частини рівняння повинна дорівнювати розмірності правої частини рівняння. Відсутність такої рівності свідчить про невірність формули.
Простий приклад
В Міжнародній системі одиниць (SI) сила має розмірність: Н (ньютон) = кг · м / с2 (LMT−2).
Знаючи, що м/с2 — це прискорення a, легко відтворити формулу сили F:
F=m·a
Пошук виграшної стратегії для ігор
Аналіз «з кінця» використовують при пошуку виграшних і програшних ситуацій для аналізу ігор. Виграшність доводиться «з кінця», з використанням ідей динамічного програмування: спочатку доводиться, що перебуваючи в одному з «передостанніх положень» можна потрапити в «останнє» (виграшне), потім - що з деякої безлічі «передперед...останніх» можна потрапити тільки в «передостаннє» і так далі, поки не доведемо, що якесь «перед ... передостаннє» положення і є початковим.
Примітки
- . Архів оригіналу за 29 січня 2020. Процитовано 27 лютого 2021.
Джерела
- Ф. Ф. Нагибин, Е. С. Канин. Решение задач с конца // Математическая шкатулка. — Просвещение, 1976.(рос.)
Див. також
Посилання
- Задачі, що розв'язуються зкінця[недоступне посилання]
- Метод решения задач с конца(рос.)
- Мат слоном і конем(рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno 3 bereznya 2021 Rishennya zadachi z kincya algoritm rishennya koli provoditsya zvorotnij rozrahunok dlya obchislennya bud yakih nevidomih danih na osnovi vzhe vidomogo kincevogo rezultatu Nevidomimi danimi mozhe buti nabir instrukcij yaki opisuyut poryadok dij vikonavcya shob dosyagti rezultatu rozv yazannya zadachi tobto algoritm Pidhid z kincya nosit universalnij harakter Krim matematiki takij pidhid vikoristovuyetsya pri rishenni lingvistichnih ta inshih golovolomok shahovih etyudiv tosho Prostij prikladTreba znajti slovo z 6 liter na nomu mozhna spati jogo mozhna gotuvati jogo mozhna sluhati Yaksho pribrati pershu literu vijde slovo ce te sho kozhen hoche shob vin buv u nogo pobilshe Yaksho pribrati drugu bude te sho bagato hto mriye znajti tretyu bude te chogo hochut vsi sim yi chetvertu bude misce kudi mozhe potrapiti dusha pislya smerti Yaksho pochinati z poshuku slova na 6 liter bude duzhe bagato variantiv yaki vsi potribno pereviryati poslidovnim vidnimannyam liter Pochnemo z kincya misce popadannya dushi za kanonami religiyi Tut abo vzhe raj abo ad Za kilkistyu bukv pidhodit ad dvi literi Druge z kincya slovo mozhna viznachiti navit prostim pereborom prigolosnih Ale blizhche do istini slovo lad vono z 3 h liter Dali namagayemosya dodati she odnu literu Pidhodit slovo klad 4 literi Potim vzhe legko znajti she odnu literu i slovo Ce oklad 5 liter Nu i nareshti znahodimo ochevidne vihidne slovo doklad 6 liter Golovolomki z monetamiTip zadach v yakih potribno vstanoviti toj chi inshij fakt vidiliti falshivu monetu sered spravzhnih vporyadkuvati nabir vantazhiv po zrostannyu vagi i t in za dopomogoyu zvazhuvannya na terezah Zavdannya vidshukannya odniyeyi falshivoyi moneti vaga yakoyi mozhe buti bilsha abo mensha Dobre vidoma zadacha v yakij za tri zvazhuvannya potribno znajti sered 12 monet falshivu i viznachiti yiyi vidnosnu vagu Yaksho pershe zvazhuvannya ne viklikaye sumniviv zazvichaj ce rozbittya 12 monet na 3 kupki i porivnyannya na terezah dvoh z nih to vibirka drugogo zvazhuvannya duzhe napruzhuye mizki Ce yaksho perebirati vsi varianti dlya drugogo zvazhuvannya Ale yaksho pidijti z kincya to stayut ochevidnimi dva varianti yaki pislya ostannogo tretogo zvazhuvannya dozvolyat dati vidpovid abo vidoma falshiva i porivnyannya yiyi z napevno ne falshivoyu viznachit yiyi vidnosnu vagu abo vidoma vidnosna vaga vibirki z troh dvoh monet i porivnyannyam dvoh z nih vinachimo falshivu Haj napriklad vibirka legsha za reshtu Yaksho ostannye zvazhuvannya pokazhe rivnovagu dvoh u vibirci z 3 h to falshiva tretya yaka ne prijmala uchasti u zvazhuvanni Nu a yaksho yakas z dvoh viyavilasya legshoyu to same vona i ye falshivoyu Znayuchi ci varianti mozok vzhe ne napruzhuyetsya zalishayuchi 3 moneti na ostannye zvazhuvannya Rozglyanemo tipovij vipadok pislya pershogo zvazhuvannya 1 2 3 4 gt 5 6 7 8 Vidklademo vbik 3 moneti Napriklad 6 7 8 Prrivnyayemo 1 2 5 i 3 4 9 tobto ne falshiva Variant A 125 349 Ostannye zvazhuvannya viznachennya legshoyi z vidkladenih 6 7 8 Variant B 125 gt 349 Ostannye zvazhuvannya viznachennya vazhchoyi u vibirci 1 i 2 Variant V 125 lt 349 Ostannye zvazhuvannya viznachennya vazhchoyi u vibirci 3 i 4 yaksho rivnovaga to 5 legsha za reshtu ros Pidhid z kincya u fiziciPidhid z kincya analiz rozmirnosti metod yakij vikoristovuyetsya fizikami dlya pobudovi obgruntovanih gipotez pro vzayemozv yazok riznih rozmirnih parametriv skladnoyi fizichnoyi sistemi Inodi analiz rozmirnosti mozhna vikoristovuvati dlya otrimannya formul z tochnistyu do bezrozmirnisnoyi konstanti Sut metodu polyagaye v tomu sho z parametriv sho harakterizuyut sistemu skladayetsya viraz sho maye potribnu rozmirnist Pri analizi rozmirnostej formul rozmirnist livoyi chastini rivnyannya povinna dorivnyuvati rozmirnosti pravoyi chastini rivnyannya Vidsutnist takoyi rivnosti svidchit pro nevirnist formuli Prostij priklad V Mizhnarodnij sistemi odinic SI sila maye rozmirnist N nyuton kg m s2 LMT 2 Znayuchi sho m s2 ce priskorennya a legko vidtvoriti formulu sili F F m aPoshuk vigrashnoyi strategiyi dlya igorAnaliz z kincya vikoristovuyut pri poshuku vigrashnih i prograshnih situacij dlya analizu igor Vigrashnist dovoditsya z kincya z vikoristannyam idej dinamichnogo programuvannya spochatku dovoditsya sho perebuvayuchi v odnomu z peredostannih polozhen mozhna potrapiti v ostannye vigrashne potim sho z deyakoyi bezlichi peredpered ostannih mozhna potrapiti tilki v peredostannye i tak dali poki ne dovedemo sho yakes pered peredostannye polozhennya i ye pochatkovim Cya stattya ye zagotovkoyu Vi mozhete dopomogti proyektu dorobivshi yiyi Ce povidomlennya varto zaminiti tochnishim Primitki Arhiv originalu za 29 sichnya 2020 Procitovano 27 lyutogo 2021 DzherelaF F Nagibin E S Kanin Reshenie zadach s konca Matematicheskaya shkatulka Prosveshenie 1976 ros Div takozhZadacha shahi Mat slonom i konemPosilannyaZadachi sho rozv yazuyutsya zkincya nedostupne posilannya Metod resheniya zadach s konca ros Mat slonom i konem ros