Кула на Ханой - решаване на проблеми с алгоритми и структури от данни
Пъзел от кулите на Ханой е изобретен от френския математик Eduardom Lukasom през 1883. Той е вдъхновен от една легенда, която разказва на индуски замък, където целта, за младите свещеници. В ранните времена са дадени три пръчки и купчина шестдесет и четири златни дискове, всеки от които е малко по-малък от предишния. Това е необходимо, за да пренаредите всички дискове от един бар в друг, след два строго определени условия. На първо място, в даден момент може да се движи само един диск. На второ място, не може да се сложи голям диск на върха на един по-малък. Свещеници работили (и работи и до днес) много спори, ден и нощ, движейки се на всяка секунда един диск. Легендата разказва, че когато те завършат работата си, замъкът ще се превърне в прах, и светът ще изчезне.
Въпреки че легендата и интересно, че не е нужно да се притеснявате за предстоящия край на света. Броят на ударите, необходими за правилното транспониране на кулата от 64-дисковете, се равнява на \ (2 ^ -1 = 18,446,744,073,709,551,615 \). При скорост от един ред в секунда, това отнема \ (\ 584,942,417,355) години! Висока фигура за такъв на пръв поглед прост, пъзела.
Фигура 1 показва пример на конфигурация диск в средата на пътуване от първия до третия клин. Имайте предвид, че (както се регулира от правилата) управлява на всяка от колчетата са образувани по такъв начин, че по-малките винаги лежи на по-големите. Ако никога не сте опитвали да се реши този пъзел, можете да опитате в момента. За това не се нуждае от реални колела и пръти - работа и купчина книги или парчета хартия.
Фигура 1: Пример за местоположение на диск Ханойска кула.
Как да се реши този проблем рекурсивно? Защо да започнем? Какво е най-благоприятният сценарий тук? Нека да помисля за това от края към началото. Да предположим, че първоначално на първи колче ви е кула от пет дискове. Ако вече знаете как да се движат четири от тях на втория клин, можете лесно да се премине към по-ниската кола прът №3, а след това се премине към една и съща кула с пръчка №2. Но какво, ако вие нямате представа как да се движат на кулата от първата четворка? Да предположим, че той е знаел как да се движат на кулата от горните три дискове на третия курс. След това, с движението на четвъртия трудности ще възникнат: Сложете го на втората лента, а след това постави на върха на тези, които са нанизани на третия. Но ако не знаете как да се движат и трите? Е, можете да преместите кулата на два диска на пръта №2, а третият - на прът №3, а след това постави на върха на кула от двете. Но ако все още не разбират как да го направя? Сигурен съм, че ще се съгласите да се движат един диск на третия клин изключително лесно - съществува нищо тривиално. Това звучи като базовия модел, както и?
Ето една обща схема за това как да се движат на кулата с предварително определен източник прът с помощта на междинен:
- Преместване кула (брой дискове - 1) до междинното клин, като се използва предварително определена.
- Поставете останалата диск към даден прът.
- Преместване на кулата от оставане на междинен вал диск до местоназначението, като се използва оригиналния курс.
Докато ние следваме правилото, че по-голям диск в долната част на комина, трите стъпки, описани могат да бъдат използвани рекурсивно обработка на всички по-големи дискове, като че ли те не са били там. Единственото нещо, което ни липсваше в диаграмата по-горе - е идентифицирането на базовия модел. Най-простият кула на Ханой - кула на един и същи диск. В този случай, ние само трябва да се движат на един диск за крайното си местоназначение. Кулата на един диск ще бъде нашата база случай. Между другото, схемата на горните стъпки, доведе до това, всеки път, когато се намалява височината на блока, монтиран на кула в параграфи 1 и 3. Обява 1 показва кода в Python за решаване на Кулите на Ханой.
Имайте предвид, че Обява 1 е почти идентичен на словесно описание. Ключът към простотата на алгоритъм, който ние правим две различни рекурсивно повикване, един в ред 3, а вторият - в съответствие 5. В ред 3, ние се преместят всички дискове с изключение на дъното, от първоначалното до междинния вал. Следващият ред просто пренарежда долния диск до крайната си позиция. След това през линия 5 се движим кулата от междинния вал на върха на най-големия диск. Базовата случай се открива, когато височината на кулата е равна на нула. В този случай, нищо не се случва, така че функцията moveTower се връща празен. При обработката на базовия модел, че е важно да се помни, че една проста замяна на moveTower - е това, което в крайна сметка позволява moveDisk функция, за да се нарече.
Функция moveDisk. показано на Обявата 2. Много е просто. Всичко, което тя прави - той отпечатва, че устройството е била преместена от един бар в друг. Ако изпишете и да започне moveTower програма. ще видите как тя ще ви напиша много ефективно решение на пъзела.
Програма ActiveCode 1 съдържа цялостно решение за проблема с трите диска.
Изпълнете Save Load Покажи в Codelens
Рекурсивно решение на проблема на кулите на Ханой. (Ханой)
Сега, можете да видите кода за moveTower. и moveDisk. може да се чудя защо ние нямаме структура от данни, които биха изрично проследите кои диск, на който лежи на пръчката. Ето един съвет: ако изрично следите дискове, може да се наложи да използвате три обекта стека - по един за всяко ядро. Отговорът е в това, че Python ни дава купища имплицитно и когато имаме нужда от нея.