Řešení problému od konce

Řešení problému od konce je algoritmus pro řešení problému, kdy se provádí zpětný výpočet pro výpočet neznámých dat na základě již známého konečného výsledku.

Jednoduchý příklad

K určitému číslu přičetli 1 , součet vynásobili 2, součin vydělili 3 a od výsledku odečetli 4. Ukázalo se, že 5. Jaké to bylo číslo?

Řešení

5 + 4 = 9 9 3 = 27 27 : 2 = 13,5 13,5 - 1 = 12,5

Odpověď: 12.5

Čtyři matematické operace byly provedeny v opačném pořadí.

Stejnou odpověď lze získat řešením rovnice:

Složitější příklad

Jeden biolog objevil úžasnou rozmanitost améby. Každý z nich je v minutě rozdělen na dva. Biolog vloží jednu amébu do zkumavky a přesně o hodinu později se celá zkumavka naplní amébou. Jak dlouho by trvalo, než by se celá zkumavka naplnila amébami, kdyby se do ní nejprve nevložila jedna améba, ale dvě? [jeden]

Řešení: Protože se jedna améba během minuty rozdělí na dvě a po dalších 59 minutách se celá zkumavka naplní amébami, trvá dvěma amébám 59 minut, než zkumavku naplní.

Hledání vítězné strategie pro hry

End-to-end analýza se používá k nalezení vítězných a prohraných situací pro analýzu hry . Vítězství je dokázáno „od konce“ pomocí myšlenek dynamického programování : nejprve je dokázáno, že být na jedné z „předposledních pozic“ se můžete dostat na „poslední“ (vítězství), pak – že z určitého souboru z „předposlední“ se můžete dostat pouze na „předposlední“ a tak dále, dokud neprokážeme, že pozice „předchozí ... předposlední“ je výchozí. (Viz funkce Grandi ).

Poznámky

1. ↑ F. F. Nagibin, E. S. Kanin . Řešení úloh od konce // Matematická krabice. - Osvícenství, 1976. - 1 000 000 výtisků.