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

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

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

კომპიუტერული მეცნიერება

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

გაკვეთილი 6: რეკურსიული ალგორითმები
პროგრამირება
კომპიუტერული მეცნიერება
ალგორითმები
რეკურსიული ალგორითმები
© 2023 Khan Academyგამოყენების პირობებიკონფიდენციალურობის პოლიტიკაშენიშვნა ქუქი-ჩანაწერებზე

რეკურსიული ფაქტორიალი

Google–ის საკლასო ოთახი
n-ის დადებითი მნიშვნელობებისთვის დავწეროთ n!, როგორც ადრე ვქენით, როგორც ნამრავლი n-იდან 1-მდე: n! = n⋅(n−1)⋯2⋅1. მაგრამ აღვნიშნოთ, რომ (n−1)⋯2⋅1 არის (n−1)!-ის ჩაწერის ერთ-ერთი გზა და, შესაბამისად, შეგვიძლია, ვთქვათ, რომ n!=n⋅(n−1)!. ნახეთ, რა ვქენით? n! ჩავწერეთ ნამრავლად, რომელთაგან ერთ-ერთი მამრავლი არის (n−1)!. ჩვენ ვთქვით, რომ n!-ის გამოთვლა შეგიძლიათ (n−1)!-ის გამოთვლით და შემდეგ (n−1)!-ის შედეგის გამრავლებით n-ზე. n-ის ფაქტორიალის ფუნქციის გამოთვლა შეგიძლიათ ჯერ n−1-ის გამოთვლით. ვამბობთ, რომ (n−1)!-ის გამოთვლა არის ქვეამოცანა, რომელიც უნდა ამოვხსნათ n!-ის გამოსათვლელად.
მოდით, შევხედოთ მაგალითს: 5!-ის გამოთვლა.
  • შეგიძლიათ, 5! გამოთვალოთ, როგორც 5⋅4!.
  • ახლა თქვენ უნდა ამოხსნათ 4!-ის გამოთვლის ქვეამოცანა, რომლის გამოთვლაც შეგიძლიათ, როგორც 4⋅3!.
  • ახლა თქვენ უნდა ამოხსნათ 3!-ის გამოთვლის ქვეამოცანა, რომელიც არის 3⋅2!.
  • ახლა 2!, რომელიც არის 2⋅1!.
  • ახლა უნდა გამოთვალოთ 1!. შეგიძლიათ, თქვათ, რომ 1! უდრის 1-ს, ვინაიდან ის არის ყველა მთელი რიცხვის ნამრავლი 1-იდან 1-მდე. ან შეგიძლიათ, გამოიყენოთ ფორმულა: 1!=1⋅0!. გავაკეთოთ ეს ფორმულის გამოყენებით.
  • ჩვენ განვსაზღვრეთ, რომ 0! უდრის 1-ს.
  • ახლა შეგიძლიათ, გამოთვალოთ 1!=1⋅0!=1.
  • მას შემდეგ, რაც გამოვთვალეთ 1!=1, შეგვიძლია, გამოვთვალოთ 2!=2⋅1!=2.
  • 2!=2-ის გამოთვლის შემდეგ შეგვიძლია, გამოვთვალოთ 3!=3⋅2!=6.
  • 3!=6-ის გამოთვლის შემდეგ შეგვიძლია, გამოვთვალოთ 4!=4⋅3!=24.
  • ბოლოს, 4!=24-ის გამოთვლის შემდეგ შეგვიძლია, დავასრულოთ 5!=5⋅4!=120-ით.
ანუ, ახლა ჩვენ გვაქვს n!-ის გამოთვლაზე ფიქრის კიდევ ერთი გზა ყველა არაუარყოფითი მთელი რიცხვი n-ისთვის:
  • თუ n=0, მაშინ ვაცხადებთ, რომ n!=1.
  • წინააღმდეგ შემთხვევაში, n უნდა იყოს დადებითი. ამოხსენით (n−1)!-ის გამოთვლის ქვეამოცანა, გაამრავლეთ ეს შედეგი n-ზე და გამოაცხადეთ n! ამ ნამრავლის ტოლად.
როდესაც ვითვლით n!-ს ამ გზით, პირველ შემთხვევას, რომელზე პასუხიც დაუყოვნებლივ ვიცით, ვეძახით ბაზისს და მეორე შემთხვევას, რომელშიც უნდა გამოვთვალოთ იგივე ფუნქცია, მაგრამ სხვა მნიშვნელობაზე, ვეძახით რეკურსიულ შემთხვევას.
ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.

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

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