Jump to content
Sign in to follow this  
GHOST_FATHER

რეკურსიის ძალა. ჰანოის კოშკები.

Recommended Posts

მოგესალმებით. დიდი ხნის პაუზის შემდეგ დავბრუნდი და მინდა შემოგთავაზოთ ერთი საინტერესო პოსტი რეკურსიის შესახებ.  მოდით ჯერ ზოგადად რეკურსიის(რეკურსიული ფუნქციის) შესახებ ვთქვათ ორიოდე სიტყვა:  რეკურსიული ფუნქცია ეწოდება ისეთ ფუნქციას რომელიც იძახებს საკუთარ თავს, მისი მთავარი იარაღია ამოცანის მარტივ ნაწილებად დაშლა ანუ დეკომპოზიცია. რეკურსია მოქმედებს პრინციპით “დაყავი და იბატონე”. რეკურსიული ფუნქციის დასრულება ხდება ამოცანის საბაზო ანუ ყველაზე მარტივ დონემდე დაყვანით. ამოცანის რეკურსიულად გადაწყვეტა მოითხოვს გაცილებით დიდ რესურსებს კომპიუტერისგან, ვიდრე ამას საჭიროებს ტრადიციული(იტერაციული) მიდგომა, თუმცა უნდა აღინიშნოს რომ ზოგიერთი ამოცანის გადაწყვეტისას რეკურსიული მიდგომა გაცილებით უკეთესია , ვიდრე იტერაციული. ასეთი ამოცანების რიგს მიეკუთვნება ამოცანა ჰანოის კოშკების შესახებ, რომლის იტერაციული გადაწყვეტა ძალიან დიდ სირთულეს წარმოადგენს, როდესაც რეკურსიით ყველაფერი მარტივად და გასაგებად წყდება. 

Tower_of_Hanoi.thumb.jpeg.bcba30c343c88f

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

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

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

 

 

ბერები ცდილობდნენ ეს პროცესი შეესრულებინათ 64 ფირფიტისთვის :) ლეგენდა ასევე ამბობს, რომ როდესაც ისინი ამ პროცესს დაასრულებენ ( ამ ყველაფერს ისინი კომპიუტერის გარეშე აკეთებენ ) ქვეყნიერების დასასრული დადგება :) ასე რომ მაინც და მაიც ნუ დავეხმარებით მათ:)

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

     მოდით განვიხილოთ პირობა, როდესაც   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

 

ავტორი:გიორგი ლობჟანიძე

Edited by GHOST_FATHER
  • Upvote 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×