Një prezantim me temën "Algoritmet rekursive" u krijua për të përgatitur studentët për Provimin e Unifikuar të Shtetit në shkencat kompjuterike dhe TIK. Puna shqyrton përkufizimin e rekursionit dhe jep shembuj të objekteve grafike të përcaktuara në mënyrë rekursive. Prezantimi përmban metoda për zgjidhjen e detyrës nr. 11 nga draft versioni demo i Provimit të Unifikuar të Shtetit - 2015 në shkenca kompjuterike. Metoda e parë përfshin ndërtimin e një peme thirrjeje, metoda e dytë zgjidh problemin duke përdorur metodën e zëvendësimit. Janë marrë në konsideratë 4 shembuj të zgjidhjes së detyrave duke përdorur të dyja metodat. Prezantimi i mëposhtëm përmban 25 ushtrime për stërvitje me përgjigje nga faqja e internetit e Konstantin Polyakov.

Shkarko:

Pamja paraprake:

Për të përdorur pamjet paraprake të prezantimeve, krijoni një llogari Google dhe identifikohuni në të: https://accounts.google.com

Titrat e rrëshqitjes:

Detyra nr 11 Provimi i Unifikuar i Shtetit (niveli bazë, koha - 5 minuta) Algoritme rekursive. Autor – Korotun O.V., mësues i informatikës, Institucioni arsimor komunal “Shkolla e Mesme Nr. 71”

Çfarë duhet të dini: Rekursioni është në përkufizimin, përshkrimin, përshkrimin e një objekti ose procesi brenda këtij objekti ose procesi, domethënë një situatë kur një objekt është pjesë e vetvetes. Stema e Federatës Ruse është një objekt grafik i përcaktuar në mënyrë rekursive: në putrën e djathtë të shqiponjës me dy koka të përshkruar në të, është mbërthyer një skeptër, i cili kurorëzohet me një kopje më të vogël të stemës. Duke qenë se në këtë stemë ka edhe një skeptër në putrën e djathtë të shqiponjës, fitohet një rekursion i pafund. Stema rekursive e Rusisë

Në programim, rekursioni është thirrja e një funksioni nga vetvetja, drejtpërdrejt ose përmes funksioneve të tjera, për shembull, funksioni A thërret funksionin B, dhe funksioni B thërret funksionin A. Numri i thirrjeve të ndërlidhura në një funksion ose procedurë quhet thellësia e rekursionit. shembull i rekursionit: Nëse keni një njollë yndyre në veshjen tuaj, mos u shqetësoni. Njollat ​​e vajit hiqen me solucion alkali.

Shembull caktimi: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajn(n); nëse n

Shembull caktimi: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajnë (n) ; nëse n

Shembull caktimi: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajn(n); nëse n Rrëshqitja 9

Shembull caktimi: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajn(n); nëse n Rrëshqitja 10

Shembull caktimi: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajn(n); nëse n Rrëshqitja 11

15 Shembulli nr. 2: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajn(n); nëse n

Shembulli nr. 2: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajn(n); nëse n Rrëshqitja 13

Shembulli nr. 3: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); fillo të shkruajnë("*"); nëse n > 0 atëherë filloni F(n-2); F(n div 2) fund fundi ; Sa yje do të shtypen në ekran kur telefononi F(7)? 7 5 3 2 3 1 1 1 1 Në këtë shembull, simboli * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 shfaqet në ekran në vend të vlerave të parametri n.

Shembulli nr. 3: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0 atëherë filloni F(n-2); F(n div 2) fund fundi ; Sa yje do të shtypen në ekran kur telefononi F(7)? * Duke numëruar numrin e "yjeve", marrim 21 Në këtë shembull, nuk janë vlerat e parametrit n që shfaqen në ekran, por simboli * * * * * * * * * * * * * * * * * * * * * * *

Shembulli nr. 3: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0 atëherë filloni F(n-2); F(n div 2) fund fundi ; Sa yje do të shtypen në ekran kur telefononi F(7)? Le ta zgjidhim problemin pa një pemë. Le të jetë S(n) numri i "yjeve" që do të printohen kur telefononi F(n). Pastaj 1+S(n-2)+ S(n div 2), n>0 1 , n Duhet të dimë S(7). S(7)= 1 +S(5)+ S(3) S(5)= 1 +S(3)+S(2) S(3)= 1 +S(1)+S(1) S( 2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S(1)= 1+ S(-1)+S(0)=1+ 1+1=3 Anasjelltas: S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+ 13+ 7= 21 S(n)=

Shembulli nr. 4: procedura F(n: numër i plotë); filloni nëse n Slide 18

Shembulli nr. 4: procedura F(n: numër i plotë); filloni nëse n Slide 19

Shembulli nr. 4: procedura F(n: numër i plotë); fillojnë nëse n

Shembulli nr. 4: procedura F(n: numër i plotë); fillojnë nëse n

Detyrat e trajnimit

Problemi 1: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0 atëherë filloni F(n-2); F(n div 2); F(n div 2); fund fundi; Sa yje do të shtypen në ekran kur telefononi F(5)? Përgjigje: 34

Problemi 2: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0 atëherë filloni F(n-2); F(n-2); F(n div 2); fundi fundi; Sa yje do të shtypen në ekran kur telefononi F(6)? Përgjigje: 58

Problemi 3: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0 atëherë filloni F(n-3); F(n div 2); fundi fundi; Sa yje do të shtypen në ekran kur telefononi F(7)? Përgjigje: 15

Problemi 4: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0 atëherë filloni F(n-3); F(n-2); F(n div 2); fundi fundi; Sa yje do të shtypen në ekran kur telefononi F(7)? Përgjigje: 55

Problemi 5: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0 atëherë filloni F(n-3); F(n-2); F(n div 2); F(n div 2); fund fundi; Sa yje do të shtypen në ekran kur telefononi F(6)? Përgjigje: 97

Problemi 6: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0, atëherë filloni të shkruani n("*"); F(n-2); F(n div 2); fund fundi; Sa yje do të shtypen në ekran kur telefononi F(7)? Përgjigje: 31

Problemi 7: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0, atëherë filloni të shkruani n("*"); F(n-2); F(n div 2); F(n div 2); fund fundi; Sa yje do të shtypen në ekran kur telefononi F(7)? Përgjigje: 81

Problemi 8: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni të shkruani ("*"); nëse n > 0, atëherë filloni të shkruani n("*"); F(n-2); F(n-2); F(n div 2); fund fundi; Sa yje do të shtypen në ekran kur telefononi F(6)? Përgjigje: 77

Problemi 9: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni nëse n > 0 atëherë filloni F(n-2); F(n-1); F(n-1); fundi; writeln("*"); fundi ; Sa yje do të shtypen në ekran kur telefononi F(5)? Përgjigje: 148

Problemi 10: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni nëse n > 0, atëherë filloni të shkruani ("*"); F(n-2); F(n-1); F(n-1); fundi; writeln ("*"); fundi; Sa yje do të shtypen në ekran kur telefononi F(5)? Përgjigje: 197

Problemi 11: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni nëse n > 1 atëherë filloni F(n-2); F(n-1); F(n div 2); fundi; writeln("*"); fundi ; Sa yje do të shtypen në ekran kur telefononi F(7)? Përgjigje: 88

Problemi 12: Jepet një algoritëm rekurziv: procedura F(n: numër i plotë); filloni nëse n > 2, atëherë filloni të shkruani ("*"); F(n-2); F(n-1); F(n div 2); fundi ; writeln("*"); fundi; Sa yje do të shtypen në ekran kur telefononi F(6)? Përgjigje: 33

Problemi 13: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 14: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 15: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 16: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 17: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 18: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 19: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 20: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 21: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 22: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 23: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 24: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Problemi 25: Jepet një algoritëm rekurziv: procedura F (n: numër i plotë); fillo të shkruajn(n); nëse n

Rekursioni është kur një nënprogram thërret veten. Kur përballen për herë të parë me një dizajn të tillë algoritmik, shumica e njerëzve përjetojnë vështirësi të caktuara, por me pak praktikë, rekursioni do të bëhet një mjet i kuptueshëm dhe shumë i dobishëm në arsenalin tuaj të programimit.

1. Thelbi i rekursionit

Një procedurë ose funksion mund të përmbajë thirrje për procedura ose funksione të tjera. Procedura gjithashtu mund të quhet vetë. Këtu nuk ka asnjë paradoks - kompjuteri ekzekuton vetëm në mënyrë sekuenciale komandat që ndesh në program dhe, nëse ndeshet me një thirrje procedure, thjesht fillon ta ekzekutojë këtë procedurë. Nuk ka rëndësi se cila procedurë ka dhënë komandën për ta bërë këtë.

Shembull i një procedure rekursive:

Procedura Rec(a: numër i plotë); filloni nëse a>

Le të shqyrtojmë se çfarë ndodh nëse një thirrje, për shembull, e formës Rec(3) bëhet në programin kryesor. Më poshtë është një diagram që tregon sekuencën e ekzekutimit të deklaratave.

Oriz. 1. Blloku i procedurës rekursive.

Procedura Rec thirret me parametrin a = 3. Përmban një thirrje për procedurën Rec me parametrin a = 2. Thirrja e mëparshme nuk ka përfunduar ende, kështu që mund të imagjinoni që një procedurë tjetër është krijuar dhe e para nuk e përfundon punën e saj derisa përfundon. Procesi i thirrjes përfundon kur parametri a = 0. Në këtë pikë, 4 instanca të procedurës ekzekutohen njëkohësisht. Numri i procedurave të kryera njëkohësisht quhet thellësia e rekursionit.

Procedura e katërt e quajtur (Rec(0)) do të printojë numrin 0 dhe do të përfundojë punën e saj. Pas kësaj, kontrolli kthehet në procedurën që e quajti (Rec(1)) dhe numri 1 shtypet dhe kështu me radhë derisa të përfundojnë të gjitha procedurat. Thirrja origjinale do të printojë katër numra: 0, 1, 2, 3.

Një tjetër imazh vizual i asaj që po ndodh është paraqitur në Fig. 2.

Oriz. 2. Ekzekutimi i procedurës Rec me parametrin 3 konsiston në ekzekutimin e procedurës Rec me parametrin 2 dhe shtypjen e numrit 3. Nga ana tjetër, ekzekutimi i procedurës Rec me parametrin 2 konsiston në ekzekutimin e procedurës Rec me parametrin 1 dhe shtypjen e numrit 2. Etj. .

Si një ushtrim më vete, merrni parasysh se çfarë ndodh kur telefononi Rec(4). Konsideroni gjithashtu se çfarë do të ndodhte nëse do të thirrni procedurën Rec2(4) më poshtë, me operatorët të kundërt.

Procedura Rec2(a: numër i plotë); fillo të shkruajnë(a); nëse a>0 atëherë Rec2(a-1); fundi;

Ju lutemi vini re se në këta shembuj thirrja rekursive është brenda një deklarate të kushtëzuar. Ky është një kusht i domosdoshëm që rekursioni të përfundojë ndonjëherë. Vini re gjithashtu se procedura e quan veten me një parametër të ndryshëm nga ai me të cilin u thirr. Nëse procedura nuk përdor variabla globale, atëherë kjo është gjithashtu e nevojshme në mënyrë që rekursioni të mos vazhdojë pafundësisht.

Një skemë pak më komplekse është e mundur: funksioni A thërret funksionin B, i cili nga ana e tij thërret A. Kjo quhet rekursion kompleks. Rezulton se procedura e përshkruar së pari duhet të thërrasë një procedurë që ende nuk është përshkruar. Që kjo të jetë e mundur, duhet të përdorni.

Procedura A(n: numër i plotë); (Përshkrimi përpara (header) i procedurës së parë) procedura B(n: numër i plotë); (Përshkrimi përpara i procedurës së dytë) procedura A(n: numër i plotë); (Përshkrimi i plotë i procedurës A) filloni të shkruani (n); B(n-1); fundi; procedura B(n: numër i plotë); (Përshkrimi i plotë i procedurës B) filloni të shkruani (n); nëse n

Deklarata e përparme e procedurës B lejon që ajo të thirret nga procedura A. Deklarata përpara e procedurës A nuk kërkohet në këtë shembull dhe shtohet për arsye estetike.

Nëse rekursioni i zakonshëm mund të krahasohet me një Ouroboros (Fig. 3), atëherë imazhi i rekursionit kompleks mund të nxirret nga poema e famshme e fëmijëve, ku "Ujqërit u frikësuan dhe hëngrën njëri-tjetrin". Imagjinoni dy ujqër që hanë njëri-tjetrin dhe do të kuptoni rekursionin kompleks.

Oriz. 3. Ouroboros - një gjarpër që gllabëron bishtin e vet. Duke u nxjerrë nga traktati alkimik "Synosius" nga Theodore Pelecanos (1478).

Oriz. 4. Rekursioni kompleks.

3. Simulimi i një cikli duke përdorur rekursion

Nëse një procedurë thërret vetveten, në thelb bën që instruksionet që ajo përmban të ekzekutohen përsëri, ngjashëm me një lak. Disa gjuhë programimi nuk përmbajnë fare konstruksione looping, duke i lënë programuesit të organizojnë përsëritje duke përdorur rekursion (për shembull, Prolog, ku rekursioni është një teknikë bazë programimi).

Për shembull, le të simulojmë funksionimin e një cikli for. Për ta bërë këtë, ne kemi nevojë për një variabël numërues hapash, i cili mund të zbatohet, për shembull, si një parametër i procedurës.

Shembulli 1.

Procedura LoopImitation (i, n: numër i plotë); (Parametri i parë është numëruesi i hapave, parametri i dytë është numri i përgjithshëm i hapave) start writeln("Përshëndetje N", i); //Këtu janë udhëzimet që do të përsëriten nëse i

Rezultati i një thirrjeje të formularit LoopImitation(1, 10) do të jetë ekzekutimi i udhëzimeve dhjetë herë, duke ndryshuar numëruesin nga 1 në 10. Në këtë rast, do të printohen sa vijon:

Përshëndetje N 1
Përshëndetje N 2
…
Përshëndetje N 10

Në përgjithësi, nuk është e vështirë të shihet se parametrat e procedurës janë kufijtë për ndryshimin e vlerave të numëruesit.

Ju mund të ndërroni thirrjen rekursive dhe udhëzimet që do të përsëriten, si në shembullin e mëposhtëm.

Shembulli 2.

Procedura LoopImitation2(i, n: numër i plotë); filloni nëse i

Në këtë rast, një thirrje procedurash rekursive do të ndodhë përpara se udhëzimet të fillojnë të ekzekutohen. Instanca e re e procedurës gjithashtu, para së gjithash, do të thërrasë një shembull tjetër, e kështu me radhë, derisa të arrijmë vlerën maksimale të numëruesit. Vetëm pas kësaj, procedura e fundit e thirrur do të ekzekutojë instruksionet e saj, pastaj e dyta e fundit do të ekzekutojë instruksionet e saj, etj. Rezultati i thirrjes së LoopImitation2(1, 10) do të jetë printimi i përshëndetjeve në rend të kundërt:

Përshëndetje N 10
…
Përshëndetje N 1

Nëse imagjinojmë një zinxhir procedurash të quajtura në mënyrë rekursive, atëherë në shembullin 1 kalojmë përmes tij nga procedurat e quajtura më parë në ato të mëvonshme. Në shembullin 2, përkundrazi, nga më vonë në më parë.

Së fundi, një thirrje rekursive mund të vendoset midis dy blloqeve të udhëzimeve. Për shembull:

Procedura LoopImitation3(i, n: numër i plotë); filloni të shkruani ("Përshëndetje N", i); (Blloku i parë i udhëzimeve mund të gjendet këtu) nëse i

Këtu, instruksionet nga blloku i parë ekzekutohen fillimisht në mënyrë sekuenciale, pastaj udhëzimet nga blloku i dytë ekzekutohen në rend të kundërt. Kur thërrasim LoopImitation3(1, 10) marrim:

Përshëndetje N 1
…
Përshëndetje N 10
Përshëndetje N 10
…
Përshëndetje N 1

Do të duheshin dy sythe për të bërë të njëjtën gjë pa rekursion.

Ju mund të përfitoni nga fakti që ekzekutimi i pjesëve të së njëjtës procedurë është i ndarë me kalimin e kohës. Për shembull:

Shembulli 3: Shndërrimi i një numri në binar.

Marrja e shifrave të një numri binar, siç dihet, ndodh duke pjesëtuar me një mbetje me bazën e sistemit të numrave 2. Nëse ka një numër, atëherë shifra e fundit e tij në paraqitjen e tij binar është e barabartë me

Marrja e të gjithë pjesës së pjesëtimit me 2:

marrim një numër që ka të njëjtin paraqitje binar, por pa shifrën e fundit. Kështu, mjafton të përsëriten dy veprimet e mësipërme derisa fusha e ndarjes tjetër të marrë një pjesë të plotë të barabartë me 0. Pa rekursion do të duket kështu:

Ndërsa x>0 fillon c:=x mod 2; x:=x div 2; shkruaj (c); fundi;

Problemi këtu është se shifrat e paraqitjes binare llogariten në rend të kundërt (së pari i fundit). Për të printuar një numër në formë normale, do t'ju duhet të mbani mend të gjithë numrat në elementët e grupit dhe t'i printoni ato në një lak të veçantë.

Duke përdorur rekursionin, nuk është e vështirë të arrihet prodhimi në rendin e duhur pa një grup dhe një lak të dytë. Gjegjësisht:

Procedura Paraqitja Binare (x: numër i plotë); var c, x: numër i plotë; start (Blloku i parë. Ekzekutohet sipas renditjes së thirrjeve të procedurës) c:= x mod 2; x:= x div 2; (Thirrje rekursive) nëse x>0 atëherë Paraqitja Binare(x); (Blloku i dytë. Ekzekutohet në rend të kundërt) write(c); fundi;

Në përgjithësi, nuk kemi marrë asnjë fitim. Shifrat e paraqitjes binare ruhen në variabla lokale, të cilat janë të ndryshme për çdo shembull ekzekutues të procedurës rekursive. Kjo do të thotë, nuk ishte e mundur të ruhej memorie. Përkundrazi, ne harxhojmë memorie shtesë duke ruajtur shumë variabla lokale x. Megjithatë, kjo zgjidhje më duket e bukur.

4. Marrëdhëniet e përsëritjes. Rekursioni dhe përsëritja

Një sekuencë vektorësh thuhet se jepet nga një relacion përsëritjeje nëse jepet vektori fillestar dhe varësia funksionale e vektorit pasues nga ai i mëparshmi.

Një shembull i thjeshtë i një sasie të llogaritur duke përdorur marrëdhëniet e përsëritjes është faktoriali

Faktoriali tjetër mund të llogaritet nga ai i mëparshmi si:

Duke futur shënimin, marrim relacionin:

Vektorët nga formula (1) mund të interpretohen si grupe vlerash të ndryshueshme. Pastaj llogaritja e elementit të kërkuar të sekuencës do të konsistojë në përditësimin e përsëritur të vlerave të tyre. Në veçanti për faktorial:

X: = 1; për i:= 2 deri në n bëj x:= x * i; shkrimln(x);

Çdo përditësim i tillë (x:= x * i) thirret përsëritje, dhe procesi i përsëritjes së përsëritjeve është përsëritje.

Le të vërejmë, megjithatë, se relacioni (1) është një përkufizim thjesht rekurziv i sekuencës dhe llogaritja e elementit të n-të është në fakt marrja e përsëritur e funksionit f nga vetvetja:

Në veçanti, për faktorial mund të shkruhet:

Funksioni Faktorial(n: numër i plotë): numër i plotë; filloni nëse n > 1 atëherë Faktorial:= n * Faktorial(n-1) tjetër Faktorial:= 1; fundi;

Duhet të kuptohet se thirrja e funksioneve përfshin disa shpenzime shtesë, kështu që opsioni i parë për llogaritjen e faktorialit do të jetë pak më i shpejtë. Në përgjithësi, zgjidhjet përsëritëse funksionojnë më shpejt se ato rekursive.

Përpara se të kalojmë në situata ku rekursioni është i dobishëm, le të shohim një shembull tjetër ku ai nuk duhet të përdoret.

Le të shqyrtojmë një rast të veçantë të marrëdhënieve të përsëritura, kur vlera tjetër në sekuencë nuk varet nga një, por nga disa vlera të mëparshme menjëherë. Një shembull është sekuenca e famshme Fibonacci, në të cilën çdo element tjetër është shuma e dy të mëparshmeve:

Me një qasje "frontale", mund të shkruani:

Funksioni Fib(n: numër i plotë): numër i plotë; filloni nëse n > 1 atëherë Fib:= Fib(n-1) + Fib(n-2) tjetër Fib:= 1; fundi;

Çdo thirrje Fib krijon dy kopje të vetes, secila kopje krijon dy të tjera, e kështu me radhë. Numri i operacioneve rritet me numrin n në mënyrë eksponenciale, megjithëse me një zgjidhje përsëritëse lineare në n numri i operacioneve.

Në fakt, shembulli i mësipërm nuk na mëson KUR rekursioni nuk duhet të përdoret, përndryshe SI nuk duhet të përdoret. Në fund të fundit, nëse ka një zgjidhje të shpejtë përsëritëse (të bazuar në lak), atëherë i njëjti lak mund të zbatohet duke përdorur një procedurë ose funksion rekurziv. Për shembull:

// x1, x2 – kushtet fillestare (1, 1) // n – numri i funksionit të kërkuar të numrave Fibonaçi Fib(x1, x2, n: numër i plotë): numër i plotë; var x3: numër i plotë; filloni nëse n > 1 atëherë filloni x3:= x2 + x1; x1: = x2; x2: = x3; Fib:= Fib(x1, x2, n-1); fundi tjetër Fib:= x2; fundi;

Megjithatë, zgjidhjet përsëritëse janë të preferueshme. Pyetja është, kur duhet përdorur rekursioni në këtë rast?

Çdo procedurë dhe funksion rekurziv që përmban vetëm një thirrje rekursive për veten e tyre mund të zëvendësohet lehtësisht nga unazat përsëritëse. Për të marrë diçka që nuk ka një homolog të thjeshtë jo-rekurziv, duhet të përdorni procedura dhe funksione që e quajnë veten dy ose më shumë herë. Në këtë rast, grupi i procedurave të thirrura nuk formon më një zinxhir, si në Fig. 1, por një pemë e tërë. Ekzistojnë klasa të gjera problemesh kur procesi llogaritës duhet të organizohet në këtë mënyrë. Për ta, rekursioni do të jetë zgjidhja më e thjeshtë dhe më e natyrshme.

5. Pemët

Baza teorike për funksionet rekursive që e quajnë veten më shumë se një herë është dega e matematikës diskrete që studion pemët.

5.1. Përkufizimet bazë. Mënyrat për të përshkruar pemët

Përkufizimi: do ta quajmë bashkësinë e fundme T, i përbërë nga një ose më shumë nyje të tilla që:
a) Ekziston një nyje e veçantë që quhet rrënja e kësaj peme.
b) Nyjet e mbetura (me përjashtim të rrënjës) përmbahen në nënbashkësi të shkëputura në çift, secila prej të cilave nga ana tjetër është një pemë. Pemët quhen nënpemë të kësaj peme.

Ky përkufizim është rekurziv. Me pak fjalë, një pemë është një grup i përbërë nga një rrënjë dhe nënpemë të lidhura me të, të cilat janë gjithashtu pemë. Një pemë përcaktohet përmes vetvetes. Megjithatë, ky përkufizim ka kuptim sepse rekursioni është i kufizuar. Çdo nënpemë përmban më pak nyje sesa pema që përmban. Në fund, arrijmë te nënpemët që përmbajnë vetëm një nyje, dhe kjo tashmë është e qartë se çfarë është.

Oriz. 3. Pemë.

Në Fig. Figura 3 tregon një pemë me shtatë nyje. Megjithëse pemët e zakonshme rriten nga poshtë lart, është e zakonshme t'i vizatoni ato anasjelltas. Kur vizatoni një diagram me dorë, kjo metodë është padyshim më e përshtatshme. Për shkak të kësaj mospërputhjeje, nganjëherë lind konfuzioni kur thuhet se një nyje është mbi ose nën një tjetër. Për këtë arsye, është më i përshtatshëm të përdoret terminologjia e përdorur kur përshkruhen pemët familjare, duke i quajtur nyjet më afër paraardhësve të rrënjëve dhe ato më të largëta pasardhës.

Një pemë mund të përshkruhet grafikisht në disa mënyra të tjera. Disa prej tyre janë paraqitur në Fig. 4. Sipas përkufizimit, një pemë është një sistem grupesh të mbivendosura, ku këto grupe ose nuk kryqëzohen ose përfshihen plotësisht në njëra-tjetrën. Komplete të tilla mund të përshkruhen si rajone në një plan (Fig. 4a). Në Fig. 4b, grupet e mbivendosura nuk janë të vendosura në një aeroplan, por janë të zgjatur në një vijë. Oriz. 4b mund të shihet gjithashtu si një diagram i ndonjë formule algjebrike që përmban kllapa të vendosura. Oriz. Figura 4c jep një mënyrë tjetër popullore të paraqitjes së një strukture peme si një listë e shkallëzuar.

Oriz. 4. Mënyra të tjera për të përshkruar strukturat e pemëve: (a) grupe të mbivendosura; (b) kllapa të vendosura; (c) listën e koncesionit.

Lista e shkallëzuar ka ngjashmëri të dukshme me mënyrën se si është formatuar kodi i programit. Në të vërtetë, një program i shkruar brenda kornizës së paradigmës së programimit të strukturuar mund të përfaqësohet si një pemë e përbërë nga struktura të mbivendosura.

Ju gjithashtu mund të vizatoni një analogji midis listës së shkallëzuar dhe paraqitjes së tabelave të përmbajtjes në libra, ku seksionet përmbajnë nënseksione, të cilat nga ana tjetër përmbajnë nënseksione, etj. Mënyra tradicionale e numërimit të seksioneve të tilla (seksioni 1, nënseksionet 1.1 dhe 1.2, nënseksioni 1.1.2, etj.) quhet sistemi dhjetor Dewey. Aplikuar në pemën në Fig. 3 dhe 4 ky sistem do të japë:

1. A; 1.1 B; 1,2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. Pemë që kalojnë

Në të gjitha algoritmet që lidhen me strukturat e pemëve, shfaqet pa ndryshim e njëjta ide, domethënë ideja duke kaluar ose kalimi i pemës. Kjo është një mënyrë për të vizituar nyjet e pemëve në të cilat çdo nyje përshkohet saktësisht një herë. Kjo rezulton në një rregullim linear të nyjeve të pemëve. Në veçanti, ekzistojnë tre mënyra: ju mund të kaloni nëpër nyjet në rendin përpara, të kundërt dhe në fund.

Algoritmi i kalimit përpara:

• Shkoni në rrënjë
• Kaloni nëpër të gjitha nënpemët nga e majta në të djathtë në rend të drejtpërdrejtë.

Ky algoritëm është rekurziv, pasi kalimi i një peme përmban kalimin e nënpemëve, dhe ato, nga ana tjetër, përshkohen duke përdorur të njëjtin algoritëm.

Në veçanti, për pemën në Fig. 3 dhe 4, kalimi i drejtpërdrejtë jep një sekuencë nyjesh: A, B, C, D, E, F, G.

Sekuenca që rezulton korrespondon me një numërim nga e majta në të djathtë të nyjeve kur përfaqëson një pemë duke përdorur kllapa të ndërthurura dhe në shënimin dhjetor të Dewey, si dhe një pasazh nga lart-poshtë kur e përfaqëson atë si një listë të shkallëzuar.

Kur zbatohet ky algoritëm në një gjuhë programimi, goditja e rrënjës korrespondon me procedurën ose funksionin që kryen disa veprime, dhe kalimi nëpër nënpemë korrespondon me thirrjet rekursive ndaj vetvetes. Në veçanti, për një pemë binare (ku çdo nyje ka më së shumti dy nënpemë), procedura përkatëse do të duket kështu:

// Preorder Traversal – Emri anglisht për procedurën e porosisë direkte PreorderTraversal((Argumentet)); fillojë //Kalimi i rrënjës DoSomething((Argumentet)); //Tranzicioni i nënpemës së majtë nëse (Ka një nënpemë të majtë) atëherë PreorderTransversal((Argumentet 2)); //Transversal i nënpemës së djathtë nëse (Ka nënpemë të djathtë) atëherë PreorderTransversal((Argumentet 3)); fundi;

Kjo do të thotë, së pari procedura kryen të gjitha veprimet, dhe vetëm atëherë ndodhin të gjitha thirrjet rekursive.

Algoritmi i kalimit të kundërt:

• Kaloni nëpër nënpemën e majtë,
• Shkoni në rrënjë
• Kaloni nëpër nënpemën tjetër në të majtë.
• Shkoni në rrënjë
• etj derisa të përshkohet nënpema më e djathtë.

Domethënë, të gjitha nënpemët përshkohen nga e majta në të djathtë dhe kthimi në rrënjë ndodhet midis këtyre përshkimeve. Për pemën në Fig. 3 dhe 4 kjo jep sekuencën e nyjeve: B, A, D, C, E, G, F.

Në një procedurë rekursive përkatëse, veprimet do të vendosen në hapësirat ndërmjet thirrjeve rekursive. Në mënyrë të veçantë për një pemë binare:

// Inorder Traversal – Emri anglisht për procedurën e rendit të kundërt InorderTraversal((Argumentet)); fillo //Udhëtimi i nënpemës së majtë nëse (Ekziston një nënpemë e majtë) atëherë InorderTraversal((Argumentet 2)); //Kalimi i rrënjës DoSomething((Argumentet)); //Kaloni nënpemën e djathtë nëse (Një nënpemë e djathtë ekziston) atëherë InorderTraversal((Argumentet 3)); fundi;

Algoritmi i kalimit të rendit fundor:

• Kaloni nëpër të gjitha nënpemët nga e majta në të djathtë,
• Shkoni në rrënjë.

Për pemën në Fig. 3 dhe 4 kjo do të japë sekuencën e nyjeve: B, D, E, G, F, C, A.

Në një procedurë rekursive përkatëse, veprimet do të vendosen pas thirrjeve rekursive. Në mënyrë të veçantë për një pemë binare:

// Postorder Traversal – Emri në anglisht për procedurën e rendit të fundit PostorderTraversal((Argumentet)); fillo //Udhëtimi i nënpemës së majtë nëse (Ka një nënpemë të majtë) atëherë PostorderTraversal((Argumentet 2)); //Duke kapërcyer nënpemën e djathtë nëse (Një nënpemë e djathtë ekziston) atëherë PostorderTraversal((Argumentet 3)); //Kalimi i rrënjës DoSomething((Argumentet)); fundi;

5.3. Paraqitja e një peme në kujtesën e kompjuterit

Nëse disa informacione gjenden në nyjet e pemës, atëherë një strukturë e përshtatshme dinamike e të dhënave mund të përdoret për ta ruajtur atë. Në Pascal, kjo bëhet duke përdorur një variabël të llojit të regjistrimit që përmban tregues për nënpemë të të njëjtit lloj. Për shembull, një pemë binare ku çdo nyje përmban një numër të plotë mund të ruhet duke përdorur një ndryshore të tipit PTree, e cila përshkruhet më poshtë:

Lloji PTree = ^TTree; TTree = rekord Inf: integer; LeftSubTree, RightSubTree: PTree; fundi;

Çdo nyje ka një lloj PTree. Ky është një tregues, që do të thotë se çdo nyje duhet të krijohet duke thirrur procedurën New në të. Nëse nyja është një nyje gjethe, atëherë fushat e saj LeftSubTree dhe RightSubTree i caktohet vlera zero. Përndryshe, nyjet LeftSubTree dhe RightSubTree krijohen gjithashtu me procedurën New.

Një regjistrim i tillë është paraqitur në mënyrë skematike në Fig. 5.

Oriz. 5. Paraqitja skematike e një rekord të tipit TTree. Rekordi ka tre fusha: Inf - një numër, LeftSubTree dhe RightSubTree - tregues për të dhënat e të njëjtit lloj TTree.

Një shembull i një peme të përbërë nga të dhëna të tilla është paraqitur në Figurën 6.

Oriz. 6. Një pemë e përbërë nga rekorde të tipit TTree. Çdo hyrje ruan një numër dhe dy tregues që mund të përmbajnë secilin prej tyre zero, ose adresat e regjistrimeve të tjera të të njëjtit lloj.

Nëse nuk keni punuar më parë me struktura që përbëhen nga regjistrime që përmbajnë lidhje me regjistrime të të njëjtit lloj, ju rekomandojmë që të njiheni me materialin rreth.

6. Shembuj të algoritmeve rekursive

6.1. Vizatimi i një peme

Le të shqyrtojmë algoritmin për vizatimin e pemës të paraqitur në Fig. 6. Nëse çdo rresht konsiderohet një nyje, atëherë ky imazh plotëson plotësisht përkufizimin e një peme të dhënë në seksionin e mëparshëm.

Oriz. 6. Pemë.

Procedura rekursive padyshim do të vizatonte një vijë (trungu deri në degën e parë), dhe më pas do të thërriste veten për të vizatuar dy nënpemë. Nënpemët ndryshojnë nga pema që i përmban në koordinatat e pikës së tyre fillestare, këndin e rrotullimit, gjatësinë e trungut dhe numrin e degëve që përmbajnë (një më pak). Të gjitha këto dallime duhet të bëhen parametra të procedurës rekursive.

Një shembull i një procedure të tillë, i shkruar në Delphi, është paraqitur më poshtë:

Pema e procedurës(Kanavacë: TCanvas; //Kanavacë në të cilën do të vizatohet pema x,y: e zgjeruar; //Koordinatat e rrënjës Këndi: i zgjeruar; //Këndi në të cilin pema rritet Gjatësia e trungut: e zgjeruar; //Gjatësia e trungut n: numër i plotë / /Numri i degëve (sa të tjera //thirrjet rekursive ende nuk janë bërë)); var x2, y2: e zgjeruar; //Fundi i trungut (pika e degës) fillon x2:= x + Gjatësia e trungut * cos(Këndi); y2:= y - Gjatësia e trungut * sin(Këndi); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); nëse n > 1 atëherë fillon Pema (Kanvas, x2, y2, Këndi+Pi/4, 0.55*Gjatësia e trungut, n-1); Pema (Kanavacë, x2, y2, Këndi-Pi/4, 0,55*Gjatësia e trungut, n-1); fundi; fundi;

Për të marrë Fig. 6 kjo procedurë u thirr me parametrat e mëposhtëm:

Pema (Image1. Canvas, 175, 325, Pi/2, 120, 15);

Vini re se vizatimi kryhet përpara thirrjeve rekursive, domethënë, pema vizatohet në rend të drejtpërdrejtë.

6.2. Kullat e Hanoi

Sipas legjendës në Tempullin e Madh të Banaras, nën katedralen që shënon mesin e botës, ndodhet një disk bronzi, në të cilin janë fiksuar 3 shufra diamanti, një kubit të lartë dhe të trashë si bleta. Shumë kohë më parë, në fillimet e kohës, murgjit e këtij manastiri kryen një ofendim para zotit Brahma. I tërbuar, Brahma ngriti tre shufra të larta dhe vendosi 64 disqe ari të pastër në njërën prej tyre, në mënyrë që çdo disk më i vogël të mbështetej në një më të madh. Sapo të 64 disqet të transferohen nga shufra në të cilën Zoti Brahma i vendosi kur krijoi botën, në një shufër tjetër, kulla së bashku me tempullin do të shndërrohen në pluhur dhe bota do të zhduket nën bubullima.
Procesi kërkon që disku më i madh të mos përfundojë kurrë mbi diskun më të vogël. Murgjit janë në dilemë: në çfarë radhe duhet t'i bëjnë turnet? Kërkohet t'u sigurohet atyre softuer për të llogaritur këtë sekuencë.

Pavarësisht nga Brahma, kjo enigmë u propozua në fund të shekullit të 19-të nga matematikani francez Edouard Lucas. Versioni i shitur zakonisht përdorte 7-8 disqe (Fig. 7).

Oriz. 7. Puzzle "Kullat e Hanoi".

Le të supozojmë se ka një zgjidhje për n-1 disk. Pastaj për ndërrim n disqe, veproni si më poshtë:

1) Zhvendosja n-1 disk.
2) Ndryshim n diskun në kutinë e mbetur të lirë.
3) Ne zhvendosim pirgun nga n-1 disk i marrë në pikën (1) sipër n- disku.

Sepse për rastin n= 1 algoritmi i rirregullimit është i dukshëm, atëherë me induksion, duke përdorur veprimet (1) – (3), mund të riorganizojmë një numër arbitrar disqesh.

Le të krijojmë një procedurë rekursive që printon të gjithë sekuencën e rirregullimeve për një numër të caktuar disqesh. Sa herë që thirret një procedurë e tillë, ajo duhet të printojë informacion rreth një ndërrimi (nga pika 2 e algoritmit). Për rirregullimet nga pikat (1) dhe (3), procedura do të quhet vetë me numrin e disqeve të reduktuar me një.

//n – numri i disqeve //a, b, c – numrat e pin. Zhvendosja bëhet nga kunja a, //në kunja b me kunjën ndihmëse c. procedura Hanoi(n, a, b, c: numër i plotë); filloni nëse n > 1 atëherë filloni Hanoi(n-1, a, c, b); writeln(a, " -> ", b); Hanoi (n-1, c, b, a); end other writeln(a, " -> ", b); fundi;

Vini re se grupi i procedurave të quajtura në mënyrë rekursive në këtë rast formon një pemë të përshkuar në rend të kundërt.

6.3. Analiza e shprehjeve aritmetike

Detyra e analizës është të llogarisë vlerën e shprehjes duke përdorur një varg ekzistues që përmban një shprehje aritmetike dhe vlerat e njohura të ndryshoreve të përfshira në të.

Procesi i llogaritjes së shprehjeve aritmetike mund të paraqitet si një pemë binare. Në të vërtetë, secili prej operatorëve aritmetikë (+, –, *, /) kërkon dy operandë, të cilët gjithashtu do të jenë shprehje aritmetike dhe, në përputhje me rrethanat, mund të konsiderohen si nënpemë. Oriz. Figura 8 tregon një shembull të një peme që korrespondon me shprehjen:

Oriz. 8. Pema sintaksore që i përgjigjet shprehjes aritmetike (6).

Në një pemë të tillë, nyjet fundore do të jenë gjithmonë variabla (këtu x) ose konstante numerike, dhe të gjitha nyjet e brendshme do të përmbajnë operatorë aritmetikë. Për të ekzekutuar një operator, së pari duhet të vlerësoni operandët e tij. Kështu, pema në figurë duhet të përshkohet sipas rendit terminal. Sekuenca përkatëse e nyjeve

thirrur shënimi i kundërt polak shprehje aritmetike.

Kur ndërtoni një pemë sintaksore, duhet t'i kushtoni vëmendje veçorisë së mëposhtme. Nëse, për shembull, ekziston një shprehje

dhe ne do të lexojmë veprimet e mbledhjes dhe zbritjes nga e majta në të djathtë, atëherë pema e saktë sintaksore do të përmbajë një minus në vend të një plus (Fig. 9a). Në fakt, kjo pemë korrespondon me shprehjen Është e mundur të lehtësohet krijimi i një peme nëse analizoni shprehjen (8) në të kundërt, nga e djathta në të majtë. Në këtë rast, rezultati është një pemë me Fig. 9b, ekuivalente me pemën 8a, por që nuk kërkon zëvendësim të shenjave.

Në mënyrë të ngjashme, nga e djathta në të majtë, duhet të analizoni shprehjet që përmbajnë operatorë të shumëzimit dhe ndarjes.

Oriz. 9. Pemë sintaksore për shprehje a – b + c kur lexoni nga e majta në të djathtë (a) dhe nga e djathta në të majtë (b).

Kjo qasje nuk e eliminon plotësisht rekursionin. Megjithatë, ju lejon të kufizoni veten në vetëm një thirrje në procedurën rekursive, e cila mund të jetë e mjaftueshme nëse motivi është të maksimizoni performancën.

7.3. Përcaktimi i një nyje peme nga numri i saj

Ideja e kësaj qasjeje është të zëvendësojë thirrjet rekursive me një lak të thjeshtë që do të ekzekutohet aq herë sa ka nyje në pemë të formuara nga procedurat rekursive. Çfarë saktësisht do të bëhet në çdo hap duhet të përcaktohet nga numri i hapit. Krahasimi i numrit të hapit dhe veprimeve të nevojshme nuk është një detyrë e parëndësishme dhe në secilin rast do të duhet të zgjidhet veçmas.

Për shembull, le të themi se dëshironi të bëni k sythe të mbivendosur n hapat në secilën:

Për i1:= 0 në n-1 bëni për i2:= 0 deri në n-1 bëni për i3:= 0 deri në n-1 bëni…

Nëse kështë i panjohur paraprakisht, është e pamundur t'i shkruani ato në mënyrë eksplicite, siç tregohet më sipër. Duke përdorur teknikën e demonstruar në seksionin 6.5, mund të merrni numrin e kërkuar të sytheve të mbivendosur duke përdorur një procedurë rekursive:

Procedura NestedCycles(Indekset: grup i numrave të plotë; n, k, thellësia: numër i plotë); var i: numër i plotë; fillojë nëse thellësia

Për të hequr qafe rekursionin dhe për të reduktuar gjithçka në një cikël, vini re se nëse numëroni hapat në sistemin e numrave bazë n, atëherë çdo hap ka një numër që përbëhet nga numrat i1, i2, i3, ... ose vlerat përkatëse nga grupi i Indekseve. Kjo do të thotë, numrat korrespondojnë me vlerat e numëruesve të ciklit. Numri i hapit në shënimin e rregullt dhjetor:

Do të ketë një total hapash n k. Duke kaluar nëpër numrat e tyre në sistemin e numrave dhjetorë dhe duke e kthyer secilin prej tyre në sistemin radix n, marrim vlerat e indeksit:

M:= round(IntPower(n, k)); për i:= 0 deri në M-1 filloni Numri:= i; për p:= 0 deri në k-1 do të fillojë Indekset := Numri mod n; Numri:= Numri div n; fundi; DoSomething(Indekset); fundi;

Le të theksojmë edhe një herë se metoda nuk është universale dhe do t'ju duhet të gjeni diçka të ndryshme për secilën detyrë.

Pyetje kontrolli

1. Përcaktoni se çfarë do të bëjnë procedurat dhe funksionet rekursive të mëposhtme.

(a) Çfarë do të printojë procedura e mëposhtme kur quhet Rec(4)?

Procedura Rec(a: numër i plotë); fillo të shkruajnë(a); nëse a>0 atëherë Rec(a-1); shkrimln(a); fundi;

(b) Sa do të jetë vlera e funksionit Nod(78, 26)?

Funksioni Nod(a, b: numër i plotë): numër i plotë; filloni nëse a > b atëherë Nod:= Nod(a – b, b) other if b > a then Nod:= Nod(a, b – a) other Nod:= a; fundi;

(c) Çfarë do të shtypet nga procedurat e mëposhtme kur thirret A(1)?

Procedura A(n: numër i plotë); procedura B(n: numër i plotë); procedura A(n: numër i plotë); fillo të shkruajn(n); B(n-1); fundi; procedura B(n: numër i plotë); fillo të shkruajn(n); nëse n

(d) Çfarë do të printojë procedura e mëposhtme kur telefononi BT(0, 1, 3)?

Procedura BT(x: real; D, MaxD: numër i plotë); filloni nëse D = MaxD atëherë shkruanin(x) tjetër fillon BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); fundi; fundi;

2. Ouroboros - një gjarpër që gllabëron bishtin e vet (Fig. 14) kur shpaloset ka një gjatësi L, diametri rreth kokës D, trashësia e murit të barkut d. Përcaktoni sa bisht mund të shtrydh në vetvete dhe në sa shtresa do të vendoset bishti pas kësaj?

Oriz. 14. Ouroboros i zgjeruar.

3. Për pemën në Fig. 10a tregon sekuencën e vizitës së nyjeve në rendin e kalimit përpara, mbrapa dhe fundi.

4. Paraqitni grafikisht pemën e përcaktuar duke përdorur kllapa të ndërthurura: (A(B(C, D), E), F, G).

5. Paraqisni grafikisht pemën e sintaksës për shprehjen aritmetike të mëposhtme:

Shkruajeni këtë shprehje me shënimin e kundërt polak.

6. Për grafikun e mëposhtëm (Fig. 15), shkruani matricën e afërsisë dhe matricën e incidencës.

Detyrat

1. Pasi të keni llogaritur faktorialin një numër mjaft të madh herë (një milion ose më shumë), krahasoni efektivitetin e algoritmeve rekursive dhe iterative. Sa do të ndryshojë koha e ekzekutimit dhe si do të varet ky raport nga numri faktorial i të cilit llogaritet?

2. Shkruani një funksion rekurziv që kontrollon nëse kllapat janë vendosur saktë në një varg. Nëse rregullimi është i saktë, plotësohen kushtet e mëposhtme:

(a) numri i kllapave hapëse dhe mbyllëse është i barabartë.
(b) brenda çdo çifti ka një hapje - kllapa mbyllëse përkatëse, kllapat janë vendosur saktë.

Shembuj të vendosjes së gabuar:)(, ())(, ())((), etj.

3. Rreshti mund të përmbajë kllapa të rrumbullakëta dhe katrore. Çdo kllapë hapëse ka një kllapë mbyllëse përkatëse të të njëjtit lloj (rrumbullak - i rrumbullakët, katror - katror). Shkruani një funksion rekurziv që kontrollon nëse kllapat janë vendosur saktë në këtë rast.

Shembull i vendosjes së gabuar: ([) ].

4. Numri i strukturave të kllapave të rregullta me gjatësi 6 është 5: ()()(), (())(), ()(()), ((())), (()()).
Shkruani një program rekurziv për të gjeneruar të gjitha strukturat e rregullta të kllapave me gjatësi 2 n.

shënim: Struktura e saktë e kllapave me gjatësi minimale "()". Strukturat me gjatësi më të madhe merren nga strukturat me gjatësi më të shkurtër në dy mënyra:

(a) nëse struktura më e vogël merret në kllapa,
(b) nëse dy struktura më të vogla shkruhen në mënyrë sekuenciale.

5. Krijo një procedurë që printon të gjitha permutacionet e mundshme për numrat e plotë nga 1 në N.

6. Krijo një procedurë që printon të gjitha nëngrupet e grupit (1, 2, ..., N).

7. Krijo një procedurë që printon të gjitha paraqitjet e mundshme të numrit natyror N si shumë e numrave të tjerë natyrorë.

8. Krijo një funksion që llogarit shumën e elementeve të grupit duke përdorur algoritmin e mëposhtëm: grupi ndahet në gjysmë, shumat e elementeve në secilën gjysmë llogariten dhe shtohen. Shuma e elementeve në gjysmën e grupit llogaritet duke përdorur të njëjtin algoritëm, pra përsëri duke e ndarë në gjysmë. Ndarjet ndodhin derisa pjesët rezultuese të grupit të përmbajnë nga një element secila dhe llogaritja e shumës, në përputhje me rrethanat, bëhet e parëndësishme.

Komentoni: Ky algoritëm është një alternativë. Në rastin e vargjeve me vlerë reale, zakonisht lejon gabime më të vogla rrumbullakimi.

10. Krijoni një procedurë që vizaton kurbën Koch (Figura 12).

11. Riprodhoni figurën. 16. Në figurë, në çdo përsëritje tjetër rrethi është 2,5 herë më i vogël (ky koeficient mund të bëhet parametër).

Letërsia

1. D. Knuth. Arti i programimit kompjuterik. v. 1. (seksioni 2.3. "Pemët").
2. N. Wirth. Algoritmet dhe strukturat e të dhënave.