Кула на Ханой
Кулата на Ханой е една от популярните пъзели на 19 век. Този проблем, който илюстрира рекурсията, е любим на програмистите.
Правилата на играта Tower of Hanoi са както следва:
Няколко кръга с различни размери са подредени един върху друг на една от пръчките, образувайки кула. Цел: преместване на кулата в друго поле.
При пренареждане трябва да се спазват някои правила.
1) кръговете се пренареждат от един прът на друг, докато се подреждат един върху друг, така че да се получат малки кули. Не можете да оставяте кръгове настрана или да поставяте един кръг вместо друг;
2) при всеки ход се движи само един кръг. Няколко кръга не могат да бъдат прехвърлени едновременно. Например, забранено е да вземате халба във всяка ръка;
3) можете да вземете кръг само от върха на кула и да го поставите само на върха на друга кула. Не можете да вземете кръг от средата на кула или да го вмъкнете в средата на друга кула;
4) забранено е поставянето на по-голям кръг върху по-малък.
Фигурата показва няколко разрешени и няколко забранени хода.
Така че можете: Така че не можете:
Тази романтична легенда е измислена през 1883 г. от френския математик ЕДУАРД ЛУКА.
• През 1878 г. Лукас дава критерий за определяне дали числото на Мерсен Mp = 2p - 1 е основно или съставно, сега известно като тест на Luc-Lemaire. Прилагайки метода си, Лука установява, че M127 = 2127 - 1 е просто число. В продължение на 75 години това число остава най-голямото просто число, познато на науката. Освен това му позволи да определи 12-то перфектно число.
• Той е първият, който забелязва и описва свойствата на числата, по-късно кръстени на него - числата на Лукас.
• Описани свойствата на последователностите, които удовлетворяват хомогенни линейни повтарящи се уравнения от втори ред, частен случай на които са числата на Фибоначи. Такива последователности сега се наричат последователности на Лука.
• Измислил редица интересни пъзели, включително известния пъзел на Ханойската кула.
Някъде в непроходимата джунгла, недалеч от град Ханой, има манастир на бог Брахма. В началото на времето, когато Брахма създава Света, той издига три високи диамантени пръчки в този манастир и поставя 64 диска от чисто злато върху един от тях. Той заповяда на монасите да преместят тази кула на друга пръчка (в съответствие с правилата, разбира се). От това време монасите работят денем и нощем. Когато приключат работата си, ще дойде краят на света.
III. Пъзел решение:
А) Формулата за зависимостта на ходовете от броя на кръговете в кулата
Ако съставите таблица на зависимостта на ходовете от броя на кръговете в играта, резултатът ще бъде очевиден:
Брой кръгове: Оптимален брой удари:
Резултатът е числова последователност: 1,3,7,15,31,.
Първо решение. Второ решение.
Въпрос: "Как да разбера следващия номер на последователността, като знам предишния?" Нека напишем степента на 2
Ако умножим предишното число по 2 и добавим едно, получаваме необходимото. 21 = 2; 22 = 4; 23 = 8; 24 = 16; 25 = 32
7 = 2 * 3 + 1 Извадете едно от тези числа, получаваме нашата последователност:
Нека означим n-то число чрез n, получаваме формулата: 15 = 24 -1
a 3 = 2 * a 2 + 1 an = 2n -1
Б) Решаване на задачата на програмен език.
Както е посочено във въведението: Кулата на Ханой е една от популярните пъзели от 19-ти век.
Играта Towers of Hanoi е както следва. Има N диска и три пръта: A, B и C. В първоначалната конфигурация всички дискове се поставят върху един от прътите, образувайки кула под формата на пирамида (по-малките дискове са разположени отгоре на по-големите нечий). Ход -> е прехвърляне на един диск. Можете да преместите горния диск от стъблото на стъблото, но не можете да поставите по-голям диск върху по-малък диск. Необходимо е да се посочи последователност от ходове, които преместват цялата кула от оригиналната лента към дадена.
Алгоритъм за решаване на проблема:
1. Ако n> 0, спрете
2. Преместете горните n-1 дискове от прът A на прът B, като използвате прът C като помощно средство.
3. Преместете останалия диск от прът A на прът C
4. Преместете n-1 дискове от прът B на прът C, като използвате прът A като помощно средство.
Лесно е да се види, че този алгоритъм е рекурсивен. Всъщност на стъпка 2 и стъпка 4 от алгоритъма се изисква да се реши проблем, подобен на оригиналния, само за по-малък брой дискове.
Рекурсивният алгоритъм е алгоритъм, който се използва като спомагателен.
Изброяване на програма на езика за програмиране Turbo Pascal.
ПРОГРАМА ханой; typebachnia = char; var a, b, c: бахния; k, kol: цяло число;
процедура Н (n: цяло число; a, b, c: бахния); започнете, ако n> 0, тогава започнете
Н (n-1, a, c, b); запис (‘преместване на диск’, n); writeln (a, ‘->,’ c); kol: = kol + 1;
Н (n-1, b, a, c); край; край;
започнете да пишете (‘въведете броя на кръговете =’); readln (k); a: = 'A'; b: = 'B'; c: = 'C';
Н (k, a, b, c); writeln ('брой стъпки =', kol); край.
Резултат от теста на програмата
С броя на кръговете K = 3
преместване на диск 1 A -> C
преместване на диск 2 A -> B
преместване на диск 1 C -> B
преместване на диск 3 A -> C
преместване на диск 1 B -> A преместване на диск 2 B -> C
преместване на диск 1 A -> C
БРОЙ СТЪПКИ = 7
(проверка на формулата 2n -1 = 23 -1 = 7 стъпки)
С броя на кръговете K = 4, преместете диск 1 A -> B преместете диск 2 A -> C преместете диск 1 B -> C преместете диск 3 A -> B преместете диск 1 C -> A преместете диск 2 C -> B преместване на диск 1 A -> B преместване на диск 4 A -> C преместване на диск 1 B -> C преместване на диск 2 B -> A преместване на диск 1 C -> A преместване на диск 3 B -> C преместване на диск 1 A -> B преместване на диск 2 A -> C преместване на диск 1 B -> C
БРОЙ СТЪПКИ = 15
(проверка на формулата 2n -1 = 24 -1 = 15 стъпки)
Изброяване на програма на езика за програмиране QBasic.
REM ОСНОВНА ПРОГРАМА
ВХОД „въведете N =“; N
ПЕЧАТ “брой стъпки =”; кол
REM РЕКУРСИВНА ПОДПРОГРАМА
1: АКО N = 0 СЛЕД ВРЪЩАНЕ
ПЕЧАТ „преместване на диск“; N; A; “->”; В
В) Време от "началото" до "края" на света.
Интересно е да се изчисли колко време ще отнеме на монасите от манастира Брахма (виж легендата) да завършат работата си и ще дойде „краят“ на света.
Ако използваме получената формула от точка III, раздел А), тогава можем да изчислим, че те ще завършат работата си в (264 -1) стъпки.
Да предположим, че на монасите им е необходима 1 секунда, за да завършат един ход на играта. Нека приблизително преценим колко време ще им отнеме да изпълнят цялата задача, или можем да кажем следното: Колко време трябва да мине от „началото“ до „края“ на света?
264 = 24 * 260 = 16 * 260 (16 * (210) 6 (16 * (10 3) 6 (16 * 1018, тъй като 210 = 1024 (1000 = 10 3 получи, че броят на ходовете е приблизително равен на шестнадесет квинтилиона).
За един ден 24 часа, за час 60 * 60 = 3600 секунди.
И така, за ден 24 * 3600 = 86 400 секунди
За една година - още 365, т.е. приблизително 32 милиона секунди или 32 * 106 секунди
За да разберете от колко години се нуждаят монасите, трябва да разделите едно от получените числа на друго:
(16 * 1018)/(32 * 106) = 0,5 * 10 12 = 500 000 000 000 години
Така че, ако се притеснявате за настъпващия "край" на света, тогава не можете да се притеснявате, петстотин милиарда години са достатъчно дълъг период.
Г) Решаване на проблема на суперкомпютър.
Представете си, вместо монаси, бъдещ суперкомпютър: Оставете го да извършва 1 милиард операции в секунда. Колко време отнема на компютъра да премести кула от 64 кръга?
Тъй като компютърът работи милиард пъти по-бързо от монасите, това ще отнеме милиард пъти по-малко време - само 500 години.
Има една притча:
„Двама приятели спориха:
-Светът отдавна трябваше да умре!
-Защо мислиш така?
-Знаете ли, има древна легенда, според която си струва да преместите само 64 чаши и краят на света ще дойде.
- Само 64, струва си да се има предвид, че ако един ход се направи за 1 секунда, тогава могат да се извършват 3600 трансфера на час
- И около сто хиляди на ден. За десет дни милион хода. С един милион хода можете, сигурен съм, да прехвърлите поне хиляда кръгове.
- Ти грешиш. Отнема 500 милиарда години, за да се прехвърлят само 64 кръга.!
- Да, това е много дълго време "
Бих искал да кажа, че игрите и пъзелите са прекрасен свят за прилагане на програмиране, развитие на логическо и алгоритмично мислене.