Решение задачи с конца

Решение задачи с конца — алгоритм решения задачи, когда производится обратный расчёт для вычисления каких-либо неизвестных данных на основе уже известного конечного результата.

Простой пример

 
 К некоторому числу прибавили 1, умножили сумму на 2, произведение разделили на 3 и отняли от результата 4. Получилось 5. Какое число было?

Решение

5 + 4 = 9
9 · 3 = 27
27 : 2 = 13.5
13.5 - 1 = 12.5

Ответ: 12.5

Было совершено четыре математические операции в обратном порядке.

Тот же ответ можно получить решив уравнение:

Более сложный пример

 
Один биолог открыл удивительную разновидность амёб. Каждая из них через минуту делится на две. В пробирку биолог кладёт одну амёбу, и ровно через час вся пробирка оказывается заполненной амёбами. Сколько потребовалось бы времени, чтобы вся пробирка заполнилась амёбами, если бы в неё положили вначале не одну амёбу, а две?[1]

Решение: Так как одна амёба через минуту разделится на две, а ещё через 59 минут вся пробирка заполнится амёбами, то нужно 59 минут, чтобы две амёбы заполнили пробирку.

Поиск выигрышной стратегии для игр

Анализ с конца используют при поиске выигрышных и проигрышных ситуаций для анализа игр. Выигрышность доказывается «с конца», с использованием идей динамического программирования: сначала доказывается, что находясь в одном из «предпоследних положений» можно попасть в «последнее» (выигрышное), затем — что из некоторого множества «предпредпоследних» можно попасть только в «предпоследнее» и так далее, пока не докажем, что «предпред…предпоследнее» положение является начальным. (См. функция Гранди).

Примечания
  1. Ф. Ф. Нагибин, Е. С. Канин. Решение задач с конца // Математическая шкатулка. — Просвещение, 1976. — 1 000 000 экз.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.