ჰანოის კოშკები

თუ რეკურსიის სახელმძღვანელო გაიარეთ, მაშინ მზად ხართ, ნახოთ სხვა ამოცანა, რომელშიც რამდენჯერმე რეკურსიის გაშვება ძალიან გვეხმარება. მას ჰქვია ჰანოის კოშკი. მოცემული გაქვთ სიმრავლე სამი ლურსმნით და $n$‍ რგოლით, თითოეული რგოლი განსხვავებული ზომისაა. ლურსმნებს დავარქვათ A, B და C, რგოლები კი გადავნომროთ 1-დან (ყველაზე პატარა რგოლი) $n$‍-მდე (ყველაზე დიდი რგოლი). დასაწყისში $n$‍ რგოლიდან თითოეული არის A ლურსმანზე, ზომის კლებადობით ქვემოდან ზემოთ, ანუ რგოლი $n$‍ არის ძირში და რგოლი 1 არის კენწეროში. აი, როგორ გამოიყურება ჰანოის კოშკი $n=5$‍ რგოლისთვის:

მიზანია, ყველა $n$‍ რგოლის გადაადგილება A ლურსმნიდან B ლურსმანზე:

მარტივი ჩანს, არა? არც ისე მარტივია, რადგან ორი წესი უნდა დაიცვათ:

შეიძლება, ფიქრობთ, რომ ეს ამოცანა ძალიან მნიშვნელოვანი არაა. პირიქით! ლეგენდა მოგვითხრობს, რომ სადღაც აზიაში (ტიბეტში, ვიეტნამში, ინდოეთში — აირჩიეთ, რომელი ლეგენდაც მოგწონთ), ბერები ხსნიან ამ ამოცანას 64 რგოლით და — ასე გრძელდება ამბავი — ბერებს სწამთ, რომ როგორც კი 64-ივე რგოლის A ლურსმნიდან B ლურსმანზე გადაადგილებას მორჩებიან, ჩვენი ორი წესის მიხედვით, სამყარო დასრულდება. თუკი ბერები მართლები არიან, შიშისგან პანიკამ უნდა მოგვიცვას?

ჯერ ვნახოთ, როგორ უნდა ამოვხსნათ ეს ამოცანა რეკურსიულად. ძალიან მარტივი შემთხვევით დავიწყოთ: ერთი რგოლი, ანუ, $n=1$‍. $n=1$‍-ის შემთხვევა იქნება ჩვენი ბაზისი. ყოველთვის შეგიძლიათ, რგოლი 1 გადააადგილოთ A ლურსმნიდან B ლურსმანზე, რადგან იცით, რომ მის ქვეშ მყოფი ყველა რგოლი უნდა იყოს უფრო დიდი. A და B ლურსმნები კი არაფრით არიან განსაკუთრებული. შეგიძლიათ, რგოლი 1 გადააადგილოთ B ლურსმნიდან C ლურსმანზე თუ ასე გსურთ, ან C ლურსმნიდან A ლურსმანზე, ან ნებისმიერი ლურსმნიდან ნებისმიერ ლურსმანზე. ჰანოის კოშკის ამოხსნა ერთი რგოლით ტრივიალურია და ის მოიცავს მხოლოდ ერთი რგოლის გადატანას ერთხელ.

ორ რგოლზე რას ფიქრობთ? როგორ ამოხსნით ამოცანას, როცა $n=2$‍? ამის გაკეთება შეგიძლიათ 3 ნაბიჯით. აი, როგორ გამოიყურება ის დასაწყისში:

პირველ ყოვლისა, გადააადგილეთ რგოლი 1 A ლურსმნიდან C ლურსმანზე:

აღვნიშნოთ, რომ ჩვენ ვიყენებთ C ლურსმანს თავისუფალ ლურსმნად, ადგილი, სადაც დავდებთ რგოლ 1-ს, რათა მივწვდეთ რგოლ 2-ს. ახლა, როცა რგოლი 2 — ძირში მყოფი რგოლი — გამოთავისუფლებულია, გადააადგილეთ ის B ლურსმანზე:

საბოლოოდ, გადადეთ რგოლი 1 C ლურსმნიდან B ლურსმანზე:

ეს ამონახსნი საჭიროებს სამ ნაბიჯს და, კიდევ ერთხელ, არაფერია განსაკუთრებული A ლურსმნიდან B ლურსმანზე ორი რგოლის გადატანაში. შეგიძლიათ, ისინი გადადოთ B ლურსმნიდან C ლურსმანზე A ლურსმნის გამოყენებით თავისუფალ ლურსმნად: რგოლი 1 გადადეთ B ლურსმნიდან A ლურსმანზე, შემდეგ რგოლი 2 გადადეთ B ლურსმნიდან C ლურსმანზე და დაასრულეთ რგოლი 1-ის გადატანით A ლურსმნიდან C ლურსმანზე. როგორ ფიქრობთ, 1 და 2 რგოლების გადატანა ნებისმიერი ლურსმნიდან ნებისმიერზე სამ სვლაში შეგიძლიათ? (თქვით „დიახ“)

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.