ძირითადი მასალა
კომპიუტერული მეცნიერება
კურსი: კომპიუტერული მეცნიერება > თემა 1
გაკვეთილი 6: რეკურსიული ალგორითმები- რეკურსია
- ფაქტორიალის ფუნქცია
- გამოწვევა: განმეორებითი ფაქტორიალი
- რეკურსიული ფაქტორიალი
- გამოწვევა: რეკურსიული ფაქტორიალი
- რეკურსიული ალგორითმების თვისებები
- რეკურსიის დახმარებით განვსაზღვროთ სიტყვა პალინდრომია თუ არა
- გამოწვევა: არის თუ არა სტრიქონი პალინდრომი?
- რიცხვის ხარისხების გამოთვლა
- გამოწვევა: რეკურსიული ხარისხები
- მრავალჯერადი რეკურსია სერპინსკის სამკუთხედით
- რეკურსიული ფუნქციების ეფექტურობის გაუმჯობესება
- პროექტი: რეკურსიული ხელოვნება
© 2023 Khan Academyგამოყენების პირობებიკონფიდენციალურობის პოლიტიკაშენიშვნა ქუქი-ჩანაწერებზე
რეკურსიული ფაქტორიალი
n-ის დადებითი მნიშვნელობებისთვის დავწეროთ n, !, როგორც ადრე ვქენით, როგორც ნამრავლი n-იდან 1-მდე: n, ! = n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. მაგრამ აღვნიშნოთ, რომ left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 არის left parenthesis, n, minus, 1, right parenthesis, !-ის ჩაწერის ერთ-ერთი გზა და, შესაბამისად, შეგვიძლია, ვთქვათ, რომ n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. ნახეთ, რა ვქენით? n, ! ჩავწერეთ ნამრავლად, რომელთაგან ერთ-ერთი მამრავლი არის left parenthesis, n, minus, 1, right parenthesis, !. ჩვენ ვთქვით, რომ n, !-ის გამოთვლა შეგიძლიათ left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლით და შემდეგ left parenthesis, n, minus, 1, right parenthesis, !-ის შედეგის გამრავლებით n-ზე. n-ის ფაქტორიალის ფუნქციის გამოთვლა შეგიძლიათ ჯერ n, minus, 1-ის გამოთვლით. ვამბობთ, რომ left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლა არის ქვეამოცანა, რომელიც უნდა ამოვხსნათ n!-ის გამოსათვლელად.
მოდით, შევხედოთ მაგალითს: 5!-ის გამოთვლა.
- შეგიძლიათ, 5! გამოთვალოთ, როგორც 5, dot, 4, !.
- ახლა თქვენ უნდა ამოხსნათ 4!-ის გამოთვლის ქვეამოცანა, რომლის გამოთვლაც შეგიძლიათ, როგორც 4, dot, 3!.
- ახლა თქვენ უნდა ამოხსნათ 3!-ის გამოთვლის ქვეამოცანა, რომელიც არის 3, dot, 2, !.
- ახლა 2!, რომელიც არის 2, dot, 1, !.
- ახლა უნდა გამოთვალოთ 1!. შეგიძლიათ, თქვათ, რომ 1! უდრის 1-ს, ვინაიდან ის არის ყველა მთელი რიცხვის ნამრავლი 1-იდან 1-მდე. ან შეგიძლიათ, გამოიყენოთ ფორმულა: 1, !, equals, 1, dot, 0, !. გავაკეთოთ ეს ფორმულის გამოყენებით.
- ჩვენ განვსაზღვრეთ, რომ 0! უდრის 1-ს.
- ახლა შეგიძლიათ, გამოთვალოთ 1, !, equals, 1, dot, 0, !, equals, 1.
- მას შემდეგ, რაც გამოვთვალეთ 1, !, equals, 1, შეგვიძლია, გამოვთვალოთ 2, !, equals, 2, dot, 1, !, equals, 2.
- 2, !, equals, 2-ის გამოთვლის შემდეგ შეგვიძლია, გამოვთვალოთ 3, !, equals, 3, dot, 2, !, equals, 6.
- 3, !, equals, 6-ის გამოთვლის შემდეგ შეგვიძლია, გამოვთვალოთ 4, !, equals, 4, dot, 3, !, equals, 24.
- ბოლოს, 4, !, equals, 24-ის გამოთვლის შემდეგ შეგვიძლია, დავასრულოთ 5, !, equals, 5, dot, 4, !, equals, 120-ით.
ანუ, ახლა ჩვენ გვაქვს n, !-ის გამოთვლაზე ფიქრის კიდევ ერთი გზა ყველა არაუარყოფითი მთელი რიცხვი n-ისთვის:
- თუ n, equals, 0, მაშინ ვაცხადებთ, რომ n, !, equals, 1.
- წინააღმდეგ შემთხვევაში, n უნდა იყოს დადებითი. ამოხსენით left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლის ქვეამოცანა, გაამრავლეთ ეს შედეგი n-ზე და გამოაცხადეთ n, ! ამ ნამრავლის ტოლად.
როდესაც ვითვლით n, !-ს ამ გზით, პირველ შემთხვევას, რომელზე პასუხიც დაუყოვნებლივ ვიცით, ვეძახით ბაზისს და მეორე შემთხვევას, რომელშიც უნდა გამოვთვალოთ იგივე ფუნქცია, მაგრამ სხვა მნიშვნელობაზე, ვეძახით რეკურსიულ შემთხვევას.
ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.