Ханой qüllələrinin bir köçürülməsi
Hanoy qüllələri məsələsinə nəzər salaq. Bu məsələdə üç dirək və bir sıra dairəvi disklər var. Disklərin sayı n ilə göstərilir. Disklər müxtəlif ölçülərdədir və heç bir iki disk eyni ölçüdə deyil. Əsas qayda budur ki, böyük diski kiçik diskin üzərinə qoymaq olmaz. Diskləri 1 (ən kiçik) ilə n (ən böyük) arasında nömrələyək, dirəkləri isə A, B və C adlandıraq. Başlanğıcda bütün disklər A dirəyində yerləşdirilib. Məqsəd onları C dirəyinə köçürməkdir, hər dəfə yalnız bir diski köçürərək və heç vaxt böyük diski kiçik diskin üzərinə qoymamaq şərti ilə. Məlum həll yolu, rekursiv olaraq n–1 diski A-dan B-yə köçürmək, sonra bir diski A-dan C-yə köçürmək və yenidən rekursiv olaraq n–1 diski B-dən C-yə köçürməkdir.
Hanoy qüllələri məsələsinin rekursiv həllinin psevdokodu belədir:
move(num_disks, from_post, spare_post, to_post)
if (num_disks == 0)
return
move(num_disks – 1, from_post, to_post, spare_post)
print ("Move disk ", num_disks, " from ", from_post, " to ", to_post)
move(num_disks – 1, spare_post, from_post, to_post)
Bu məsələdə verilmiş k və n üçün k-cı köçürməni tapmaq lazımdır.
Giriş verilənləri
Hər bir sətir iki tam ədəd k və n ehtiva edir. Giriş məlumatlarının sonunda iki sıfırdan ibarət sətir yerləşir. Giriş dəyərləri düzgündür, k və n müsbət tam ədədlərdir, k 2^n-dən kiçikdir, buna görə k-cı köçürmə mövcuddur, n 60-dan çox deyil, buna görə cavab 64-bitlik tam ədəd tipinə yerləşir.
Çıxış verilənləri
Alqoritm tərəfindən həyata keçirilmiş axtarılan k-cı köçürməni çıxarın. Çıxış formatı belə olmalıdır: "Case", bir boşluq, test nömrəsi, iki nöqtə, bir boşluq və cari test üçün cavab: disk nömrəsi, from_post dirəyinin adı və to_post dirəyinin adı, onları bir boşluqla ayıraraq. Sətirin sonunda boşluqlar çıxarılmamalıdır.