ფაქტორიალის ფუნქცია

რეკურსიის ჩვენს პირველ მაგალითში ვნახოთ, როგორ გამოვთვალოთ ფაქტორიალის ფუნქცია. $n$n-ის ფაქტორიალს აღვნიშნავთ შემდეგნაირად: $n!$n, !. ეს არის 1-იდან $n$n-მდე მთელი რიცხვების ნამრავლი. მაგალითად, 5! არის $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5$1, dot, 2, dot, 3, dot, 4, dot, 5, იგივე 120\ (შენიშვნა: როდესაც ფაქტორიალის ფუნქციაზე ვსაუბრობთ, ყველა ძახილის ნიშანი აღნიშნავს ფაქტორიალს და არა — სასვენ ნიშანს).

შეიძლება, ფიქრობთ, რაში გვაინტერესებს ფაქტორიალის ფუნქცია. ის ძალიან გამოსადეგია, როცა ვითვლით, რამდენი განსხვავებული დალაგება არსებობს კონკრეტული ობიექტებისთვის ან ობიექტების რამდენი განსხვავებული კომბინაცია არსებობს. მაგალითად, რამდენი განსხვავებული გზით შეგვიძლია დავალაგოთ $n$n ცალი ნივთი? პირველი ნივთის ასარჩევად გვაქვს $n$n ცალი ვარიანტი. ამ $n$n არჩევანიდან თითოეულისთვის გვრჩება $n-1$n, minus, 1 ვარიანტი მეორე ნივთის ასარჩევად, ასე რომ, პირველი ორი ნივთის ასარჩევად გვაქვს $n \cdot (n-1)$n, dot, left parenthesis, n, minus, 1, right parenthesis ვარიანტი. ახლა, ამ ორი არჩევანიდან თითოეულისთვის გვაქვს $n-2$n, minus, 2 ვარიანტი მესამე ნივთის ასარჩევად, რაც გვაძლევს $n \cdot (n-1) \cdot (n-2)$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis ვარიანტს პირველი სამი ნივთის ასარჩევად. ასე ვაგრძელებთ მანამ, სანამ არ ჩამოვალთ ბოლო ორ ნივთზე და შემდეგ მხოლოდ ერთ ნივთზე. გამოდის, რომ $n$n ცალი ნივთის დასალაგებლად გვაქვს $n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis, \@cdots, 2, dot, 1 გზა. ეს ნამრავლი კი არის $n!$n, ! ($n$n-ის ფაქტორიალი), უბრალოდ 1-იდან დაწყებისა და $n$n-მდე ასვლის ნაცვლად ნამრავლი ჩაწერილია $n$n-იდან დაწყებული და ჩამოდის 1-მდე.

ფაქტორიალის კიდევ ერთი გამოყენება არის ნივთების სიმრავლიდან ნივთების ამორჩევის გზების რაოდენობის დათვლა. მაგალითად, წარმოიდგინეთ, რომ მიდიხართ სამოგზაუროდ და გინდათ, აირჩიოთ, თუ რომელი მაისური წაიღოთ. ვთქვათ, გაქვთ $n$n მაისური, მაგრამ მხოლოდ $k$k მათგანისთვის სამყოფი ადგილი გაქვთ. რამდენი განსხვავებული გზით შეგიძლიათ $k$k ცალი მაისურის ამორჩევა $n$n ცალი მაისურის სიმრავლიდან? პასუხი (რომლის დამტკიცებასაც აქ არ შევეცდებით) არის $n! / (k! \cdot (n-k)!)$n, !, slash, left parenthesis, k, !, dot, left parenthesis, n, minus, k, right parenthesis, !, right parenthesis. ასე რომ, ფაქტორიალის ფუნქცია შეიძლება, საკმაოდ გამოსადეგი იყოს. შეგიძლიათ, უფრო ღრმად ისწავლოთ გადანაცვლებები (იგივე პერმუტაციები) და კომბინაციები, მაგრამ მათი გააზრება არ გჭირდებათ ფაქტორიალის ფუნქციის ალგორითმის იმპლემენტაციისათვის.

ფაქტორიალის ფუნქცია განსაზღვრულია ყველა დადებითი მთელი რიცხვისათვის 0-თან ერთად. 0! რა მნიშვნელობის უნდა იყოს? ეს არის 1-ზე მეტი ან ტოლი და 0-ზე ნაკლები ან ტოლი ყველა მთელი რიცხვის ნამრავლი. მაგრამ ასეთი მთელი რიცხვები არ არსებობს. ასე რომ, 0!-ს განვსაზღვრავთ გამრავლების იგივეობის ტოლად, რაც არის 1. (განსაზღვრა 0! = 1 კარგად ჯდება $n$n ცალი ნივთიდან $k$k ცალი ნივთის ამორჩევის ფორმულაში. წარმოიდგინეთ, რომ გვინდა, გავიგოთ, რამდენნაირად არის შესაძლებელი $n$n ცალი ნივთიდან $n$n ცალი ნივთის ამორჩევა. ეს ადვილია, რადგან მხოლოდ ერთი გზა გვაქვს: ვირჩევთ ყველა $n$n ნივთს. ასე რომ, ახლა ვიცით, რომ ჩვენი ფორმულის გამოყენებით $n! / (n! \cdot (n-n)!)$n, !, slash, left parenthesis, n, !, dot, left parenthesis, n, minus, n, right parenthesis, !, right parenthesis უნდა უდრიდეს 1-ს. მაგრამ $(n-n)!$left parenthesis, n, minus, n, right parenthesis, ! არის 0!, ასე რომ, ახლა ვიცით, რომ $n! / (n! \cdot 0!)$n, !, slash, left parenthesis, n, !, dot, 0, !, right parenthesis უნდა უდრიდეს 1. თუ ამ $n!$n, !-ს შევკვეცავთ მნიშვნელსა და მრიცხველში, ვხედავთ, რომ $1/(0!)$1, slash, left parenthesis, 0, !, right parenthesis უნდა უდრიდეს 1-ს და ეს ასეც არის, რადგან 0! უდრის 1-ს.)

ასე რომ, $n!$n, !-ის წარმოდგენის გზა გვაქვს. ის უდრის 1-ს, როცა $n = 0$n, equals, 0 და ის უდრის $1 \cdot 2 \cdots (n-1) \cdot n$1, dot, 2, \@cdots, left parenthesis, n, minus, 1, right parenthesis, dot, n-ს, როცა $n$n არის დადებითი.

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