Математическата игра на Люка за Ханойските кули

[lyk4o0]

(математическата игра на Люка за Ханойските кули)
Имате 3 еднакви стълба и 64 различни по големина диска. Още в самото начало дисковете са подредени на левия стълб, като най-големият е най-отдолу, а най-малкият - отгоре. Целта е кулата от дискове да бъде преместена на десния стълб. Може да се мести само по един диск на ход и не може по-голям диск да бъде поставен върху по-малък. Правилното им преместване и подреждане на точно толкова на брой дискове образува така наречената Кула на Брахма. Според легенда, при успешното и построяване ще настъпи краят на Света? Каква е вероятността легендата да се сбъдне и кулата да бъде издигната без грешка?

[loving_math]

За вероятността да я построят без грешка не мога да кажа каква е, но вероятността това да се случи скоро , е нулева. Да празнувам тогаав, че краят на света е твърде далеч във времото.

Да оставим шегата настрана.Имаме 64 диска, които предполагам, че както в разните там интернет игри с подобна задача, трябва да бъдат преместени от първия стълб на третия, като вторият се ползва за междинна станция.

Нека разгледаме примерчета с по- малко на брой дискове, за да хванем алгоритъма.
Нека стълбовете са А,В и С, като целта ни е да преместим дисковете от А на С, ползвайки междинно В.

Нека разполагаме с един диск на стълб А. Взимаме го и директно го прехвърляме на стълб С.
1 диск - един ход
Нека разполагаме с два диска на стълб А. Нека 1 е големият, а две -малкият.
1. Преместваме 2 от А на В
2. Преместваме 1 от А на С
3. Преместваме 1 от В на С
2 диска - 3 хода
Нека дисковете на стълб А са 3.
Като си поиграем по горната схема, ще видим , че са ни нужни 7 хода за пълно преместване до С.
3 диска - 7 хода
Нека дисковете на стълб А са 4.
Като си поиграем по горната схема, ще видим че са ни нужни 15 хода за пълно преместване до С.
4 диска - 15 хода и т.н...
1-1
2->3 => 2.1 +1= 3
3->7 => 2.3+1= 7
4->15 => 2.7 + 1=15
5->31 => 2.15+1 =31
6->63 => 2.31+1= 63
7->127 =>2.63+1=127
=> Търсената формула за броя ходове при правилна подредба на n диска е 2N+1 , където N e броят на ходовете, необходими за правилната подредба на n-1 дискове.
Да, но това не ни върши особена работа, тъй като ще се изгърбим от сметки нататък .
1,3,7,15,31,63,127....
2-1, 2^2-1, 2^3-1, 2^4-1,2^5-1,2^6-1..............2^63-1, 2^64-1
Болдваното е броят на ходовете за безгрешна наредба на 64-те диска.

За майтап само да приемем, че за един ход са ни нужни няколко секунди поне... И така, 2-3 секунди, умножени по броя ходове ни докарват милиарди години работа. Не ми се смята колко точно.

[martosss]

не разбирам в случая как определяш шанса...
1) задължително ли е да използваш минимален брой ходове
2) трябва ли да включваме във вероятността възможност да се направи грешен ход?

За да сметнеш вероятността просто гледаш колко възможни премествания имаш на всеки ход(мисля, че са 2).
Като се замисля обаче те са различни за всеки ход, ако имаш само 1 купчина имаш 2 възможности, а като имаш 3 купчинки стават повече... така че се променя.. така че не знам, но както и да е трябва първо да уточниш горните две точки...