Решение задачи с конца — алгоритм решения задачи, когда производится обратный расчёт для вычисления каких-либо неизвестных данных на основе уже известного конечного результата.
Простой пример К некоторому числу прибавили 1, умножили сумму на 2, произведение разделили на 3 и отняли от результата 4. Получилось 5. Какое число было? Решение
5 + 4 = 9 9 · 3 = 27 27 : 2 = 13.5 13.5 - 1 = 12.5
Ответ: 12.5
Было совершено четыре математические операции в обратном порядке.
Тот же ответ можно получить решив уравнение:
Более сложный пример Один биолог открыл удивительную разновидность амёб. Каждая из них через минуту делится на две. В пробирку биолог кладёт одну амёбу, и ровно через час вся пробирка оказывается заполненной амёбами. Сколько потребовалось бы времени, чтобы вся пробирка заполнилась амёбами, если бы в неё положили вначале не одну амёбу, а две?
Решение: Так как одна амёба через минуту разделится на две, а ещё через 59 минут вся пробирка заполнится амёбами, то нужно 59 минут, чтобы две амёбы заполнили пробирку.
Поиск выигрышной стратегии для игр Анализ с конца используют при поиске выигрышных и проигрышных ситуаций для анализа игр. Выигрышность доказывается «с конца», с использованием идей динамического программирования: сначала доказывается, что находясь в одном из «предпоследних положений» можно попасть в «последнее» (выигрышное), затем — что из некоторого множества «предпредпоследних» можно попасть только в «предпоследнее» и так далее, пока не докажем, что «предпред…предпоследнее» положение является начальным. (См. функция Гранди).
Примечания
Категория:Программирование Категория:Математическая логика