Հիմնական նյութ
Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 1
Դաս 6: Ռեկուրենտ ալգորիթմներ- Ռեկուրսիա
- Ֆակտորիալ ֆունկցիան
- Մարտահրավեր․ կրկնողական ֆակտորիալ
- Ռեկուրենտ ֆակտորիալ
- Մարտահրավեր․ ռեկուրենտ ֆակտորիալ
- Ռեկուրենտ ալգորիթմների հատկությունները
- Օգտագործելով ռեկուրսիա՝ գտիր այն բառերը, որոնք պալինդրոմ են
- Մարտահրավեր․ պալինդրոմ տողայիններ
- Հաշվել թվի աստիճանները
- Մարտահրավեր․ ռեկուրսիվ աստիճաններ
- Սիերպինսկիի եռանկյունը
- Նախագիծ․ ռեկուրենտ արվեստ
© 2024 Khan AcademyՕգտագործման պայմաններԳաղտնիության քաղաքականությունՔուքի (Cookie) ծանուցում
Ռեկուրենտ ալգորիթմների հատկությունները
Ահա ռեկուրենտ ալգորիթմների հիմնական միտքը․
Խնդիրը լուծելու համար լուծիր ենթախնդիր, որը նույն խնդրի ավելի փոքր տարբերակն է, և ենթախնդրի լուծումն օգտագործելով՝ լուծիր խնդիրը։
Ռեկուրենտ ալգորիթմը կաշխատի այն դեպքում, երբ փոքր ենթախնդիրներն ամենավերջում հասնեն առաջնային դեպքի։ -ը հաշվելիս ենթախնդիրները շարունակ փոքրանում են՝ վերջում հասնելով դեպքին։ Դու պետք է վստահ լինես, որ վերջում հասնելու ես առաջնային դեպքին։
Օրինակ՝ ի՞նչ կլինի, եթե մենք փորձենք ռեկուրենտ մեթոդով հաշվել բացասական թվի ֆակտորիալը։ -ը հաշվելու համար նախ և առաջ պետք է հաշվես -ը, որպեսզի գտնես -ը։ Բայց -ը հաշվելու համար նախ և առաջ պետք է հաշվես -ը, որպեսզի գտնես -ը։ Հետո պետք է հաշվես -ը և այսպես շարունակ։ Այո, թվերը փոքրանում են, բայց դրանք նաև հեռանում են առաջնային դեպքից, այսինքն՝ հաշվելուց։ Այսպես դու երբեք պատասխան չես ստանա։
Նույնիսկ եթե վստահ ես, որ -ի արժեքը բացասական չէ, դու ոչ մի պատասխան էլ չես ստանա, եթե ենթախնդիրներն անընդհատ չփոքրանան։ Ահա օրինակ։ Վերցնենք հավասարումը և երկու կողմը բաժանենք -ի՝ ստանալով ։ Արի ստեղծենք նոր փոփոխական՝ և այն հավասարեցնենք -ին։ Քանի որ բանաձևը գործում է բոլոր դրական թվերի համար, արի գրենք -ի փոխարեն՝ ։ Քանի որ , կստանանք ։ Նորից հետ փոխելով ու նկատի ունենալով, որ ՝ ստանում ենք ։ Այս բանաձևով կարող ենք երթադրել, որ կկարողանանք հաշվել -ը՝ սկզբում գտնելով -ը և այն բաժանելով -ի։ Բայց -ը հաշվելու համար պետք է գտնես -ը, հետո՝ -ը, և այսպես շարունակ։ Դու երբեք չես հասնի 0\ դեպքին։ Ինչո՞ւ։ Որովհետև ամեն ռեկուրենտ ենթախնդիրը հաշվում է նախորդից ավելի մեծ թվի արժեքը, ոչ թե ավելի փոքր։ Եթե -ը դրական է, դու այդպես երբեք չես հասնի առաջնային դեպքին՝ 0-ին։
Ռեկուրսիայի այս միտքը կարող ենք ներկայացնել երկու կանոնի տեսքով․
- Ամեն հաջորդ ռեկուրենտ կանչը պետք է լինի ավելի փոքր արժեքի համար, այսինքն՝ լինի ավելի փոքր ենթախնդիր։
- Ռեկուրենտ կանչերն ինչ-որ պահի պետք է հասնեն առաջնային դեպքի, որը լուծվում է առանց ռեկուրսիայի։
Նույնը պատկերացնենք ռուսական տիկնիկի՝ մատրյոշկայի օրինակով։ Չնայած դրանք որևէ ալգորիթմի հետ կապ չունեն, բայց յուրաքանչյուր տիկնիկ ծածկում է իրենից ավելի փոքր տիկնիկին (ճիշտ ռեկուրենտ ալգորիթմի նման) այնքան, մինչև ամենափոքրը չի ծածկում ոչ մի տիկնիկ (առաջնային դեպքի պես)։
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։
Ուզո՞ւմ ես միանալ խոսակցությանը։
Առայժմ հրապարակումներ չկան։