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

კურსი: კომპიუტერული მეცნიერება > თემა 1

გაკვეთილი 7: ჰანოის კოშკები

ჰანოის კოშკები, გაგრძელება

როდესაც ჰანოის კოშკი ამოხსენით სამ რგოლზე, დაგჭირდათ, რომ გამოგეთავისუფლებინათ ძირში მყოფი რგოლი, რგოლი 3, რათა შეგძლებოდათ მისი გადაადგილება A ლურსმნიდან B ლურსმანზე. რგოლი 3-ის გამოთავისუფლებისთვის დაგჭირდათ რგოლი 1-ისა და რგოლი 2-ის გადაადგილება A ლურსმნიდან თავისუფალ ლურსმანზე, რომელიც არის ლურსმანი C:

ერთი წუთით — როგორც ჩანს, ორი რგოლი გადაადგილდა ერთ სვლაში, რაც პირველ წესს არღვევს. მაგრამ ისინი ერთ სვლაში არ გადაადგილებულან. ჩვენ შევთანხმდით, რომ რგოლი 1-ისა და რგოლი 2-ის გადატანა შეგვიძლია ნებისმიერი ლურსმნიდან ნებისმიერ ლურსმანზე სამი სვლის გამოყენებით. ზემოთ მოცემული სიტუაცია წარმოადგენს იმას, რაც სამი სვლის შემდეგ გაქვთ (რგოლი 1 გადადეთ A ლურსმნიდან B ლურსმანზე; რგოლი 2 გადადეთ A ლურსმნიდან C ლურსმანზე; რგოლი 1 გადადეთ B ლურსმნიდან C ლურსმანზე).

მეტიც, 1 და 2 რგოლების A-დან C ლურსმანზე გადაადგილებით თქვენ ქვეამოცანა ამოხსენით რეკურსიულად: გადააადგილეთ რგოლები 1-დან

n - 1

-მდე (გახსოვდეთ, რომ

n = 3

) A ლურსმნიდან C ლურსმანზე. როგორც კი ამ ქვეამოცანას ამოხსნით, შეგიძლიათ, რგოლი 3 გადადოთ A ლურსმნიდან B ლურსმანზე:

ახლა დასასრულებლად საჭიროა, რომ რეკურსიულად ამოხსნათ შემდეგი ქვეამოცანა: გადადეთ რგოლები 1-დან

n - 1

-მდე C ლურსმნიდან B ლურსმანზე. კიდევ ერთხელ, ჩვენ შევთანხმდით, რომ ამის გაკეთება შეგვიძლია სამ სვლაში (გადადეთ რგოლი 1 C ლურსმნიდან A ლურსმანზე; გადადეთ რგოლი 2 C ლურსმნიდან B ლურსმანზე; გადადეთ რგოლი 1 A ლურსმნიდან B ლურსმანზე). ამით დაასრულებთ:

და — თქვენ იცოდით, რომ ამ შეკითხვას დაგისვამდით — ის ლურსმნები, რომლებზეც რგოლებს გადააადგილებდით, რამით განსაკუთრებული არიან? ნებისმიერი ლურსმნიდან ნებისმიერზე შეგეძლოთ მათი გადაადგილება. მაგალითად, B ლურსმნიდან C ლურსმანზე:

რეკურსიულად ამოხსენით 1 და 2 რგოლების B-დან თავისუფალ A ლურსმანზე გადატანის ქვეამოცანა (რგოლი 1 გადადეთ B ლურსმნიდან C ლურსმანზე; რგოლი 2 გადადეთ B ლურსმნიდან A ლურსმანზე; რგოლი 1 გადადეთ C ლურსმნიდან A ლურსმანზე).
ახლა, როცა რგოლი 3 გამოთავისუფლებულია B ლურსმანზე, გადადეთ ის C ლურსმანზე.
რეკურსიულად ამოხსენით 1 და 2 რგოლების A ლურსმნიდან C ლურსმანზე გადატანის ქვეამოცანა (რგოლი 1 გადადეთ A ლურსმნიდან B ლურსმანზე; რგოლი 2 გადადეთ A ლურსმნიდან C ლურსმანზე; რგოლი 1 გადადეთ B ლურსმნიდან C ლურსმანზე).

მნიშვნელობა არა აქვს როგორ დაჭრით მას, 1-დან 3-მდე რგოლები შეგიძლიათ, გადაიტანოთ ნებისმიერი ლურსმნიდან ნებისმიერ ლურსმანზე, რგოლების 7-ჯერ გადადებით. აღვნიშნოთ, რომ რგოლებს გადააადგილებთ 3-ჯერ თითოეულ ჯერზე, როდესაც რეკურსიულად ხსნით 1 და 2 რგოლების გადატანის ქვეამოცანას (ამას ორჯერ აკეთებთ), პლუს რგოლი 3-ის გადატანის ერთი სვლა.

მაშინ რა ხდება, როცა

n = 4

? ვინაიდან თქვენ შეგიძლიათ, რეკურსიულად ამოხსნათ 1-დან 3-მდე რგოლების ნებისმიერი ლურსმნიდან ნებისმიერ ლურსმანზე გადატანის ქვეამოცანა, თქვენ აგრეთვე შეგიძლიათ ამოხსნათ ამოცანა

n = 4

-ისთვის:

რეკურსიულად ამოხსენით 1-იდან 3-მდე რგოლების A ლურსმნიდან C ლურსმანზე გადატანის ქვეამოცანა, რგოლები გადაიტანეთ 7-ჯერ.
რგოლი 4 გადაიტანეთ A ლურსმნიდან B ლურსმანზე.
რეკურსიულად ამოხსენით 1-იდან 3 რგოლების C ლურსმნიდან B ლურსმანზე გადატანის ქვეამოაცანა, რგოლები გადაიტანეთ 7-ჯერ.

ამ ამოხსნას გადააქვს რგოლები 15-ჯერ (7 + 1 + 7) და, დიახ, შეგიძლიათ, 1-იდან 4-მდე რგოლები გადადოთ ნებისმიერი ლურსმნიდან ნებისმიერ ლურსმანზე.

ამ დროისათვის თქვენ შეიძლება, ორი კანონზომიერება დაიჭირეთ. პირველი, ჰანოის კოშკის ამოცანის ამოხსნა რეკურსიულად შეგიძლიათ. თუ If

n = 1

, უბრალოდ გადადეთ რგოლი 1. წინააღმდეგ შემთხვევაში, როდესაც

n \geq 2

, ამოხსენით ამოცანა სამ ნაბიჯში:

რეკურსიულად ამოხსენით 1-იდან $n - 1$ ‍-მდე რგოლების საწყისი ლურსმნიდან თავისუფალ ლურსმანზე გადატანის ქვეამოცანა.
გადადეთ რგოლი $n$ ‍ საწყისი ლურსმნიდან სამიზნე ლურსმანზე.
რეკურსიულად ამოხსენით 1-იდან $n - 1$ ‍-მდე რგოლების თავისუფალი ლურსმნიდან სამიზნე ლურსმანზე გადატანის ქვეამოცანა.

მეორე,

n

რგოლისთვის ამოცანის ამოხსნა საჭიროებს

2^{n} - 1

სვლას. ჩვენ ვნახეთ, რომ ეს ჭეშმარიტია შემდეგ შემთხვევებში:

$n = 1$ ‍ ( $2^{1} - 1 = 1$ ‍, მხოლოდ ერთი სვლა არის საჭირო)
$n = 2$ ‍ ( $2^{2} - 1 = 3$ ‍, სამი მოძრაობა არის საჭირო)
$n = 3$ ‍ ( $2^{3} - 1 = 7$ ‍, შვიდი სვლა არის საჭირო)
$n = 4$ ‍ ( $2^{4} - 1 = 15$ ‍, 15 სვლა არის საჭირო).

თუ შეგიძლიათ, ამოცანა ამოხსნათ

n - 1

რგოლისთვის

2^{n - 1} - 1

სვლაში, მაშინ შეგიძლიათ,

n

რგოლისთვის ამოცანა ამოხსნათ

2^{n} - 1

სვლაში. თქვენ გჭირდებათ:

$2^{n - 1} - 1$ ‍ სვლა 1-დან $n - 1$ ‍ მდე რგოლების გადატანის ქვეამოცანის ამოსახსნელად.
$1$ ‍ სვლა $n$ ‍ რგოლის გადასატანად
$2^{n - 1} - 1$ ‍ სვლა (ისევ) 1-დან $n - 1$ ‍-მდე რგოლების გადატანის ქვეამოცანის ამოსახსნელად

თუ დააჯამებთ სვლებს, მიიღებთ

2^{n} - 1

-ს.

დავუბრუნდეთ ბერებს. ისინი იყენებენ

n = 64

რგოლს და, შესაბამისად, მათ დასჭირდებათ

2^{64} - 1

სვლა. ეს ბერები სწრაფები და ძლიერები არიან. მათ შეუძლიათ თითო რგოლი ერთ წამში გადაიტანონ, დღისითაც და ღამითაც — განუწყვეტლივ.

რამდენად დიდი დროა

2^{64} - 1

წამი? მიახლოებითი შეფასების გამოყენებით, 365.25 დღე წელიწადში, გამოგვდის 584,542,046,090.6263 წელი. ეს არის 584+ მილიარდი წელი. მზე კიდევ იარსებებს დაახლოებით 5-იდან 7 მილიარდ წლამდე, სანამ ზეახალ ვარსკვლავად გარდაიქმნება. ასე რომ, დიახ, მსოფლიო დამთავრდება, მაგრამ განურჩევლად იმისა, თუ რამდენად ჯიუტები იქნებიან ბერები, ეს გაცილებით უფრო ადრე მოხდება, სანამ ისინი 64-ივე რგოლს გადადებენ B ლურსმანზე.

გაინტერესებთ, სამყაროს დასასრულის პროგნოზირების გარდა კიდევ როგორ შეგვიძლია ამ ალგორითმის გამოყენება? ვიკიპედიაზე ჩამოთვლილია რამდენიმე საინტერესო გამოყენება.

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

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.