Mandag 1/10: Lur leting og regning med tabeller

Vi leter etter "Truls" i en tabell a() med 1 million (N) element

• hvis a() er usortert må vi lete gjennom alle N element før vi erklærer "ikke funnet"
• hvis a() er sortert stigende kan vi avbryte etter posisjon k hvis a(k) > "Truls"
• hvis a() er sortert kan vi gjøre et binærsøk (kap. 7.4). Ved å sjekke a(N/2), midtveis, kan en erklære halvparten av a() som uinteressant. Hver sjekk halverer søkeområdet. Hvis "Truls" ikke er i tabellen har vi gjort log₂ (1,000,000) som er omtrent 20 sjekker (istedetfor å sjekke alle en million).

På tavla stod en tabell R() med { 0, -1, 6, 4 } som innhold. I gruppearbeid laget alle 9 :-( av dere, funksjoner for Sum(R), snitt(R) og median(R).

 Function sum (ByValRef a() as Integer) As Integer
   ' laget av Orjan og Johan
   Dim s as Integer = 0
   For i as Integer = 0 to a.getUpperBound(0)
      s += a(i)
   Next
   Return s
 End Function

 Function snitt (ByValRef x() as Integer) as Double
   ' laget av Orjan og Johan
   Return sum(x) / (x.getUpperBound(0)+1)
 End Function

 Function Median (ByValRef m() as Integer) as Double
   ' klassen viste meg hva median er (s. 376)
   Dim n as Integer = m.getUpperBound(0) + 1
   If isPartall(n)
      Return ... (ikke ferdig)
   Else
      Return ...
   End If
 End Function

 Function isPartall (DimByVal y as Integer) as Boolean
    If y Mod 2 = 0 ...
 End Function

Håpet om å lage funksjonene laveste(R) og høyeste(R) utsettes. Disse funksjonene vil nok kunne legges til tabellomformeren i oblig 5.