Рішення задачі з кінця
Рішення задачі з кінця — алгоритм рішення, коли проводиться зворотний розрахунок для обчислення будь-яких невідомих даних на основі вже відомого кінцевого результату. «Невідомими даними» може бути набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі (тобто алгоритм). Підхід «з кінця» носить універсальний характер. Крім математики, такий підхід використовується при рішенні лінгвістичних та інших головоломок, шахових етюдів тощо.
Простий приклад
Треба знайти слово з 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 легша за решту)[1].(рос.)
Підхід «з кінця» у фізиці
Підхід «з кінця», аналіз розмірності — метод, який використовується фізиками для побудови обґрунтованих гіпотез про взаємозв'язок різних розмірних параметрів складної фізичної системи. Іноді аналіз розмірності можна використовувати для отримання формул (з точністю до безрозмірнісної константи). Суть методу полягає в тому, що з параметрів, що характеризують систему, складається вираз, що має потрібну розмірність.
При аналізі розмірностей формул розмірність лівої частини рівняння повинна дорівнювати розмірності правої частини рівняння. Відсутність такої рівності свідчить про невірність формули.
Простий приклад
В Міжнародній системі одиниць (SI) сила має розмірність: Н (ньютон) = кг · м / с2 (LMT−2).
Знаючи, що м/с2 — це прискорення a, легко відтворити формулу сили F:
F=m·a
Пошук виграшної стратегії для ігор
Аналіз «з кінця» використовують при пошуку виграшних і програшних ситуацій для аналізу ігор. Виграшність доводиться «з кінця», з використанням ідей динамічного програмування: спочатку доводиться, що перебуваючи в одному з «передостанніх положень» можна потрапити в «останнє» (виграшне), потім - що з деякої безлічі «передперед...останніх» можна потрапити тільки в «передостаннє» і так далі, поки не доведемо, що якесь «перед ... передостаннє» положення і є початковим.
Примітки
Джерела
- Ф. Ф. Нагибин, Е. С. Канин. Решение задач с конца // Математическая шкатулка. — Просвещение, 1976.(рос.)