Oppgaveteksten ligger her.

I denne oppgaven skulle man først simulere et skrått kast (typisk fysikkoppgave) med luftmotstand. Selve simuleringen foregår etter en oppskrift som er gitt i oppgaven, og var relativt enkel koding.

Deloppgave 2 var vanskeligere. Her er luftmotstandskoeffesienten den ukjente. Det kom mange gode løsninger på dette, og jeg vil kort beskrive de vanligste algoritmene:

Lineært søk med konstant steg: 

Dette er den enkleste algoritmen. Man starter med k = 0, kjører simuleringen og lar k øke med en bestemt verdi (som regel 0.0001) så lenge den utregnede lengden er større enn den faktiske lengden. Siden hver simulering er ganske tidkrevende, vil det ta svært lang tid å komme frem til svaret om den faktiske k er høy. Vi må kjøre simuleringen ekte_k / k_steg ganger, og nøyaktigheten er k_steg.

Lineært søk på hver desimalplass:

Dette er en forbedring av forrige algoritme. Vi starter med k = 0, og lar k øke med en ekstremt grov verdi i første steg (mange startet med 0.1 eller 1.0). Om utregnet lengde er mindre enn den faktiske lengden, vet vi at faktisk k er mindre enn k vi brukte i utregningen. Dermed har vi i praksis bestemt en desimal i k. Nå minker vi k_steg med faktor 10, og søker på neste desimalplass. Et søk kan f.eks forløpe slik (faktisk k = 0.0213):

Denne algoritmen finner svaret relativt fort. Antallet ganger simuleringen kjøres er i verste fall 9 ganger antallet desimalplasser nøyaktighet vi ønsker i svaret. Men vi kan gjøre løsningen enda bedre.

Binærsøk

I praksis er det som foregår for hvert siffer i den forrige algoritmen litt som følgende gjettelek: En venn sier han tenker på et siffer (0 – 9) og du skal gjette dette. For hver gang du gjetter får du vite om du gjettet for høyt eller for lavt. I stedet for å prøve 1, så 2 osv. bør vi prøve på midten med en gang. Prøver vi 5 først, får vi uansett svar utelukket ganske mange muligheter.

Men det er ingen grunn til å begrense oss til en slik gjettelek for hvert siffer. I stedet tar vi hele intervallet k kan ligge i, deler det i to og prøver denne verdien av k. Hver gang halverer vi søkeområdet. Denne algoritmen trenger ca. lg2 (10^N) kjøringer av simuleringen for å finne k med N desimalers nøyaktighet. Dette blir ca. 3.32 simuleringer per desimal.

En liten detalj gjennstår. Det er nemlig ikke slik at vi vet intervallet k ligger i til å begynne med. k kan godt være større enn 1.0. Vi kan raskt finne en øvre grense for k ved å hele tiden doble den k-verdien vi prøver: k = 1.0, 2.0, 4.0 osv.

Løsningsforslag i C++ som benytter denne metoden ligger her.