Uppgift 9
Algoritmuppgift (=uppgift 9)
-
Ge en tajt O-uppskattning, som funktion av n,
av värstafallstiden för följande fem loopar:
Algorithm Loop1(n):
a = 0
for i = 1 to n
a += i
Algorithm Loop2(n):
b = 1
for i = 1 to 4n
b++
Algorithm Loop3(n):
c = 1
for i = 1 to n2
c--
Algorithm Loop4(n):
d = 5
for i = 1 to 3n
for j = 1 to i
d = d + j
Algorithm Loop5(n):
e = 5
for i = 1 to n2
for j = 1 to i
e = e + j
-
Förklara varför (n+1)3 är
O(n3).
Använd dig av följande definition:
f(n) är O(g(n))
om det finns positiva konstanter c och n0 så att
f(n) ≤ cg(n) för alla
n ≥ n0.
-
Studera följande algoritm och ge en uppskattning av körtiden.
Ange svaret som en funktion av problemstorleken och använd O-notation.
Beskriv i detalj hur du har resonerat.
Vilka grundläggande operationer valde du att räkna?
Hur påverkas körtiden om alla element i vektorn är lika?
Algorithm Reverse(a):
Input: An array a.
Output: The same array with elements reversed.
n = a.length
for i = 0 to n/2
if a[i] != a[n-1-i]
Swap the elements a[i] and a[n-1-i]
return a
Den här delen av uppgiften ska som vanligt lämnas till
din övningsledare på övningen 26/11. För godkänt
måste du ha gjort samtliga deluppgifter. Det är tillåtet
att göra enstaka fel och misstag men det är viktigt att
du försöker lösa samtliga uppgifter.
Slutuppgift i programmering (=uppgift 11)
Slutuppgiften på den här delen av kursen är att skriva
ett äventyrsspel som bygger på projektet i kapitel 7.
Du ska implementera minst fyra, men gärna fler,
av förslagen i uppgift 7.42-7.49.
Uppgiften ska redovisas i två steg. En första spelbar
version ska vara klar senast 26/11. Då ska du låta
någon annan provspela ditt spel och du ska prova
någon annans program. Ni ger kommentarer till varandra
och därefter förbättrar ni spelet. När båda är nöjda
så är det dags att lämna in koden, på papper, till er
övningsledare. Sista inlämningsdag är i samband med
den näst sista övningen 3/12.