TILDA, ÖVNING 2

    Länkade listor

  1. ANDRA NODEN BORT

  2. VARANNAN NOD BORT

    Binära sökträd

  3. TRÄDBYGGEN

    Insättning av 4 2 1 6 3 7 5 ger trädet 

                 4

       2           6

    1     3     5     7
    Binärt sökträd: ja
    Balanserat: ja

    Insättning av 5 7 3 6 1 4 2 ger trädet 

                 5

       3           7

    1     4     6       

     2
    Binärt sökträd: ja
    Balanserat: ja

  4. POSTORDERTRÄD

    Inordning + nybygge

    Båda träden ger 1 2 3 4 5 6 7 8 i inordning
    Nya trädet bli en tarm, ytterst obalanserat. 

    
   1
     2
       3
         4
           5
             6
               7

    Preordning + nybygge Första trädet i preordning ger 4 2 1 3 6 5 7 och nytt träd blir 

    
             4

       2           6

    1     3     5     7
    (samma som ursprungsträdet)

    Andra trädet i preorder ger 5 3 1 2 4 7 6 och nytt träd blir 

                 5

       3           7

    1     4     6       

     2
    (samma som ursprungsträdet)

    Postorder + nybygge

    Första trädet i postorder ger 1 3 2 5 7 6 4 och nytt träd blir 

                                                                
             1                                              
                                                            
                    3                                       
                                                            
               2         5                                  
                                                            
                      4     7                               
                                                            
                           6
    Andra trädet i postorder ger 2 1 4 3 6 7 5 och nytt träd blir 

                                                                
             2                                              
                                                            
      1             4                                       
                                                            
               3         6                                  
                                                            
                      5     7

    Rekursion

  5. GCD

    För att beräkna största faktorn som två tal m och n har gemensamt kan vi använda Euklides algoritm:

    Om m är jämnt delbar med n så är n den största gemensamma faktorn. Annars är GCD(m, n) = GCD(n, m%n). Skriv en rekursiv funktion! 

       def gcd(m, n):
     if m%n == 0:
        return n
     else:
        return gcd(n, m % n)

  6. FIBONACCITAL

    Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta talföljd:
    Sista december föds en kaninpojke och en kaninflicka. Vid två månaders ålder och varje månad därefter producerar varje kaninpar ett nytt kaninpar. Vi kan skriva en rekursiv formel för antal kaninpar: Skriv en rekursiv funktion för att beräkna Fibonaccital. Visa vilka rekursiva anrop den ger upphov till vid beräkningen av f(5). Är det här det effektivaste sättet att beräkna Fibonaccitalen? 

           def fib(n):
           if n <= 1: 
              return n
           else:
              return fib(n-1) + fib(n-2)


    Man kan visa att antalet anrop faktiskt växer snabbare än själva Fibonaccitalen!
    (För N=40 är Fibonaccitalet ca hundra miljoner men antalet rekursiva anrop är över 300 miljoner.)
    Bättre vore här att använda en for-slinga: 

        def fib(n):
         f0 = 0
         f1 = 1
         for i in range(n-1):
	      f2 = f1 + f0
	      f0 = f1
	      f1 = f2
         return f1
    Den här implementationen går i linjär tid, O(n).

  7. REKURSIV TRÄDSUMMA

    Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar.

    Rekursiv tanke: Summan är rottalet plus vänsterträdets summa plus högerträdets summa ... men tomt träd har summan noll. 

       def summa(p):     # Om den står utanför klassen slipper man self
      if p == None: 
         return 0
      else:
         return int(p.value)+summa(p.left)+summa(p.right)

   class Bintree
     - - -
     def sum(self):
       return summa(self.rot)

  8. REKURSIV TRÄDHÖJD

    Ge en rekursiv tanke för höjden av ett träd. Höjden är den maximala nivån som nån av trädets noder befinner sig på. Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1.
    Rekursiv tanke: Höjden är 1 + max(höjden av vänsterträdet, höjden av högerträdet) ...men tomt träd har höjden -1. 

       def height(p):
      if p == None: 
         return -1
      else:
         h1 = height(p.left)
         h2 = height(p.right)
         return max(h1,h2) + 1

    Komplexitet

  9. KÖRTIDER

    En viss algoritm tar 0.5 ms när antal indata är 100. Hur lång kommer körtiden att bli när antal indata är 500 om man vet att körtiden är: 

    Linjär    k * N 	

N = 500   k * 500 = x
          -------------
N = 100   k * 100 = 1/2

             5
         x = - = 2.5 ms  (5x längre)
             2 

O(NlogN)  k * NlogN 	

N = 500   k * 500 * log(500) = x
          ------------------------
N = 100   k * 100 * log(100) = 1/2

              5 * log(500)
          x = ------------  = 3.37 ms  (6.74x längre)
              2 * log(100)

kvadratisk   k * N * N 	

N = 500   k * 500 * 500 = x
          -------------------
N = 100   k * 100 * 100 = 1/2

              5 * 5
          x = ----- = 12.5 ms   (25x längre)

                2

kubisk    k * N * N * N 	

N = 500   k * 500 * 500 * 500 = x
          -------------------------
N = 100   k * 100 * 100 * 100 = 1/2

              5 * 5 * 5
          x = --------- = 62.5 ms (125x längre)
                  2