Ханойски кули
Задача за ханойските кули
Разполагаме с три "пилона", върху които могат да се нареждат
краен брой "дискове" с целочислен диаметър. Никои два диска не са с
еднакъв диаметър и даден диск може да се постави върху друг, само ако е
с по-малък диаметър от него.
В началото всички дискове са на първия
пилон (фиг 1). Да се даде последователност от ходове (премствания на един диск), като на
всеки ход може да се взема само най-горния диск на даден пилон и да се
поставя само върху по-голям диск на някой друг пилон или на празен пилон. След изпълнение на тези ходове всички дискове трябва да се озоват на последния пилон.
Фиг.1 Начална конфигурация на ханойските кули
Задача 1. Да се реализира функция
void move (int Source, int Destination, int Temp, int n)
Която довежда до изпечатване на ходовете, необходими за преместване на n диска от пилон Source на пилон Destination.
Едно решение на задачата се крие в следаната рекурсивна идея. Ако n>0 да преместим n-1 диска от Source на Temp. Сега да преместим един диск от Source на Dest. И накрая да преместим n-1 диска от Temp на Dest.
Хубаво е да се помисли защо такъв алгоритъм винаги завършва и още по-хубаво: довежда до коректно решение.
Задача 2. Да се допълни решението на горната задача по такъв начин, че след всеки ход да се изпечава новото състояние на пилоните.
Например на отделен ред за всеки пилон можем да печатаме последователно диаметрите на дисковете му. Хубаво е да се обмисли подходяща структура от данни за представяне на задачата (двумерен масив + още един масив за броя на дисковете за всеки пилон).
The Tower of Hanoi (sometimes referred to as the Tower of Brahma or the End of the World Puzzle) was invented by the French mathematician, Edouard Lucas, in 1883. He was inspired by a legend that tells of a Hindu temple where the pyramid puzzle might have been used for the mental discipline of young priests. Legend says that at the beginning of time the priests in the temple were given a stack of 64 gold disks, each one a little smaller than the one beneath it. Their assignment was to transfer the 64 disks from one of the three poles to another, with one important provisoøa large disk could never be placed on top of a smaller one. The priests worked very efficiently, day and night. When they finished their work, the myth said, the temple would crumble into dust and the world would vanish.
Едно решение на задачата се крие в следаната рекурсивна идея. Ако n>0 да преместим n-1 диска от Source на Temp. Сега да преместим един диск от Source на Dest. И накрая да преместим n-1 диска от Temp на Dest.
Хубаво е да се помисли защо такъв алгоритъм винаги завършва и още по-хубаво: довежда до коректно решение.
Задача 2. Да се допълни решението на горната задача по такъв начин, че след всеки ход да се изпечава новото състояние на пилоните.
Например на отделен ред за всеки пилон можем да печатаме последователно диаметрите на дисковете му. Хубаво е да се обмисли подходяща структура от данни за представяне на задачата (двумерен масив + още един масив за броя на дисковете за всеки пилон).
Малко любопитни факти за ханойските кули, взети от
http://www.lhs.berkeley.edu/Java/Tower/towerhistory.html
http://www.lhs.berkeley.edu/Java/Tower/towerhistory.html
The Tower of Hanoi (sometimes referred to as the Tower of Brahma or the End of the World Puzzle) was invented by the French mathematician, Edouard Lucas, in 1883. He was inspired by a legend that tells of a Hindu temple where the pyramid puzzle might have been used for the mental discipline of young priests. Legend says that at the beginning of time the priests in the temple were given a stack of 64 gold disks, each one a little smaller than the one beneath it. Their assignment was to transfer the 64 disks from one of the three poles to another, with one important provisoøa large disk could never be placed on top of a smaller one. The priests worked very efficiently, day and night. When they finished their work, the myth said, the temple would crumble into dust and the world would vanish.
Последно модифициране: събота, 12 ноември 2011, 17:38