Rekursive sammenhenger og programmering

Neste ledd regnes ut fra det forrige. Fibonacci, bestander og lån, utforsket med små Python-programmer rett i nettleseren.

R2
Fint å kunne først: Geometriske rekkerGrunnleggende Python (løkker og variabler)
Utforsk

Start her: utforsk

En pasient tar 200 mg av et legemiddel hver morgen. I løpet av et døgn bryter kroppen ned 40 % av det som er i blodet, så 60 % er igjen neste morgen. Hvor mye er det i kroppen rett etter dose nummer 2? Nummer 3? Hoper medisinen seg opp for alltid?

Regn ut dag 2 og dag 3 for hånd først. Kjør så programmet. Hver runde i løkka bruker gårsdagens tall til å regne ut dagens.

PythonMedisindoser
Ctrl/Cmd + Enter kjører koden. Første kjøring laster Python (noen sekunder).

Prøv dette:

  1. Stemmer tallene dine for dag 2 og dag 3 med programmet?
  2. Hva skjer med mengden etter mange dager? Nærmer den seg et bestemt tall?
  3. Endre dosen til 100 mg. Hvilket tall nærmer mengden seg nå? Gjett før du kjører.
  4. Hva trenger du for å regne ut mengden en bestemt dag?
Forklaring

Forklaring

Rekursiv og eksplisitt form

For medisinen trengte du bare gårsdagens tall og en regel: Dag 2 er 0,6⋅200+200=3200{,}6 \cdot 200 + 200 = 320 mg, og dag 3 er 0,6⋅320+200=3920{,}6 \cdot 320 + 200 = 392 mg. Med symboler: m1=200m_1 = 200 og mn+1=0,6⋅mn+200m_{n+1} = 0{,}6 \cdot m_n + 200. En slik sammenheng, der neste ledd regnes ut fra det forrige, kalles rekursiv. Datamaskiner er som skapt for dette: En løkke gjentar regelen så mange ganger du vil.

En følge kan beskrives på to måter:

AritmetiskGeometrisk
Rekursiva1=3a_1 = 3, an+1=an+2a_{n+1} = a_n + 2a1=3a_1 = 3, an+1=2ana_{n+1} = 2a_n
Eksplisittan=3+2(n−1)a_n = 3 + 2(n - 1)an=3⋅2n−1a_n = 3 \cdot 2^{n-1}

Den rekursiveRekursjonÅ definere hvert ledd ut fra det eller de forrige leddene, som an+1=1,05⋅an+1000a_{n+1} = 1{,}05 \cdot a_n + 1000. Passer godt for programmering. formen trenger alltid et startledd og en regel.

Når formelen blir vanskelig

Mange rekursive sammenhenger har ingen enkel eksplisitt formel, eller en som er vanskelig å finne:

  • Fibonacci: F1=F2=1F_1 = F_2 = 1 og Fn+2=Fn+1+FnF_{n+2} = F_{n+1} + F_n.
  • Bestand med fangst: Bn+1=1,08⋅Bn−500B_{n+1} = 1{,}08 \cdot B_n - 500.
  • Logistisk vekst i diskret form: xn+1=r⋅xn(1−xn)x_{n+1} = r \cdot x_n (1 - x_n).

Da er programmering det naturlige verktøyet.

Modell: Fibonacci

Kjør programmet. Endre det så det skriver ut forholdet Fn+1Fn\frac{F_{n+1}}{F_n}. Hvilket tall nærmer forholdet seg?

PythonFibonacci-følgen
Ctrl/Cmd + Enter kjører koden. Første kjøring laster Python (noen sekunder).

Modell: Kaos i logistisk vekst

Den diskrete logistiske modellen xn+1=rxn(1−xn)x_{n+1} = r x_n(1 - x_n) oppfører seg helt forskjellig for ulike rr. Prøv r=2,8r = 2{,}8, r=3,2r = 3{,}2, r=3,5r = 3{,}5 og r=3,9r = 3{,}9.

PythonLogistisk kart
Ctrl/Cmd + Enter kjører koden. Første kjøring laster Python (noen sekunder).

Mønsteret i et program

a = 3            # startledd
for n in range(10):
    print(n + 1, a)
    a = 2 * a    # regelen: neste ledd fra det forrige

Hver runde i løkka skriver ut ett ledd og regner ut det neste.

Likevekt

Medisinmengden nærmet seg 500 mg. Der skjer det ingen endring lenger: 0,6⋅500+200=5000{,}6 \cdot 500 + 200 = 500. Generelt kan an+1=k⋅an+ba_{n+1} = k \cdot a_n + b nærme seg en likevekt LL, der L=kL+bL = kL + b, altså L=b1−kL = \frac{b}{1 - k} (når ∣k∣<1|k| < 1). For medisinen er L=2001−0,6=500L = \frac{200}{1 - 0{,}6} = 500. Det er nært beslektet med den uendelige geometriske rekken.

Eksempler

Gjennomgåtte eksempler

Eksempel 1: Fra rekursiv til eksplisitt

En følge er gitt ved a1=5a_1 = 5 og an+1=an⋅3a_{n+1} = a_n \cdot 3. Finn en eksplisitt formel.

Hvert ledd er 3 ganger det forrige, så følgen er geometrisk med k=3k = 3.
an=5⋅3n−1a_n = 5 \cdot 3^{n-1}.
Eksempel 2: Likevekt for medisinen

Med mn+1=0,6⋅mn+200m_{n+1} = 0{,}6 \cdot m_n + 200: Hvilken mengde nærmer mnm_n seg?

Likevekten LL oppfyller L=0,6L+200L = 0{,}6L + 200.
0,4L=2000{,}4L = 200, så L=500L = 500 mg.
Mengden rett etter hver dose nærmer seg 500 mg.
Eksempel 3: Bestand med fangst

En fiskebestand er 10 000 tonn og vokser med 8 % per år før fangst. Hvert år fanges 500 tonn. Vil bestanden vokse eller minke?

Bn+1=1,08Bn−500B_{n+1} = 1{,}08B_n - 500. Likevekt: L=1,08L−500L = 1{,}08L - 500 gir L=6250L = 6250.
Bestanden starter over likevekten, og siden k=1,08>1k = 1{,}08 > 1, beveger den seg bort fra likevekten: Den vokser.
Med en start under 6250 tonn ville bestanden krympet mot utryddelse. Likevekten er ustabil.
Vanlige feil

Vanlige feil

  • Å glemme startleddet. Uten a1a_1 er følgen ikke bestemt.
  • Feil rekkefølge i løkka. Skriv ut før du oppdaterer, ellers mister du det første leddet.
  • a, b = b, a + b vs. to linjer. a = b og deretter b = a + b gir feil, fordi a allerede er endret.
  • Avrundingsfeil i lange løkker. Rund av bare når du skriver ut.
Huskelapp

Huskelapp

  • Rekursiv form: startledd + regel for neste ledd.
  • Program: løkke som skriver ut og oppdaterer.
  • Aritmetisk an+1=an+da_{n+1} = a_n + d, geometrisk an+1=k⋅ana_{n+1} = k \cdot a_n.
  • Likevekt i an+1=kan+ba_{n+1} = ka_n + b: L=b1−kL = \frac{b}{1 - k}, stabil når ∣k∣<1|k| < 1.
Oppgaver

Øv selv