Pošto je prostor u ovim "Računarima" neuobičajeno ograničen, preskočićemo uvod i preći na program sa slike 1. Radi se zapravo o konkatenaciji četiri programa koji (respektivno) generišu permutacije, varijacije i kombinacije bez ponavljanja te kombinacije sa ponavljanjem. Upotreba programa je vrlo jednostavna: startujete ga, izaberete odgovarajuću stavku iz menija, unesete tražene podatke i pročitate (ili odštampate) željene sekvence. Program nismo opterećivali mnoštvom IF-ova tako da su rezultati u slučaju zadavanja nemogućih ili trivijalnih problema nepredvidljivi.
Program sa slike 1 je pisan u standardnom bejziku i na prvi pogled deluje nestrukturirano. Program je nastao prevođenjem odgovarajućih paskal procedura na najpopularniji kompjuterski jezik što znači da ga je relativno lako pretvoriti u algoritam odnosno program na nekom drugom programskom jeziku. Proceduru sa slike 2 koja generiše permutacije sa ponavljanjem nismo uspeli da racionalno prevedemo na bejzik (suviše je rekurzivna) pa ga dajemo "u originalu".
Slika 3 prikazuje vremena izvršavanja (generisanje bez ispisivanja) pojedinih procedura na raznim mašinama: BBC je BBC B sa 6502 dodatnim procesorom, AT je IBM PC AT kompatibilan računar (mikroprocesor 80286) koji radi na 8 MHz a UNIX jedna razvojna mašina sa mikroprocesorom 68020 koji radi na 16 MHz. Test 1 su permutacije bez ponavljanja od 7 elemenata, test 2 varijacije bez ponavljanja pete klase od 8 elemenata, test 3 kombinacije bez ponavljanja sedme klase od 15 elemenata a test 4 permutacije sa ponavljanjem od 12 elemenata gde se dva puta po dva ponavljaju; zbog dimenzija problema (treba generisati gotovo 120 miliona permutacija) ovaj je test izvršen samo na UNIX mašini.
Na svim smo računarima koristili potpuno isti bejzik program (prenosili smo ga posredstvom RS 232 interfejsa) ali je, jasno, kvalitet interpretatora bitno različit (posumnjali smo, na primer, da UNIX vrši internu kompilaciju kada se otkuca RUN) tako da iz benčmark testova ne treba izvlačiti previše dalekosežne zaključke.
Pre nego što se osvrnemo na priloge koje smo dobili, odaćemo priznanje čitaocima "Računara" koji su zaslužni za programe sa slika 1 i 2. Procedure za generisanje varijacija bez ponavljanja i obe verzije kombinacija su delo Đorđa Ljubičića iz Beograda, šampion rekurzija na bejziku (program za kombinacije) je Boris Stanojević dok je program sa slike 2 sastavio Predrag Miletić. Program za generisanje varijacija sa ponavljanjem koji smo objavili u "Računarima 24" je, najzad, delo urednika ove rubrike; sastavljen je i testiran na IBM-u 360 davne 1979 godine!
Moramo da priznamo da uopšte nije bilo lako pregledati i rangirati priloge - iako smo eksplicitno tražili vremena potrebna za rešavanje test problema, mnogi su čitaoci ove podatke ignorisali (uz objašnjenja poput ja imam Atari 512 pa vam vremena na njemu ništa ne znače), sakrili na petnaestoj stranu rukom pisane dokumentacije ili čak naveli u nerazumljivoj formi (zar vreme može da bude nerazumljivo? Kako biste pročitali broj 28:62'' ili, još bolje, 2:14?). Vremena izvršavanja procedura koje smo testirali su bila bitno različita tako da je za generisanje permutacija od 7 elemenata nekim programima bilo potrebno i par časova!
Vuk Simović se bavio isključivo generisanjem permutacija bez ponavljanja i to na Amstradu 464 i došao do vrlo originalnog algoritma. Algoritam je preveden u paskal program koji je, na žalost, mnogo duži od verzije koju mi objavljujemo (vreme izvršavanja nije naglašeno).
Za permutacije je bio zainteresovan i Dragan Jovanović, vlasnik Spektruma. Test primer 1 se, primenom njegovog programa, izvršava za 36 minuta što je samo na izgled mnogo - na paskalu se ista procedura izvrši za 25 sekundi!
Dejan Miljković se bavio varijacijama, kombinacijama i bejzikom. Algoritmi su interesantni ali relativno spori - preko 20 minuta za test primer 1, doduše na Commodore 64.
Marko Vuković se bavio isključivo generisanjem kombinacija i sastavio programe koji su interesantni ali sporiji od onih koje objavljujemo.
Dardan Vokshi je rešio sve zadate probleme koristeći logične algoritme koji nisu brzinski šampioni - primer 1 se izvrši za sat ipo (nije nam jasno na kom računaru).
Stevan Kordić je takođe rešio sve probleme ali vremena izvršavanja i specifikaciju hardvera nismo uspeli da pronađemo u opsežnoj dokumentaciji.
Dragan Sretenović je poslao programe koji su do poslednjeg trenutka konkurisali za objavljivanje - algoritmi su dobro objašnjeni a programi logični. Na žalost, jedna od procedura koju smo otkucali nije radila na našem računaru a kolega Sretenović nije specificirao vremena za rešavanje test problema.
Ostalo je još da pomenemo prilog Pintera Antala iz Subotice. Kolega Pinter je, ukoliko nas sećanje dobro služi, učestvovao na našem davno prošlom konkursu sa sličnim prilogom i ozbiljno konkurisao za nagradu. Komisija je tada smatrala da su njegovi programi, iako veoma interesantni, nešto sporiji nego što bi trebali da budu što se ovde samo delimično potvrdilo.
Radionica na odmoru
Nastupaju letnji meseci pa će naša Programerska radionica sebi priuštiti (ne)zasluženi odmor - znamo da bi letnji odziv bio slab pa sledeći problem ostavljamo za septembar. Voleli bismo da nam u međuvremenu pišete, komentarišete objavljena rešenja i, naročito, predlažete nove probleme. Adresa znate: "Računari" (za Programersku radionicu), Bulevar vojvode Mišića 17, Beograd.
10 REM
20 REM KOMBINATORIKA
30 REM
40 REM (C) Programerska radionica
50 REM
60 REM "Racunari 27"
70 REM
80 DIM el$(50),izlaz(50),pom(50)
90 CLS
100 PRINT "1. Permutacije bez ponavljanja"
110 PRINT "2. Varijacije bez ponavljanja"
120 PRINT "3. Kombinacije bez ponavljanja"
130 PRINT "4. Kombinacije sa ponavljanjem"
140 PRINT
150 INPUT " Vas izbor? " izb
160 PRINT: PRINT
170 ON izb GOTO 180,410,610,780 ELSE GOTO 90
180 REM Permutacije bez ponavljanja
190 GOSUB 980
200 k=n
210 GOSUB 1030
220 GOSUB 1070
230 FOR i=1 TO k
240 izlaz(i)=i
250 pom(i)=0
260 NEXT i
270 b=0: t=TIME
280 kn=n
290 IF n<>2 THEN 330
300 GOSUB 1250:GOSUB 1320
310 GOSUB 1250:GOSUB 1320
320 GOTO 390
330 n=n-1
340 GOSUB 290
350 GOSUB 1320
360 pom(n)=pom(n)+1
370 IF pom(n)=n AND n=kn THEN 1380
380 IF pom(n)=n THEN pom(n)=0 ELSE GOTO 330
390 n=n+1
400 RETURN
410 REM Varijacije bez ponavljanja
420 GOSUB 980
430 GOSUB 1000
440 GOSUB 1030
450 GOSUB 1070
460 GOSUB 1200
470 GOSUB 1250
480 i=k
490 IF izlaz(i)<>n THEN 530
500 izlaz(i)=1:i=i-1
510 IF i<>0 THEN 490
520 GOTO 1380
530 izlaz(i)=izlaz(i)+1
540 j=0
550 j=j+1:IF j>i-1 THEN 580
560 IF izlaz(i)=izlaz(j) THEN 490
570 GOTO 550
580 IF i=k THEN 470
590 i=i+1
600 GOTO 540
610 REM Kombinacije bez ponavljanja
620 GOSUB 980
630 GOSUB 1000
640 GOSUB 1030
650 GOSUB 1070
660 GOSUB 1200
670 GOSUB 1250
680 i=k
690 IF izlaz(i)<>n-k+i THEN 720
700 i=i-1
710 IF i>=1 THEN 690 ELSE 1380
720 izlaz(i)=izlaz(i)+1
730 IF i=k THEN 670
740 FOR j=i+1 TO k
750 izlaz(j)=izlaz(j-1)+1
760 NEXT j
770 GOTO 670
780 REM Kombinacije sa ponavljanjem"
790 GOSUB 980
800 GOSUB 1000
810 GOSUB 1030
820 GOSUB 1070
830 FOR i=1 TO k
840 izlaz(i)=1
850 NEXT i
860 b=0: t=TIME
870 GOSUB 1250
880 i=k
890 IF izlaz(i)<>n THEN 920
900 i=i-1
910 IF i>=1 THEN 890 ELSE 1380
920 izlaz(i)=izlaz(i)+1
930 IF i>=k THEN 870
940 FOR j=i+1 TO k
950 izlaz(j)=izlaz(j-1)
960 NEXT j
970 GOTO 870
980 INPUT "Koliko elemenata"; n
990 RETURN
1000 INPUT "Koja klasa "; k
1010 RETURN
1020 RETURN
1030 INPUT "Zelite li ispis "; odg$
1040 odg$=LEFT$(odg$,1)
1050 ispis=NOT (odg$="n" OR odg$="N")
1060 RETURN
1070 PRINT
1080 PRINT
1090 FOR i=1 TO n
1100 IF ispis THEN 1130
1110 el$(i)=CHR$(i+ASC("A")-1)
1120 GOTO 1170
1130 PRINT "Unesi element ";i;" ili <CR> ";
1140 INPUT LINE "" el$(i)
1150 IF el$(i)="" THEN el$(i)=CHR$(i+ASC("A")-1)
1160 el$(i)=LEFT$(el$(i),1)
1170 NEXT i
1180 PRINT
1190 RETURN
1200 FOR i=1 TO k
1210 izlaz(i)=i
1220 NEXT i
1230 b=0: t=TIME
1240 RETURN
1250 b=b+1
1260 IF NOT ispis THEN 1310
1270 FOR l=1 TO k
1280 PRINT el$(izlaz(l));
1290 NEXT l
1300 PRINT
1310 RETURN
1320 r=izlaz(kn-n+1)
1330 FOR i=kn-n+1 TO kn-1
1340 izlaz(i)=izlaz(i+1)
1350 NEXT i
1360 izlaz(kn)=r
1370 RETURN
1380 PRINT
1390 PRINT "Ukupno: "; b
1400 PRINT
1410 PRINT "Vreme rada: "; (TIME-t)/100; " sekundi."
1420 END
program permp (input,output);
type niz = array [1..20] of char;
var a, ta : niz;
p: array [1..20] of Boolean;
j,n,b: integer;
odg: Boolean;
odgt: char;
procedure stampa;
var i:integer;
begin
b:=b+1;
if odg then
begin
for i:=1 to n do
write(ta[i]);
writeln;
end;
end;
procedure perm(i,m: integer);
var j,k: integer;
begin
if i<=n then
begin
k:=1;
if i>1 then if a[i]=a[i-1] then k:=m;
for j:=k to n do
begin
if p[j] then begin
ta[j]:=a[i];
p[j]:=false;
perm(i+1,j+1);
p[j]:=true;
end
end
end
else
stampa
end;
begin
write ('Koliko elemenata: ');
readln (n);
write ('Unesite elemente tako da oni');
writeln ('koji se ponavljaju budu sukcesivni');
b:=0;
for j:=1 to n do
begin
readln(a[j]);
p[j]:=true
end;
write ('Zelite li ispis? ');
readln (odgt);
odg:= not ((odgt='N') or (odgt='n'));
perm(1,1);
writeln ('Ukupno: ', b);
end.
|
Kompjuter |
BBC |
AT |
Unix |
|
Test 1 |
2' 28'' |
2' 52'' |
0' 07'' |
|
Test 2 |
6' 10'' |
4' 56'' |
0' 12'' |
|
Test 3 |
1' 54'' |
1' 45'' |
0' 04'' |
|
Test 4 |
- |
- |
8h 30' |