Hanoi qüllələri

Hər bir proqramçı "Hanoi qüllələri" tapmacasını tanıyır. Qısa olaraq onun şərtini xatırladaq.

3 çubuq var: A, B, C. Əvvəlcə n fərqli diametrli disk A çubuğunda yerləşdirilib: ən kiçik disk yuxarıda, diametri artan şəkildə aşağıya doğru düzülüb. İkinci və üçüncü çubuqlar isə boşdur.

Bütün diskləri A çubuğundan B çubuğuna, C çubuğunu əlavə olaraq istifadə edərək köçürmək lazımdır.

Bir addımda yalnız bir üst diski götürmək və onu ya boş çubuğa, ya da üstündəki diskdən daha böyük diametrə malik olan çubuğa qoymaq icazəlidir.

Demək olar ki, bütün proqramlaşdırma kitablarında məsələnin rekursiv həlli mövcuddur. Məsələn, aşağıda Pascal dilində həll verilmişdir.

Procedure Hanoi (A, B, C: integer; N:integer);

Begin

If N>0 then

Begin

Hanoi (A, C, B, N-1);

Writeln('Disk ', N, ' from ', A, ' to ', B);

Hanoi (C, B, A, N-1)

End

End;

Məlumdur ki, yuxarıda göstərilən həll (2^n–1) addım tələb edir. Başlanğıc yerləşməni nəzərə alaraq, üç çubuqda n diskin yerləşdirilməsi üçün ümumilikdə 2^n kombinasiya mövcuddur. Bəzi kombinasiyalar alqoritmin icrası zamanı heç vaxt rast gəlinmir. Məsələn, "CAB" kombinasiyası n = 3 olduqda oyunda heç vaxt rast gəlinməyəcək (ən kiçik disk C çubuğunda, orta A çubuğunda və ən böyük B çubuğunda yerləşdirilib).

Verilmiş kombinasiyanın oyunda rast gəlinib-gəlinməyəcəyini müəyyən edən proqram yazın.