Rekursive sammenhenger og programmering

Rekursive sammenhenger R2 – Python, modeller og oppgaver Matematikk R2 · Kapittel 2

Fra startverdi og overgangsregel til likevekt, stabilitet, terskler, feilsøking og dokumentert Python-programmering.

Rekursiv arbeidskjede. Figuren viser arbeidsrekkefølgen og erstatter ikke den matematiske begrunnelsen. 16 undervisningsseksjoner 48 modelløsninger 96 øvingsoppgaver 48 testoppgaver

Offisiell forankring og kapittelgrense

Kapittelet dekker kompetansemålet «Utforske rekursive sammenhenger ved å bruke programmering og presentere egne framgangsmåter». Følger og rekker behandles i kapittel 1. Generell bevisteori og systematisk induksjon behandles i kapittel 3, men kontroll av foreslåtte formler brukes her når det støtter programmeringen.

Kildeprinsipp: Udir, moderne REA3058-oppgavetyper, eksisterende Ifingo-materiale og offentlige konkurrentressurser brukes til dekningskontroll. Formuleringer, tallsett, oppgaver, løsninger, figurer og kode er selvstendig utviklet.

Innhold

1. 1. Startverdi og rekursiv overgangsregel
2. 2. Indeks, løkker og off-by-one-feil
3. 3. Additive rekursjoner og variable tillegg
4. 4. Multiplikative rekursjoner og prosentvis endring
5. 5. Affine rekursjoner: beholdning og fast bidrag
6. 6. Fastpunkt og likevekt
7. 7. Stabilitet, konvergens og oscillasjon
8. 8. Fra rekursiv til eksplisitt form
9. 9. Terskelverdier og stoppbetingelser
10. 10. Rekursjon med flere tidligere ledd
11. 11. Flere tilstandsvariabler i samme modell
12. 12. Rekursive funksjoner og iterative algoritmer
13. 13. Lister, tabeller og grafisk utforsking
14. 14. Feilsøking, testing og robuste programmer
15. 15. Fra tekst og data til rekursiv modell
16. 16. Eksamensføring og presentasjon av framgangsmåte

1. Startverdi og rekursiv overgangsregel

En rekursiv sammenheng beskriver hvordan en ny tilstand bygges fra en eller flere tidligere tilstander. En fullstendig modell må angi både startverdien og oppdateringsregelen. Uten startverdi finnes det vanligvis mange mulige følger som oppfyller den samme regelen.

Kjernepunkt: Startverdi, overgangsregel, indeks og enhet må defineres før beregning. Startverdi og rekursiv overgangsregel. Figuren viser arbeidsrekkefølgen og erstatter ikke den matematiske begrunnelsen. Modelløsning 1 Seksjon 1

Bygg en følge fra startverdi og regel

En prosess starter med 4 enheter og øker med 3 per steg. Skriv rekursjonen og finn de seks første leddene. Bygg en følge fra startverdi og regel. Punktene er diskrete ledd, ikke en kontinuerlig funksjonsgraf. a₀=4, aₙ=aₙ₋₁+3 Faglig idé

Startverdi og overgangsregel må oppgis sammen.

Metodevalg

Modellen beregnes trinnvis og kontrolleres med en selvstendig kodekjøring.

1. Startverdien er a₀=4.
2. Oppdateringsregelen er aₙ=aₙ₋₁+3.
3. Gjenta regelen fem ganger og behold indeksen.

Følgen blir [4, 7, 10, 13, 16, 19]. Python-kontroll – faktisk kjørt

a=4 vals=[a] for n in range(1,6): a=a+3 vals.append(a) print(vals) assert vals==[4, 7, 10, 13, 16, 19]

Kjørt utskrift: [4, 7, 10, 13, 16, 19]

Vanlig feil: Å gi bare aₙ=aₙ₋₁+3 uten startverdi. Sensorblikk: Vis både definisjon og beregnede ledd.

Se alle tre modelløsningene i seksjonen

2. Indeks, løkker og off-by-one-feil

Programmet må holde styr på hvilket ledd variabelen representerer før og etter en oppdatering. Mange feil skyldes at startverdien skrives ut etter at den allerede er oppdatert, eller at range-grensene gir én iterasjon for mye eller for lite.

Kjernepunkt: Koble hver iterasjon til en presis matematisk indeks. Indeks, løkker og off-by-one-feil. Figuren viser arbeidsrekkefølgen og erstatter ikke den matematiske begrunnelsen. Modelløsning 4 Seksjon 2

Indekskontroll 1: riktig antall utskrifter

Følgen starter med a₁=5 og øker med 4. Skriv ut nøyaktig 6 ledd og forklar range-grensene. Indekskontroll 1: riktig antall utskrifter. Punktene er diskrete ledd, ikke en kontinuerlig funksjonsgraf. a₁=5, aₙ=aₙ₋₁+(4) Faglig idé

range(2,N+1) representerer indeksene 2 til N.

Metodevalg

Modellen beregnes trinnvis og kontrolleres med en selvstendig kodekjøring.

1. Skriv ut startverdien som ledd 1.
2. Oppdater deretter count−1 ganger.
3. Kontroller lengden på listen og siste indeks.

Listen har 6 ledd og siste verdi er 25. Python-kontroll – faktisk kjørt

a=5 vals=[a] for n in range(2,7): a=a+(4) vals.append(a) print(vals) assert len(vals)==6 assert vals[-1]==25

Kjørt utskrift: [5, 9, 13, 17, 21, 25]

Vanlig feil: range(2,N) stopper før N. Sensorblikk: Kommenter hva variabelen a representerer i hver iterasjon.

Se alle tre modelløsningene i seksjonen

3. Additive rekursjoner og variable tillegg

I en additiv rekursjon legges et fast eller indeksavhengig bidrag til forrige ledd. Konstant tillegg gir en aritmetisk utvikling, mens et tillegg som avhenger av n kan gi kvadratiske eller høyereordens mønstre.

Kjernepunkt: Undersøk differansene og forklar hva hvert tillegg representerer. Additive rekursjoner og variable tillegg. Figuren viser arbeidsrekkefølgen og erstatter ikke den matematiske begrunnelsen. Modelløsning 7 Seksjon 3

Additiv modell 1

En følge har a₁=6 og aₙ=aₙ₋₁+(2). Finn a_12 rekursivt og kontroller med en eksplisitt formel. Additiv modell 1. Punktene er diskrete ledd, ikke en kontinuerlig funksjonsgraf. aₙ=a₁+(n−1)d Faglig idé

Konstant tillegg gir lineær utvikling i indeksen.

Metodevalg

Modellen beregnes trinnvis og kontrolleres med en selvstendig kodekjøring.

1. Iterer fra ledd 2 til ønsket ledd.
2. Bruk den samme differansen i hver runde.
3. Kontroller med aₙ=a₁+(n−1)d.

a_12=28. Python-kontroll – faktisk kjørt

a=6 for k in range(2,13): a=a+(2) explicit=6+(12-1)*(2) print(a, explicit) assert a==explicit==28

Kjørt utskrift: 28 28

Vanlig feil: Å bruke n steg i stedet for n−1. Sensorblikk: Bruk rekursjonen i hovedmetoden og eksplisitt form som kontroll.

Se alle tre modelløsningene i seksjonen

4. Multiplikative rekursjoner og prosentvis endring

Når hvert nytt ledd er en fast faktor ganger det forrige, beskriver rekursjonen gjentatt prosentvis vekst eller nedgang. Fortegn, størrelsen på faktoren og startverdien avgjør om følgen vokser, avtar eller alternerer.

Kjernepunkt: Skill mellom prosent, prosentpoeng og vekstfaktor. Multiplikative rekursjoner og prosentvis endring. Figuren viser arbeidsrekkefølgen og erstatter ikke den matematiske begrunnelsen. Modelløsning 10 Seksjon 4

Multiplikativ modell 1

Startverdien er a₀=5, og aₙ=1.2aₙ₋₁. Finn a_8 og beskriv utviklingen. Multiplikativ modell 1. Punktene er diskrete ledd, ikke en kontinuerlig funksjonsgraf. aₙ=r aₙ₋₁ Faglig idé

Faktoren virker på hele forrige tilstand.

Metodevalg

Modellen beregnes trinnvis og kontrolleres med en selvstendig kodekjøring.

1. Oppdater med vekstfaktoren for hvert tidssteg.
2. Behold nok desimaler underveis.
3. Tolk om følgen vokser, avtar eller alternerer.

a_8≈21.4991. Python-kontroll – faktisk kjørt

a=5 vals=[a] for k in range(1,9): a=a*(1.2) vals.append(a) print(vals) assert abs(a-(21.49908479999999))<1e-10

Kjørt utskrift: [5, 6.0, 7.199999999999999, 8.639999999999999, 10.367999999999999, 12.441599999999998, 14.929919999999996, 17.915903999999994, 21.49908479999999]

Vanlig feil: Å legge til prosenttallet i stedet for å multiplisere med vekstfaktoren. Sensorblikk: Tolk fortegn og størrelsen på faktoren.

Se alle tre modelløsningene i seksjonen

5. Affine rekursjoner: beholdning og fast bidrag

Modeller av typen a_n=r a_{n-1}+b kombinerer en andel som videreføres med et fast bidrag. De brukes blant annet i lagerstyring, miljømodeller, dosering og andre trinnvise prosesser.

Kjernepunkt: Tolk r som beholdt andel og b som bidrag per periode. Affine rekursjoner: beholdning og fast bidrag. Figuren viser arbeidsrekkefølgen og erstatter ikke den matematiske begrunnelsen. Modelløsning 13 Seksjon 5

Affin rekursjon 1

En tilstand følger aₙ=0.8aₙ₋₁+(3) med a₀=0. Finn a_10 og tolk leddene. Affin rekursjon 1. Punktene er diskrete ledd, ikke en kontinuerlig funksjonsgraf. aₙ=r aₙ₋₁+b Faglig idé

Den affine modellen kombinerer videreføring og nytt bidrag.

Metodevalg

Modellen beregnes trinnvis og kontrolleres med en selvstendig kodekjøring. …