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

  ამოცანის პირობა:

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

1.     ერთ გადატანაზე შეიძლება გადაიტანო მხოლოდ ერთი ფირფიტა

2.     დიდი ზომის ფირფიტა არასდროს არ უნდა აღმოჩნდეს პატარა ფირფიტის ზემოდან

3.     შეგვიძლია გამოვიყენოთ მხოლოდ ერთი დამხმარე ღერძი

შევუდგეთ ამოცანის ამოხსნას:

     მოდით განვიხილოთ პირობა, როდესაც   1 – ი ღერძიდან 3 – მე ღერძზე გადასატანია 3 ფირფიტა, 2 – ე ღერძს ვიყენებთ ფირფიტების დროებით განსათავსებლად. ამოცანას თუ დავუკვირდებით შევამჩნევთ, რომ 3 ფირფიტის გადატანა შეიძლება გამარტივდეს 2 ფირფიტის   გადატანის საშუალებით ანუ  n ფირფიტის გამარტივება ხდება  n-1 ფირფიტის გადანაცვლებით.

შემოვიტანოთ ცვლადები:

disc – ფირფიტების რაოდენობა

first – ღერძი, რომელზეც განთავსებულია ფირფიტები

last – ღერძი, რომელზეც გადაგვაქვს ფირფიტები

temp – დამხმარე რერძი, ფირფიტების დროებიტ განსათავსებლად

ამოცანის გადაწყვეტის ალგორითმი თითოეული რეკურსიული ბიჯისთვის ასეთია:

1. გადავიტანოთ disc – 1 ფირფიტა  first – დან temp– ზე

2. გადავიტანოთ 1 დარჩენილი ფირფიტა first – დან last – ზე

3. გადავითანოთ disc – 1 ფირფიტა temp – დან last – ზე

ეს პროცესი დასრულდება, მაშინ როდესაც გადასატანი იქნება მხოლოდ 1 ფირფიტა, ანუ ფუნქცია მიაღწევს საბაზო ამოცანამდე. ეს ალგორითმი შეიძლება გამოვიყენოთ 64 ფირფიტის ამოცანის გადაწყვეტისთვისაც. :) ახლა კი ამ ალგორითმის რეალიზაცია C++ ზე.

void HanoiTower(int disc, int first, int last, int temp)//ფუნქცია იღებს ზემოთ ჩამოთვლილ პარამეტრებს

{

    if( disc == 1 ) //მოწმდება პირობა: არის თუ არა ფირფიტების რაოდენობა  საბაზო ანუ 1

    {

        cout<<first<<” –> “<<last<<endl;//იბეჭდება, საიდან სად უნდა გადავიტანოთ ფირფიტა. მაგალითად: 1 –> 3

    }

    else//როდესაც ფირფიტების რაოდენობა ერთზე მეტია

    {

        //ფუნქცია იძახებს თავისთავს ალგორითმის წესების შესამამისად

        HanoiTower(disc – 1, first, temp, last);

        HanoiTower(1,first,last,temp);

        HanoiTower(disc – 1, temp, last, first);

    }

    return;

}

თუ ფუნქციას გამოვიძახებთ პარამეტრებით HanoiTower(3,1,3,2) გვექნება შემდეგი შედეგი:

1–>3

1–>2

3–>2

1–>3

2–>1

2–>3

1–>3

მაგალითი 4 რგოლზე :

#include <iostream>
#include "stdafx.h"
using namespace std;
void Hanoi(int n, char src, char mid, char dst) //charshi racaa eg svetebia
{
   if (n==2)
   {
             cout << "moving ring 1 from " <<src<<" to " <<mid<<endl;
             cout << "moving ring 2 from " <<src<<" to " <<dst<<endl;
             cout << "moving ring 1 from " <<mid<<" to " <<dst<<endl;  //ori calis gadatana
   }
   else
   {
       Hanoi(n-1, src, dst, mid);
       cout << "moving ring " <<n<<" from " <<src<<" to " <<dst<<endl;
       Hanoi(n-1, mid, src, dst);
     
   }
}
int _tmain(int argc, _TCHAR* argv[])
{
 Hanoi (4, 'S', 'M', 'D'); // S svetidan gadagvaq D ze Mis daxmarebiT 4cali
return 0;
}