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):
k | k_steg | Utregnet lengde > faktisk lengde? |
---|---|---|
1.0 | 1.0 | Nei |
0.1 | 0.1 | Nei |
0.01 | 0.01 | Ja |
0.02 | 0.01 | Ja |
0.03 | 0.01 | Nei |
0.021 | 0.001 | Ja |
0.022 | 0.001 | Nei |
0.0211 | 0.0001 | Ja |
0.0212 | 0.0001 | Ja |
0.0213 | 0.0001 | Lik |
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.
Jeg ønsker å teste denne koden, hvordan gjør jeg det etter å ha nedlastet den?
Da trenger du en kompilator.
g++ (GNU) eller f.eks. Visual C++ fra Microsoft, dersom du ønsker å kjøre dette under Windows.
Kommer an på operativssystem. I linux har man allerede gcc installert og kan skrive:
g++ kast2.cpp -o kast2
Deretter skriver man ./kast2 for å kjøre programmet.
På mac må man laste ned Xcode før man kan gjøre det samme.
Er ikke sikker på enkleste måten i Windows. Kanskje noen andre kan svare?
En annen mulighet er å laste ned Dev-C++ (IDE inkl. MinGW): http://www.bloodshed.net/devcpp.html
Dette prosjektet er riktignok utdatert, men noe enklere å sette seg inn i enn Microsoft Visual Studio. Installer og kjør. Deretter:
I. File–>New–>Project (Velg Empty Project)
II. File–>New–>Source File
III. Kopier og lim inn kildekoden (løsningsforslaget). Legg til følgende linje like over return 0; i main():
/* CODE */
cin.ignore(‘\n’);
/* END OF CODE*/
Dette er for å hindre at vinduet skal forsvinne med en gang programmet har kjørt ferdig, siden det ikke kjøres gjennom terminal.
IIII. Execute–>Compile & Run (eller CTRL+F9)
s/IIII./IV./
testet programmet, og det det virker som om det kræsjer om det blir kjørt mere enn en gang.
Man kan også laste ned Apple Developer Command Line tools i stedet for hele Xcode på Mac. Mye mindre nedlasting, men man må logge seg på og registrere seg som en utvikler (dette er gratis).
Nedlastingene finner du her (“Command Line Tools for Xcode”): https://developer.apple.com/downloads/
Pingback: Sortering og binærsøk | Bootcamp