Krüptoritmide lahendamine
Mitmesugused arvude ja numbritega seotud ülesanded aitavad aru erinevatest võimalustest
Prologis ülesande tingimuste kirjeldamiseks ja asjaoludest, mis mõjustavad programmi kiirust.
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 on 65 ja selle 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 . Kuna me tahame kasutada seda predikaati kõigi arvude Algus ja Lopp vahel olevate arvude genereerimiseks, ei või siin kasutada lõiget !; kui järgnevas definitsioonis esimene lause oleks kujul
vahel(A,A,L):-!,
tuleks esimese argumendi väärtuseks vaid A ja predikaat lõpetaks pärast seda töö, s.t. me ei saaks ülejäänud väärtusi.
vahel(A,A,L).
vahel(A,X,L) :-
A1 is A+1,
A1 =< L,
!,
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, %
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.
See viimane lause on vajalik vaid selleks, et Prolog saaks lõpetada; esimese lause lõpus olev fail sunnib Prolog-i tagurdama (backtrack) ja leidma kõik lahendid; kui rohkem lahendeid ei leidu, lõpetab teine lause töö.
Teine lahendus . Otsime kolmekohalise arvu numbreid N1, N2, N3 ; algul tuleb muidugi selgitada, mis on number; seda võiks teha kas "otse" deklareerides
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, !
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. Samal viisil saab lahendada ka krüptoritme, näiteks
EIN
+ EIN
+ EIN
+ EIN
-----
VIER |
ONE
+ ONE
+ ONE
+ ONE
-----
FOUR |
SEND
+ MORE
-----
MONEY
|
VATER
+ MUTTER
------
ELTERN
|
GAUSS
+ RIESE
------
EUKLID
|
FORTY
+ TEN
+ TEN
------
SIXTY |
(iga täht tähistab mingit numbrit 0..9, erinevad tähed tähistavad erinevaid numbreid ja
arvud ei alga 0-ga). Näiteks esimese ülaltoodud krüptoritmi 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),
kitsendused(E,I,N,V,R).
kitsendused(E,I,N,V,R):-
A1 is 4*(100*E+10*I+N),
A2 is 1000*V+100*I+10*E+R,
A2 = A1.
(sellel krüptoritmil on vaid 1 lahend!).
Ülalesitatud "jõumeetodil" lahendus on tegelikult väga aeglane, sest Prolog peab läbi uurima
peaaegu kõik 10^5 lahendusvarianti (kõigi viie muutuja kümme võimalikku väärtust). Palju kiirema lahenduse saame, kui jälgime protseduuri,
mida inimesed kasutavad tulba kujul liitmisel:
EIN
+ EIN
+ EIN
+ EIN
CD
-----
VIER |
(C, D on ülekandenumbrid, liidetavate arvu põhjal C < 4, D < 5). Tulba kujul liitmise algoritmis (viimasest numbrist ettepoole) hakatakse genereeritud numbritele kohe kitsendusi rakendama, seega versioonid hakkavad kiiresti kaduma ja programmi töö muutub mitu korda kiiremaks:
kitsendused1(E,I,N,V,R):-
num(C),C< 4,
num(D),D< 5,
S1 is 4 * N,
S1 is 10 * C+R,
S2 is 4 * I + C,
S2 is 10 * D + E,
S3 is 4 * E + D,
S3 is 10*V + I.
Kitsendusi peab püüdma arvesse võtta nii pea kui võimalik, see vähendab
läbivaadatave variantide arvu ja kiirendab prologi tööd. Näiteks ülaltoodud krüptoritmi
lahendamisel peab olema S > 0, M > 0 ja S+M > 8 (muidu ei saa tekkida viiekohaline summa). Sellepärast defineerime abipredikaadi enumbers/3 (kolmekohalise); enumbers leiab esimese argumendi kohale nimistu erinevatest numbritest; selle pikkus on määratud teise argumendiga (seda predikaati kasutades otsitakse krüptoritmi numbrid S, M ); kolmas argument on nn "keelatud" numbrid, s.t. neid ei tohi kasutada (ülejäänud numbrite otsimisel on näiteks keelatud kasutata S,M väärtusi).
Selline kaheosaline otsimine töötab oluliselt kiiremini kui kõigi muutujate otsimine korraga:
num(0).
num(1).
num(2).
num(3).
num(4).
num(5).
num(6).
num(7).
num(8).
num(9).
enumbers(N,L,M):-
enum(N,[],0,L,M).
enum(N,N,L,L,M):-!.
enum(N,Y,L1,L,M):-
num(X),
not(member(X,M)),
not(member(X,Y)),
L2 is L1+1,
enum(N,[X|Y],L2,L,M).
member(X,[X|_]):-!.
member(X,[_|Y]):-
member(X,Y).
solve:-
enumbers([S,M],2,[]),
M>0,S>0,
S+M > 8,
enumbers([E,N,D,O,R,Y],6,[S,M]),
(C1 is 0; C1 is 1),
(C2 is 0; C2 is 1),
(C3 is 0; C3 is 1),
Y1 is D + E ,
Y2 is 10 * C1+Y,
Y1 = Y2,
E1 is N + R + C1,
E2 is 10 * C2 + E,
E1 = E2,
N1 is E + O+ C2,
N2 is 10 * C3 + N,
N1 = N2,
O1 is S + M + C2,
O2 is 10*M + O,
O1 = O2,nl,
write(' '),
write(S),write(E),write(N),write(D),nl,
write(' '),write(M),write(O),write(R),write(E),nl,
write(M),write(O),write(N),write(E),write(Y).
Ülesandeid:
1.
Tee predikaadid teiste ülaltoodud krüptoritmide lahendamiseks.
2.
Tee programm, mis leiab kõrvalolevas arvlabyrindis silmusteta tee, millel läbitud
ruutude kogusumma oleks etteantud arv (näiteks 69).
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 agu kõrvaloleval joonisel
(nn "maagiline ruut"; neid kasutatakse näiteks katsete planeerimisel)
4.
Järgnevates krüptoritmides tähistab
* mingit paarisnumbrit (0,2,4,6,8),
# - paaritut numbrit
(1,3,5,7,9) ja
% - mingit algnumbrit (1,3,5,7).
**#
x ##
-----
*#*#
*##
-----
#####
|
%%%
x %%
-----
%%%%
%%%%
------
%%%%%%
|
1.
Ylesande tekst
1.
Ylesande tekst
Küsimused, probleemid:
©2004
Jaak Henno
