Ханойска кула: Разлика между версии

Изтрито е съдържание Добавено е съдържание
Премахната редакция 3707566 на 83.222.163.171 (б.) daite mu go kato iska
Ред 5:
Съществува вариант на играта със 64 диска, наречен Кулата на Брахма. Легендата разказва, че когато монасите от Брахма приключат играта ще настъпи краят на Света.
 
Не прочетохте ли!?
== Алгоритъм за рекурсивно решение с най-малко ходове ==
Ще обобщим решението, което търсим за n диска:
* това позволява да изследваме случаите в които n е малко
* намирайки решение за n диска, можем лесно да изчислим n=8 и n=64
 
Нека T<sub>n</sub> бъде броят ходове, нужни за решаване на задачата. Един от начините за решаване на задачата с n диска е:
* преместваме (n-1) диска от левия към средния стълб: T<sub>n-1</sub> хода
* преместваме най-големия диск от левия на десния стълб: 1 ход
* преместваме дисковете от средния стълб на десния: T<sub>n-1</sub> хода
Следователно T<sub>n</sub> = 2T<sub>n-1</sub>+1, ∀n>1
 
От където получаваме:
 
<math>\left\{\begin{array}{ll}
T_{0} = 0 \\ T_{n} = 2T_{n-1}+1, \forall n \geq 1
\end{array}\right.</math>
 
Сега можем да проверим стойностите на T<sub>n</sub> при малки стойности на n:
 
T<sub>1</sub> = 2T<sub>0</sub>+1 = 1
 
T<sub>2</sub> = 2T<sub>1</sub>+1 = 3
 
T<sub>3</sub> = 2T<sub>2</sub>+1 = 7
 
Това решение може да бъде представено на различни програмни езици като например [[CAML]]:
 
<code>
let rec T n=
if n=0
then 0
else 1+(2*(T(n-1)));;
</code>
 
или [[Python]]:
 
<code>
def T(n):
if(n==0):
return 0
else
return 1+2*T(n-1)
</code>
 
или [[C]]:
 
<source lang='C'>
int conf[HEIGHT]; /* Елементът conf[d] връща текущата позиция на диск d. */
void move(int d, int t) {
/* премества диск d на стълба t */
conf[d] = t;
}
void hanoi(int h, int t) {
if (h > 0) {
int f = conf[h-1];
if (f != t) {
int r = 3 - f - t ;
hanoi(h-1, r);
move(h-1, t);
}
hanoi(h-1, t);
}
}
</source>
 
Въпреки, че този рекурсивен алгоритъм позволява да се изчисли T<sub>n</sub>, той не е ефикасен при големи стойности на n. За това решението е да намерим затворена форма на [[Рекурсия|рекурсията]]. Нека погледнем стойностите на T<sub>n</sub> при n=0...7:
<table style="text-align: center;border: 1px solid #333" border="1" cellspacing="0" width="100%">
<tr style="background: #ddf"><td>n</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td></tr>
<tr><td>T<sub>n</sub></td><td>0</td><td>1</td><td>3</td><td>7</td><td>15</td><td>31</td><td>63</td><td>127</td></tr>
</table>
Забелязваме, че T<sub>n</sub> = 2<sup>n</sup>-1, ∀n≥0.
Това свойство може да бъде доказано, чрез [[математическа индукция]]:
* T<sub>0</sub>=2<sup>0</sup>-1=0, следователно основният случай е верен.
* Нека n > 0. Да предположим, че T<sub>k</sub> = 2<sup>k</sup>-1 за 0≤k≤n-1. Тогава T<sub>n</sub> = 2T<sub>n-1</sub>+1 = 2(2<sup>n-1</sup>-1)+1 (според индукционната хипотеза) От където T<sub>n</sub> = 2<sup>n</sup>-1
 
Така за играта Ханойска кула получаваме T<sub>8</sub> = 2<sup>8</sup>-1 = 255 хода, а за Кулата на Брахма - T<sub>64</sub> = 2<sup>64</sup>-1 ≈ 10<sup>19,3</sup> хода. Ако предположим, че можем да извършваме по един ход на секунда, то за решаването на Ханойска кула ще са ни нужни 4мин и 15 секунди, докато за кулата на Брахма ще са необходими около 585 милиарда години от където и идва легендата за края на света.
 
== Приложения ==