Skip to end of metadata
Go to start of metadata

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 10 Next »

Læringsmål:

  • PLACEHOLDER

Pensum:

  • PLACEHOLDER

Rekursive funksjoner er som Inception: Det tar tid før man forstår hva som skjer. Skisser hva som skjer ved en forenkling av hver problemstilling med en rekursjonsdybde på 4. Begynn gjerne ved det innerste funksjonskallet og jobb deg utover.

a)

Fibonaccitallene er definert som følger:

fn=

fn-1 + fn-2hvis n>2
1hvis n = 2
1hvis n = 1

For eksempel er f3 = f1 + f2 = 1 + 1 = 2. Dermed blir begynnelsen av rekken slik: 1, 1, 2, 3, 5, 8, 13, 21... Lag den rekursive funksjonen fibonacci som tar tallet n som parameter og returnerer det n-te elementet i fibonacci-følgen.

b)

Skriv om funksjonen i a) slik at den returnerer en liste over de n første fibonaccitallene. Lag funksjonen fibStore, som bruker funksjonen forklart tidligere, og lagrer fibonacci-følgen i en fil med ett tall per linje.

c)

Lag funksjonen fact som tar tallet n som parameter og returnerer resultatet av den matematiske operasjonen n!. Funksjonen er definert slik:

fn=

1n <= 1
n*fac(n-1)ellers

d)

Lag funksjonen des2bin(descimal) som tar inn et positivt heltall (eller 0) og returnerer den binære representasjonen av tallet som en tekststreng. Funksjonen skal være rekursiv, og for hvert rekursive kall skal funksjonen finne det binære sieret lengst til høyre i resultatet. Funksjonen kan implementeres etter følgende rekursjonsskjema:

des2bin(n) =

'0'n == 0
'1'n == 1
[des2bin(n/2) '0']n partall
[des2bin((n-1)/2) '1']n oddetall

 

Test funksjonen slik:

des2bin (0) 	% '0'
des2bin (1) 	% '1'
des2bin (2) 	% '10'
des2bin (127) 	% '1111111 '

 

e)

Lag funksjonen tower_of_hanoi(n, source, dest, temp). Funksjonen skal skrive ut løsningen på Tower of Hanoi problemet. Se wikipedia for denisjon av problemet. Eksempelutskrift for tower_of_hanoi(3, 1, 3, 2) er:

Flytt fra 1 til 3
Flytt fra 1 til 2
Flytt fra 3 til 2
Flytt fra 1 til 3
Flytt fra 2 til 1
Flytt fra 2 til 3
Flytt fra 1 til 3

f)

Regn ut sin( x ) rekursivt ved at: sin(x) = 3*sin(x/3)-4*(sin(x/3))^3, og at sin( x ) ~ x når x << 1. Du skal ikke bruke den innebygde sinus funksjonen. 

 

Sidetype

Ferdig

Undersider, revidert

Undersider, til revisjon

oppgave

80

0

0

  • No labels