Jump to content
Sign in to follow this  
ToQcHista

რეკურსიული ალგორითმი...

Recommended Posts

        ამ საიტზე რომ დავსერჩე არ იყო ეს თემა და გადავწყვიტე დამეპოსტა.

Recursioლათინურად დაბრუნებას ნიშნავს.რეკურსია წარმოადგენს მეთოდს, რომელსაც ზოგადი ამოცანა დაჰყავს უფრო მცირე ზომის, მარტივი ამოცანების ამოხსნაზე.

რეკურსიული ალგორითმი მუშაობის პროცესში საკუთარ თავს მიმართავს.

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

რეკურსია არის 2 სახის პირდაპირი და ირიბი.

პირდაპირი- არის ჩვეულებრივი როცა ფუნფცია იძახებს თავის თავს.

ირიბი- როცა A ფუნქცია იძახებს B-ს ხოლო B-ე A-ს

ორ სარკეს შორის მოთავსებული საგანი წარმოშობს რეკურსიულ გამოსახულებათა უსასრულო როდენობას.

                                                       ფაქტორიალის გამოთვლა რეკურსიულად

N! =   1,  როცა  N = 1

           N * (N – 1)!, როცა N > 1

 

     რეკურსიის დროს მნიშვნელოვანია ქვეპროგრამიდან (ფუქციიდან) გამოსვლის მომენტის მკაფიო განსაზღვრა, რათა ალგორითმი სასრული იყოს.

 

int factorial( int a)  {

   if (a == 1)    return 1;

       else

       {

        a = a* factorial(a-1);

        return a;

       }

 }

                          

                             ფიბონაჩის მიმდევრობა

ვიპოვოთ ფიბონაჩის მიმდევრობის საწყისი N წევრი. ცნობილია, რომ ამ მიმდევრობის პირეველი ორი წევრი 1-ის ტოლია, ხოლო ყოველი მომდევნო წევრი წინა ორი წევრის ჯამის ტოლია    (1, 1, 2, 3, 5, 8, 13, 21, …).

          ამოცანის რეკურსიული აღწერა:

 

               1 თუ  n = 1 ან n = 2;

Ф(n) = 

             Ф(n – 1) + Ф(n – 2), როცა n > 2                                    

 

 

 

 

 

 

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

using namespace std;

int k,x;

 

int fibon(int n)

{

if(n<=2) return 1;

return fibon(n-1)+fibon(n-2);

}

 

main (){

     cin>>k;

     x=fibon(k);

     cout<<x<<endl;

     system("PAUSE");

     }

 

 

ეს პროგრამა ნათლად ამჟღავნებს რეკურსიის ნაკლოვან მხარეს. K>70 მნიშვნელობებისათვის პროგრამა ძალზე დიდ დროს ანდომებს. საქმე იმაშია, რომ FIB[70]-ის გამოთვლისთვის რეკურსიულმა ფუნქციამ უნდა გამოთვალოს FIB[69] და FIB[68].  მიუხედავად იმისა, რომ FIB[68] ფუნქციას უკვე გამოთვლილი ჰქონდა FIB[69]-ის გამოთვლის დროს, ის ამ მნიშვნელობას თავიდან ითვლის და ასე იქცევა მიმდევრობის ყველა სხვა წევრის მიმართაც. სწორედ ეს გახლავთ რეკურსიის ნელი მუშაობის მიზეზი – ის უამრავჯერ ითვლის ფუნქციის მნიშვნელობას ერთი და იგივე არგუმენტისათვის. მართალია, მასივის შემოღება და მიღებული შედეგების მასში შენახვა მკვეთრად გააუმჯობესებს რეკურსიის მუშაობის სიჩქარესაც.

ამ შემთხვევაში რეკურსიულ ვარიანტზე გაცილებით ეფექტურია იტერაციული ვარიანტი.

 

 

 

მგონი საკმარისია.. 

 

 

 

 

 

 

 

 

 

 

 

  • Upvote 1

Share this post


Link to post
Share on other sites

აბა ნახეთ თუ სასაცილო არის???

 

 

https://www.youtube.com/watch?v=0JHRo-vCTLs&feature=youtu.be

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  

×