24

Numbrite manipuleerimist.

1. Teha programm, mis leiab kolmekohalise arvu, mille tagurpidi kirjutamisel saadud arv on esialgsest 396 võrra väiksem; näiteks 965 - 569 = 396.

Esimene lahendus. Otsime kohe kolmekohalist arvu X ja leiame selle numbrid N1, N2, N3 , kasutades süsteemipredikaati mod, mis annab mooduliga jagamisel saadava jäägi, näiteks 965 mod 100 tuleb 65, mille esialgsest arvust lahutamisel saamegi sajaliste numbri.

Et arvutuste alates arvul X juba väärtus oleks, kasutame (lõpprekursiivset!) generaatorit vahel(Algus,X,Lopp), mis genereerib kõk arvud vahemikus Algus...Lopp.

vahel(A,A,L).
vahel(A,X,L) :-

A1 is A+1,
A1 =< L,
!, /* see hoiab ära tagurdamise, kui eelmine tingimus enam ei kehti */
vahel(A1,X,L).

Et predikaat arvuta esitaks kõik lahendused, sunnitakse see pärast järjekordse tingimust rahuldava arvu leidmist ja väljastamist süsteemipredikaadiga fail (selle väärtus on alati FALSE) tagurdama (s.t. algab backtracking). Kui kõik lahendid on leitud, lõpetab predikaadi arvuta viimane lause töö ("puhtalt", s.t. ilma ebaõnnestumiseta).

arvuta:-

vahel(100,X,999),
K1 is X mod 100,
N1 is (X-K1)//100, /* süsteemipredikaat // teisendab jagatise alati täisarvuks, reaalarvuga annaks süsteemipredikaat mod hiljem vea */
X1 is X-100*N1,
K2 is X1 mod 10,
N2 is (X1-K2)//10,
N3 is X1-10*N2,
Y is 100*N3+10*N2+N1,
Z is X-Y,
Z = 396,
write(X),
nl,
fail.

arvuta.


Teine lahendus. Otsime kolmekohalise arvu numbreid N1, N2, N3; algul tuleb muidugi selgitada, mis on number; seda võiks teha kas "otse" deklareerides
num(0).
num(1).
...

kuid võib ka kasutada ülalkirjeldatud predikaati vahel:

num(X):-

vahel(0,X,9).

Lahendus on veel sirgjoonelisem kui eelmine:

arvuta1 :-

num(N1), N1>0,/* muidu ei oleks arv kolmekohaline! */
num(N2),
num(N3),
A1 is 100*N1+10*N2+N3,
A2 is 100*N3+10*N2+N1,
Z is A1-A2,
Z = 396,
write(A1),
nl,
fail.

arvuta1.

2. Ka krüptogrammide, näiteks


  EIN	  SEND     VATER   FOURTY	  
+ EIN   + MORE  + MUTTER      TEN
+ EIN   ------	 -------      TEN
+ EIN    MONEY	  ELTERN  -------
------                      SIXTY
 VIER

lahendamine (iga täht tähistab mingit numbrit 0..9, erinevad tähed tähistavad erinevaid numbreid ja arvud ei alga 0-ga) on eelmise lahenduse sarnane, näiteks ülaltoodud esimese krüptogrammi lahendid leiab predikaat:

leia(E,I,N,V,R):-

num(E), E>0,
num(I), not(I=E),
num(N), not(N=E),not(N=I),
num(V), V>0, not(V=E),not(V=I),not(V=N),
num(R), not(R=E),not(R=I),not(R=N),not(R=V),
A1 is 4*(100*E+10*I+N),
A2 is 1000*V+100*I+10*E+R,
A2 = A1.

(sellel krüptogrammil on vaid 1 lahend!).

Ûlesandeid.

1. Tee predikaadid ülaltoodud teiste krüptogrammide lahendamiseks.

2. Tee programm, mis leiab kõrvalolevas arvlabyrindis silmusteta tee, millel läbitud ruutude kogusumma oleks 59.

3. Tee programm, mis paigutab 3x3 maatriksisse numbrid 1..9 (kõik erinevad) nii, et numbrite summa kõigis horisontaal- ja vertikaalridades oleks sama, näiteks nii:

8 1 6
3 5 7
4 9 2
(nn maagiline ruut, selliseid kasutatakse katsete planeerimises).
Küsimused, probleemid:
jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde