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

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

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

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

თემა 1: გაკვეთილი 6

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

რიცხვის ხარისხების გამოთვლა

მიუხედავად იმისა, რომ JavaScript-ს აქვს ჩაშენებული pow ფუნქცია, რომელიც ითვლის რიცხვის ხარისხებს, შეგიძლიათ, ანალოგიური ფუნქცია დაწეროთ რეკურსიულად და ის შეიძლება, ძალიან ეფექტური იყოს. ერთადერთი დაბრკოლება არის ის, რომ მაჩვენებელი უნდა იყოს მთელი რიცხვი.
ვთქვათ, გსურთ, გამოთვალოთ x, start superscript, n, end superscript, სადაც x არის ნებისმიერი ნამდვილი რიცხვი და n არის ნებისმიერი მთელი რიცხვი. მარტივია, თუ n არის 0, ვინაიდან x, start superscript, 0, end superscript, equals, 1 იმის მიუხედავად, თუ რა არის x. ეს კარგი ბაზისია.
ახლა მოდით, ვნახოთ, რა ხდება, როცა n არის დადებითი. დავიწყოთ იმის გახსენებით, რომ როდესაც x-ის ხარისხებს ამრავლებთ, ხარისხის მაჩვენებლები იკრიბება: x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript ნებისმიერი ფუძე x-ისთვის და ნებისმიერი a და b მაჩვენებლებისთვის. ასე რომ, თუ n არის დადებითი და ლუწი, მაშინ x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. თუ გსურთ, გამოთვალოთ y, equals, x, start superscript, n, slash, 2, end superscript რეკურსიულად, მაშინ შეგიძლიათ, გამოთვალოთ x, start superscript, n, end superscript როგორც y, dot, y. მაშინ რა ხდება, როცა n არის დადებითი და კენტი? მაშინ x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x და n, minus, 1 არის ან 0 ან დადებითი და ლუწი. ჩვენ ახლა ვნახეთ, როგორ გამოვთვალოთ x-ის ხარისხები, როცა მაჩვენებელი არის 0 ან დადებითი და ლუწი. ასე რომ, შეგიძლიათ, x, start superscript, n, minus, 1, end superscript გამოთვალოთ რეკურსიულად და შემდეგ ეს შედეგი გამოიყენოთ x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x-ის გამოსათვლელად.
მაშინ რა ხდება, როცა n არის უარყოფითი? მაშინ x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript და მაჩვენებელი minus, n არის დადებითი, რადგან ის არის უარყოფითი რიცხვის უარყოფა. ასე რომ, შეგიძლიათ, გამოთვალოთ x, start superscript, minus, n, end superscript რეკურსიულად და აიღოთ მისი შებრუნებული.
ამ დაკვირვებების გაერთიანებით ვიღებთ შემდეგ რეკურსიულ ალგორითმს x, start superscript, n, end superscript-ის გამოსათვლელად:
  • ბაზისი არის, როცა n, equals, 0 და x, start superscript, 0, end superscript, equals, 1.
  • თუ n არის დადებითი და ლუწი, რეკურსიულად გამოთვალეთ y, equals, x, start superscript, n, slash, 2, end superscript და შემდეგ x, start superscript, n, end superscript, equals, y, dot, y. აღვნიშნოთ, რომ შეგიძლიათ, ამ შემთხვევაში მხოლოდ ერთი რეკურსიული გამოძახება იმყოფინოთ, x, start superscript, n, slash, 2, end superscript გამოთვლა მხოლოდ ერთხელ და შემდეგ ამ რეკურსიული გამოძახების შედეგს ამრავლებთ საკუთარ თავზე.
  • თუ n არის დადებითი და კენტი, რეკურსიულად გამოთვალეთ x, start superscript, n, minus, 1, end superscript, რათა მაჩვენებელი იყოს ან 0 ან დადებითი და ლუწი. მაშინ, x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
  • თუ n არის უარყოფითი, რეკურსიულად გამოთვალეთ x, start superscript, minus, n, end superscript, რათა მაჩვენებელი გახდეს დადებითი. შემდეგ, x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript.

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.