Ֆակտորիալ ֆունկցիան

Ռեկուրսիայի մեր առաջին օրինակի համար արի նայենք, թե ինչպես կարող ենք հաշվել ֆակտորիալի ֆունկցիան։ $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 \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, ! է ($n$n ֆակտորիալ), բայց արտադրյալը գրվում է նվազման կարգով՝ $n$n-ից մինչև 1, ոչ թե 1-ից մինչև $n$n, որոնք նույն բանն են։

Ֆակտորիալն օգտագործելու մեկ այլ օրինակ է ինչ-որ հավաքածուից իրեր ընտրելու եղանակներ հաշվելը։ Օրինակ՝ պատկերացրու, թե գնում ես հանգստի և ուզում ես ընտրել, թե որ շապիկներն ես հետդ վերցնելու։ Ընդունենք՝ դու ունես $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 սահմանելը շատ է օգնում $k$k իրը $n$n իրերի միջից ընտրելու ժամանակ։ Պատկերացրու՝ մենք ուզում ենք իմանալ, թե քանի տարբեր եղանակով կարող ենք ընտրել $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-ի կողմից։