Tietotekniikan perusteet, syksy 1998

Harjoitus 6 (27.29.10.)

 

1. Käännä seuraava Pascal-kielinen ohjelma MIX-konekoodiksi (käskytaulukko luentomonisteen s. 69):

program collatz(input);

var x : integer;

begin

read(x);

while x <> 1 do

if x mod 2 = 0 then x := x/2

else x := 3*x+1

end.

 

2. Seuraava Prolog-ohjelma määrittelee joidenkin taruolentojen sukusuhteita (father(X, Y) º "X:n isä on Y" jne.):

 

father(elrond, earendil).

father(elros, earendil).

mother(elrond, elwing).

mother(elros, elwing).

mother(earendil, idril).

father(idril, turgon).

father(turgon, fingolfin).

father(gilgalad, fingon).

father(fingon, fingolfin).

 

parent(X,Y) :- father(X,Y).

parent(X,Y) :- mother(X,Y).

 

ancestor(X,Y) :- parent(X,Y).

ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

 

Täydennä ohjelmaa predikaateilla sibling(X,Y) º "X ja Y ovat sisaruksia" ja cousin(X,Y) º "X ja Y ovat serkuksia". Tarvitset aiempien tietojen lisäksi alkeispredikaattia (X \== Y) º "X ja Y eivät viittaa samaan olioon". (Voit kokeilla Prolog-ohjelmointia käytännössä yliopiston atk-keskuksen koneille (esim. "tukki") asennetulla C-Prolog -tulkilla. Tulkki käynnistyy komennolla "prolog", ja vastaamalla tulkin ensimmäiseen "?-" -kehotteeseen komennolla "[user]." (huomaa piste) pääsee kirjoittamaan omaa ohjelmaa. Ylläkuvattujen rivien jälkeen saa esim. kyselyllä "?- ancestor(elrond,X)" selville taruhenkilö Elrondin esivanhemmat. Kun kone on selvittänyt ja tulostanut yhden esivanhemman (esim. "X = earendil"), saadaan seuraava kirjoittamalla tulosrivin loppuun puolipiste (";").)

 3. Todista, että seuraava algoritmi laskee syötteenä annetun ei-negatiivisen kokonaisluvun n neliöjuuren ylöspäin pyöristäen, so. asettaa m ¬ éÖnù.

input n

if n = 0 then output 0

else

m ¬ 1

while m*m < n do

m ¬ m+1

output m.

 

Ohje: Tarkastele erikseen tapaukset n = 0 ja n > 0. Jälkimmäisessä tapauksessa valitse silmukkainvariantiksi ehto n > (m-1)2. Totea, että invariantti on voimassa ennen silmukan ensimmäistä suorituskertaa, ja että siitä silmukan viimeisen suorituskerran jälkeen seuraa ominaisuus m = éÖnù. Tarkasta myös, että silmukan suoritus aina päättyy.

 

Muistutus: Lokakuun viimeisellä viikolla (26.30.10.) ei ole luentoja, eikä seuraavalla viikolla (2.6.11.) demoja.