1. COMP.CS.300 Tietorakenteet ja algoritmit 1 »
  2. Pala kerrallaan ja hajoita-ja-hallitse »
  3. 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.