Algoritmid ja rekursioon Matemaatika kiirreferents

Algoritmid ja rekursioon

Mõiste

Algoritm on täpne sammude jada probleemi lahendamiseks. Rekursioon tähendab, et objekt või arvutus määratletakse eelmiste väärtuste kaudu.

Eeldus: oskad kasutada jaguvust, jääki, lihtsaid tingimuslauseid ja jadade esimesi liikmeid.

Hea algoritm kirjeldab:

Algoritmi kontrollimisel küsi alati: kas sisend on selge, kas sammud on üheselt mõistetavad ja kas arvutus jõuab lõpuni?

Lõppemise kontrolliks otsi suurust, mis igal sammul liigub peatustingimuse poole. Eukleidese algoritmis muutub jääk väiksemaks; rekursioonis peab järgmine väljakutse olema lihtsam juht.

Pseudokood

Pseudokood on inimloetav kirjeldus, mis sarnaneb programmile, aga ei sõltu ühestki programmeerimiskeelest.

Näide: kahe arvu summa.

sisend: arvud a ja b
summa = a + b
väljund: summa

Näide: leia loendist suurim arv.

sisend: arvude loend
suurim = esimene arv loendis
iga järgmise arvu kohta:
    kui arv > suurim:
        suurim = arv
väljund: suurim

Eukleidese algoritm

Kahe arvu suurima ühisteguri saab leida jääkide abil.

sisend: positiivsed täisarvud a ja b
kuni b ei ole 0:
    jääk = a jagamisel b-ga tekkiv jääk
    a = b
    b = jääk
väljund: a

Näiteks $SÜT(48,18)$:

$$48=2\cdot18+12,$$

$$18=1\cdot12+6,$$

$$12=2\cdot6+0.$$

Kui jääk on 0, on viimane nullist erinev jagaja 6. Seega $SÜT(48,18)=6$.

Rekursioon

Fibonacci jada:

$$F_1=1,\qquad F_2=1,$$

$$F_n=F_{n-1}+F_{n-2}.$$

Siin on peatustingimused $F_1=1$ ja $F_2=1$. Ilma nendeta ei teaks, kust arvutamist alustada.

Rekursiivne pseudokood Fibonacci arvu jaoks:

F(n):
    kui n = 1 või n = 2:
        tagasta 1
    muidu:
        tagasta F(n-1) + F(n-2)

Peatustingimus on rida

kui n = 1 või n = 2:
    tagasta 1

See takistab lõputut tagasikutsumist.

Rekursioonis peab iga samm liikuma lihtsama juhu poole: $F_6$ vajab $F_5$ ja $F_4$, need vajavad veel varasemaid liikmeid, kuni jõutakse väärtusteni $F_1$ ja $F_2$.

Näide

Leia $F_6$.

Alustame teadaolevatest algväärtustest:

$$F_1=1,\quad F_2=1.$$

Seejärel kasutame reeglit $F_n=F_{n-1}+F_{n-2}$:

$$F_3=F_2+F_1=1+1=2,$$

$$F_4=F_3+F_2=2+1=3,$$

$$F_5=F_4+F_3=3+2=5,$$

$$F_6=F_5+F_4=5+3=8.$$

Vastus: $F_6=8$.

Kontroll: iga uus liige on kahe eelmise summa, nii et jada algus on $1,1,2,3,5,8$.

Tüüpviga

Rekursiivsel kirjeldusel peab olema algväärtus. Muidu ei saa arvutust alustada.

Teine tüüpviga on kirjutada rekursioon nii, et see ei liigu peatustingimuse poole. Näiteks kui $F(n)$ kutsub uuesti $F(n)$, ei muutu ülesanne väiksemaks ja arvutus ei lõpe.

Kolmas tüüpviga on ajada algoritmi kirjeldus ja üks konkreetne arvutus segi. Algoritm peab töötama kõigi lubatud sisendite jaoks, mitte ainult ühe näite jaoks.

Neljas tüüpviga on jätta sisendipiirid ütlemata. Näiteks Eukleidese algoritmi juures peab olema selge, et sisendiks on positiivsed täisarvud.

Harjutused

Lihtne kontroll

  1. Leia Fibonacci jada kuues liige.
  2. Kirjelda algoritm kahe arvu suurima ühisteguri leidmiseks.

Rakendus

  1. Miks vajab rekursioon lõpetamistingimust?
  2. Mis on sisend ja väljund Eukleidese algoritmis?

Mõtlemisülesanne

  1. Kirjuta pseudokood, mis kontrollib, kas arv $n$ on paarisarv.
  2. Mis juhtub rekursiooniga, kui peatustingimus puudub?
  3. Milline on sisend, väljund ja lõpetamistingimus algoritmis, mis loendab arvud 1-st $n$-ni?
  4. Miks on oluline, et rekursiivne samm liiguks lihtsama juhu poole?

Vastused

  1. $F_6=8$.
  2. Jaga suuremat väiksemaga, asenda arvud jagaja ja jäägiga, korda kuni jääk on 0; viimane nullist erinev jagaja on SÜT.
  3. Et arvutus lõpeks ja jõuaks teadaoleva algväärtuseni; iga samm peab liikuma sellele lähemale.
  4. Sisend on kaks positiivset täisarvu, väljund on nende suurim ühistegur.
  5. Näiteks:
sisend: n
kui n jagamisel 2-ga jääk on 0:
    väljund: paarisarv
muidu:
    väljund: paaritu arv
  1. Arvutus võib jätkuda lõputult või kuni arvutil ressursid otsa saavad.
  2. Sisend on positiivne täisarv $n$; väljund on arvud $1,2,\ldots,n$; lõpetamistingimus on see, et loendur jõuab väärtuseni $n$, seega järgmine samm enam uut arvu ei lisa.
  3. Siis jõuab arvutus lõpuks algväärtuse või peatustingimuseni; rekursiivne sisend peab igal sammul lihtsamaks muutuma.

Seosed

Algoritmid seovad matemaatika informaatika, tõestuste, jadade ja modelleerimisega. Järgmine modelleerimise plokk kasutab sama mõtet: päris olukord tuleb muuta selgete sisendite, reeglite ja väljundiga matemaatiliseks mudeliks.