If you're seeing this message, it means we're having trouble loading external resources on our website.

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა

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

თუ რეკურსიის სახელმძღვანელო გაიარეთ, მაშინ მზად ხართ, ნახოთ სხვა ამოცანა, რომელშიც რამდენჯერმე რეკურსიის გაშვება ძალიან გვეხმარება. მას ჰქვია ჰანოის კოშკი. მოცემული გაქვთ სიმრავლე სამი ლურსმნით და n რგოლით, თითოეული რგოლი განსხვავებული ზომისაა. ლურსმნებს დავარქვათ A, B და C, რგოლები კი გადავნომროთ 1-დან (ყველაზე პატარა რგოლი) n-მდე (ყველაზე დიდი რგოლი). დასაწყისში n რგოლიდან თითოეული არის A ლურსმანზე, ზომის კლებადობით ქვემოდან ზემოთ, ანუ რგოლი n არის ძირში და რგოლი 1 არის კენწეროში. აი, როგორ გამოიყურება ჰანოის კოშკი n, equals, 5 რგოლისთვის:
სამი კოშკი, რომელთაც აწერია A, B და C. კოშკ A-ს აქვს რგოლები ნომრად 5, 4, 3, 2 და 1, რგოლი 5 არის ძირში და რგოლი 1 არის კენწეროში. კოშკებს B და C არ აქვთ რგოლები.
მიზანია, ყველა n რგოლის გადაადგილება A ლურსმნიდან B ლურსმანზე:
სამი კოშკი, რომელთაც აწერია A, B და C. კოშკ B-ს აქვს რგოლები ნომრად 5, 4, 3, 2 და 1, რგოლი 5 არის ძირში და რგოლი 1 არის კენწეროში. კოშკებს A და C არ აქვთ რგოლები.
მარტივი ჩანს, არა? არც ისე მარტივია, რადგან ორი წესი უნდა დაიცვათ:
  1. ყოველ ჯერზე შეგიძლიათ მხოლოდ ერთი რგოლის გადაადგილება.
  2. არცერთი რგოლი არ უნდა დაიდოს უფრო პატარა რგოლის ზემოთ. მაგალითად, თუ რგოლი 3 არის ლურსმანზე, მაშინ რგოლი 3-ის ქვემოთ არცერთ რგოლს არ უნდა ჰქონდეს 3-ზე მეტი რიცხვი.
შეიძლება, ფიქრობთ, რომ ეს ამოცანა ძალიან მნიშვნელოვანი არაა. პირიქით! ლეგენდა მოგვითხრობს, რომ სადღაც აზიაში (ტიბეტში, ვიეტნამში, ინდოეთში — აირჩიეთ, რომელი ლეგენდაც მოგწონთ), ბერები ხსნიან ამ ამოცანას 64 რგოლით და — ასე გრძელდება ამბავი — ბერებს სწამთ, რომ როგორც კი 64-ივე რგოლის A ლურსმნიდან B ლურსმანზე გადაადგილებას მორჩებიან, ჩვენი ორი წესის მიხედვით, სამყარო დასრულდება. თუკი ბერები მართლები არიან, შიშისგან პანიკამ უნდა მოგვიცვას?
ჯერ ვნახოთ, როგორ უნდა ამოვხსნათ ეს ამოცანა რეკურსიულად. ძალიან მარტივი შემთხვევით დავიწყოთ: ერთი რგოლი, ანუ, n, equals, 1. n, equals, 1-ის შემთხვევა იქნება ჩვენი ბაზისი. ყოველთვის შეგიძლიათ, რგოლი 1 გადააადგილოთ A ლურსმნიდან B ლურსმანზე, რადგან იცით, რომ მის ქვეშ მყოფი ყველა რგოლი უნდა იყოს უფრო დიდი. A და B ლურსმნები კი არაფრით არიან განსაკუთრებული. შეგიძლიათ, რგოლი 1 გადააადგილოთ B ლურსმნიდან C ლურსმანზე თუ ასე გსურთ, ან C ლურსმნიდან A ლურსმანზე, ან ნებისმიერი ლურსმნიდან ნებისმიერ ლურსმანზე. ჰანოის კოშკის ამოხსნა ერთი რგოლით ტრივიალურია და ის მოიცავს მხოლოდ ერთი რგოლის გადატანას ერთხელ.
ორ რგოლზე რას ფიქრობთ? როგორ ამოხსნით ამოცანას, როცა n, equals, 2? ამის გაკეთება შეგიძლიათ 3 ნაბიჯით. აი, როგორ გამოიყურება ის დასაწყისში:
სამი კოშკი, სახელად A, B და C. კოშკ A-ს აქვს რგოლი 2 ძირში და რგოლი 1 კენწეროში. B და C კოშკებს არ აქვთ რგოლები.
პირველ ყოვლისა, გადააადგილეთ რგოლი 1 A ლურსმნიდან C ლურსმანზე:
სამი კოშკი, სახელად A, B და C. A კოშკს აქვს რგოლი 2. B კოშკს არ აქვს რგოლი. C კოშკს აქვს რგოლი 1.
აღვნიშნოთ, რომ ჩვენ ვიყენებთ C ლურსმანს თავისუფალ ლურსმნად, ადგილი, სადაც დავდებთ რგოლ 1-ს, რათა მივწვდეთ რგოლ 2-ს. ახლა, როცა რგოლი 2 — ძირში მყოფი რგოლი — გამოთავისუფლებულია, გადააადგილეთ ის B ლურსმანზე:
სამი კოშკი, სახელად A, B და C. A კოშკს არ აქვს რგოლი. B კოშკს აქვს რგოლი 2. C კოშკს აქვს რგოლი 1.
საბოლოოდ, გადადეთ რგოლი 1 C ლურსმნიდან B ლურსმანზე:
სამი კოშკი, სახელად A, B და C. კოშკ A-ს არ აქვს რგოლი. კოშკ B-ს აქვს რგოლი 2 ძირში და რგოლი 1 კენწეროში. C კოშკს არ აქვს რგოლი.
ეს ამონახსნი საჭიროებს სამ ნაბიჯს და, კიდევ ერთხელ, არაფერია განსაკუთრებული A ლურსმნიდან B ლურსმანზე ორი რგოლის გადატანაში. შეგიძლიათ, ისინი გადადოთ B ლურსმნიდან C ლურსმანზე A ლურსმნის გამოყენებით თავისუფალ ლურსმნად: რგოლი 1 გადადეთ B ლურსმნიდან A ლურსმანზე, შემდეგ რგოლი 2 გადადეთ B ლურსმნიდან C ლურსმანზე და დაასრულეთ რგოლი 1-ის გადატანით A ლურსმნიდან C ლურსმანზე. როგორ ფიქრობთ, 1 და 2 რგოლების გადატანა ნებისმიერი ლურსმნიდან ნებისმიერზე სამ სვლაში შეგიძლიათ? (თქვით „დიახ“)

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