- COMP.CS.300
- 4. Pala kerrallaan ja hajoita-ja-hallitse
- 4.5 Aktiivisuus
Aktiivisuus¶
Harjoitukset kurssiaiheeseen 3¶
Tehtävä 1 - Sukat¶
Olet juuri pessyt täyden pesukoneellisen mustia sukkia. Koneessa oli vain mustia sukkia, jokaiselle sukalle on pari, jokainen sukkapari on hieman toisista sukkapareista erilainen, eikä yksikään sukka hävinnyt pesun aikana. Nyt sinun pitäisi löytää jokaiselle sukalle pari. Miten kuvailisit sukkien parien etsinnän prosessin “algoritmisesti”? Kuinka nopeasti parienetsintä sujuu parhaassa tapauksessa (ja millainen on paras tapaus?) Entä kuinka nopeasti parien etsintä sujuu huonoimmassa tapauksessa?
Tehtävä 2 - Jono¶
Oletetaan, että A on kiinteäkokoinen taulukko (array). Miten ja mitä seuraavat algoritmit laskevat? Mitä asioita tulisi ottaa huomioon, jos algoritmi toteutettaisiin C++:lla?
1 2 3 4 5 6 7 8 9 10 11 | QueuePush(A,x):
IF QueueSize(A) = n THEN
RETURN "queue is full"
END IF
A[QueueEnd(A)] := x
QueueEnd(A) := QueueEnd(A) + 1
IF QueueEnd(A) > n THEN
QueueEnd(A) := 1
END IF
QueueSize(A) := QueueSize(A) + 1
RETURN
|
1 2 3 4 5 6 7 8 9 10 11 | QueuePop(A):
IF QueueSize(A) = 0 THEN
RETURN "queue is empty"
END IF
x := A[QueueBegin(A)]
QueueBegin(A):= QueueBegin(A) + 1
IF QueueBegin(A) > n THEN
QueueBegin(A) := 1
END IF
QueueSize(A) := QueueSize(A) - 1
RETURN x
|
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.
Palautusta lähetetään...