Göm menyn

Del C: Rekursiva funktioner

Exempel C1

Definiera en funktion som beräknar största gemensamma delaren av två heltal. Funktionen kan matematiskt definieras så här:

             / a           om a=b
             |
  sgd(a,b) = | sgd(a-b,b)  om a>b
             |
             \ sgd(a,b-a)  om a<b

Se svar

Exempel C2

Man kan hitta den största gemensamma delaren med Euklides algoritm. Algoritmen baseras på observation att om r är resten efter heltalsdivision av a med b, så är minsta gemensamma nämnaren mellan a och b samma som minsta gemensamma nämnaren mellan b och r. Problemet reduceras till allt mindre och mindre par av tal och man kan visa att förr eller senare kommer b att vara 0. Motsvarande a är då största gemensamma delaren. Definiera funktionen sgd även med denna metod! Exempel:

  a   b   r
  ----------
  70  42  28
  42  28  14
  28  14  0

Vi ska hitta största gemensamma delaren av 70 och 42. Vi delar 70 med 42 och får 28 som rest (antecknas i kolumnen r). I nästa varv använder vi som a och b gamla värdena på b och r. Resten vid divisionen 42 genom 28 är 14. Resten vid den sista divisionen 28 genom 14 är 0. Alltså är största gemensamma delaren för ursprungstalen motsvarande värde på b i sista raden.

Se svar

Exempel C3

Skriv en funktion summera-tal som summerar talen på en lista! Exempel:

  CL-USER(84): (summera-tal '(5 9 13))
  27

Se svar

Exempel C4

Skriv en funktion medel som beräknar medelvärdet av talen på en lista! Exempel:

  CL-USER(77): (medel '(5 9 13))
  9
  CL-USER(78): (medel '(3 6 5 8))
  11/2

Se svar

Exempel C5

Skriv en funktion summera-kvadrat-tal som summerar kvadraten av talen på en lista! Exempel:

  CL-USER(86): (summera-kvadrat-tal '(1 2 3))
  14

Se svar

Exempel C6

Definiera en funktion summera-sekvens som summerar alla tal som förekommer i en lista, oavsett nivå. Definiera också en funktion summera-träd som summerar alla tal som förekommer i ett binärt träd. Utgå från att endast tal förekommer i strukturerna. Körexempel:

  CL-USER(89): (summera-sekvens '(1 2 (3 (4 5)) 6))
  21
  CL-USER(90): (summera-träd '((2 . (3 . 4)) . 5))
  14 

Utforma dina två lösningar enligt lärobokens mallar för sekvenser respektive binära träd. Går det att anropa sekvenslösningen med ett binärt träd som argument och tvärtom? Vad händer?

Se svar

Exempel C7

Skriv en funktion ordning? som tar två raka listor. Funktionen ska kontrollera om alla element i den första listan finns med i den andra listan i samma ordning. Den andra listan kan dock innehålla extra element. Exempel:

  CL-USER(110): (ordning? '(a b c) '(x a b d c e))
  T
  CL-USER(111): (ordning? '(a b c) '(a x c y b z))
  NIL

Se svar

Exempel C8

Skriv en funktion kombinera-listor som tar två raka listor med tal och returnerar en ny lista som innehåller alla möjliga summor av ett tal från vardera listan. Exempel:

  CL-USER(112): (kombinera-listor '(1 2) '(10 20 30))
  (11 21 31 12 22 32)
  CL-USER(113): (kombinera-listor '(1 2) '(3 4))
  (4 5 5 6)

Som framgår av exemplet är det okej om ett tal förekommer mer än en gång. Ett tips är att skriva en hjälpfunktion kombinera-element som kombinerar ett element med en lista.

Se svar

Exempel C9

Med hjälp av s.k. McLaurin-utveckling kan man beräkna ett närmevärde till e upphöjt till x. Formeln ser ut så här:

                 2    3          n
   x       x    x    x          x
  e  = 1 + -- + -- + -- + ... + --
           1!   2!   3!         n!

Skriv en funktion ex som beräknar e upphöjt till x med hjälp av formeln. Funktionen ska ta två argument, x och n. Ju högre värde på n desto mer exakt blir svaret. Jämför med värdet du får ut från den inbyggda Lisp-funktionen exp som gör samma sak!

Se svar

Exempel C10

Skriv en funktion parenteser som för en godtycklig uttryck (utan punkterade par) returnerar antalet parenteser som behövs för att skriva ut listan. Observera att tomma listan skrivs ut som uttrycket nil. Exempel:

  CL-USER(152): (parenteser 'adam)
  0
  CL-USER(153): (parenteser '())
  0
  CL-USER(154): (parenteser '(a b (c d)))
  4
  CL-USER(155): (parenteser '(a (b (c (nil) e) f) g))
  8

Se svar

Exempel C11

Skriv en funktion löv-lista som från ett binärt träd returnerar en rak lista med alla löv. Exempel:

  CL-USER(156): (löv-lista 'a)
  (A)
  CL-USER(157): (löv-lista '(a . b))
  (A B)
  CL-USER(158): (löv-lista '((a . b) . (c . (d . e))))
  (A B C D E)

Se svar

Exempel C12

Skriv en funktion build som tar en rak lista med symboler och en rak lista med heltal. Vi önskar bygga upp en ny lista av symbolerna på så sätt att varje symbol ska placeras i en dellista och där motsvarande heltal anger vilken dellista i ordningen i den nya listan. Exempel:

  CL-USER(4): (build '(a x p q y b c) '(1 3 2 2 3 1 1))
  ((C B A) (Q P) (Y X))

Exemplet anger att a ska läggas i lista 1, x i lista 3, p i lista 2, osv. Av exemplet framgår att ordningen i varje dellista inte spelar någon roll. Den nya listan ska bestå av så många element som det största talet anger i andra argumentet. Om ingen symbol ska lagras i en viss position blir den dellistan tom. Exempel:

  CL-USER(5): (build '(a e f b) '(1 4 4 1))
  ((B A) NIL NIL (F E))

Se svar

Exempel C13

Skriv en funktion rotera som tar en lista och ett heltal. Heltalet anger hur många steg listan ska roteras. Ett positivt heltal betyder att vi ska rotera åt vänster, dvs flytta element från början till slutet i listan. Ett negativt tal betyder att vi ska flytta element från slutet till början. Exempel:

  CL-USER(1): (rotera '(a b c d e) 1)
  (B C D E A)
  CL-USER(2): (rotera '(a b c d e) -2)
  (D E A B C)

Tips: Titta på exempel B8 och använd dig av de funktionerna.

Se svar

Exempel C14

Vi har en trädstruktur med namn på varje löv där vi har associerat ett avstånd med varje båge. Exempel:

        +---+
        |   |
     20 +---+  5
       /     \
  +---+       +---+
  | A |       |   |
  +---+     3 +---+ 10
             /     \
        +---+       +---+
        |   |       | E |
     12 +---+ 6     +---+
       /     \
  +---+       +---+
  | B |       |   |
  +---+     4 +---+ 6
             /     \
        +---+       +---+
        | C |       | D |
        +---+       +---+

Vi önskar få reda på alla noder som kan nås på ett givet avstånd från roten. Ùnskar vi t.ex. alla noder med avstånd 20 ska vi få löven A (20), B (5+3+12) och D (5+3+6+6) som svar. Ovanstående träd kan representeras så här: ett löv representeras som en symbol och en intern nod representeras som en lista med följande utseende:

  ((avstånd-till-vänster-delträd vänster-delträd)
   (avstånd-till-höger-delträd höger-delträd))

Det innebär att exempelträdet ser ut så här i Lisp:

  (setq träd '((20 . a)
               (5 . ((3 . ((12 . b) (6 . ((4 . c) (6 . d)))))
                     (10 . e)))))

Skriv en funktion avstånd som tar ett träd representerat på ovanstående sätt, samt ett avstånd. Funktionen ska returnera en lista med alla löv som har exakt detta totala avstånd till roten. Exempel:

  CL-USER(11): (avstånd träd 20)
  (A B D)
  CL-USER(12): (avstånd träd 15)
  (E)
  CL-USER(13): (avstånd träd 25)
  NIL

Se svar

Exempel C15

Vi vill kunna bearbeta godtyckliga trädstrukturer på formen:

         A
        /|\
       / | \
      B  C  D
     /   |
    E    F
        /|\
       / | \
      G  H  I

I denna typ av träd finns alltså information både i löv och i noder, och varje nod kan ha godtyckligt många grenar. Trädet representerar vi i Lisp på formen (symbol gren1 gren2 ... grenN) vilket innebär att exemplet ovan ser ut så här:

  (a (b e)
     (c f
        (g h i)(
     d)

Man kan traversera noderna i ett träd enligt bredden först eller djupet först. Vid bredden först börjar man med roten och besöker alla noderna på nästa nivå. När det är klart besöks alla noderna ytterligare ett steg från roten osv. I vårt exempel besöks noderna i ordningen:

  (a b c d e f g h i)

Vid djupet först börjar man med roten. Sedan tar man den första grenen och går igenom den fullständigt innan man tar rotens nästa gren osv. I vårt exempel skulle det bli:

  (a b e c f g h i d)

Skriv två funktioner bredden-först och djupet-först som vardera tar ett träd på formen ovan. Funktionerna ska returnera en lista med alla löven, besökta i den ordning som funktionsnamnet anger.

Se svar


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2004-11-08