Primer 1:
Napisati program koji učitani prirodni broj n transformiše tako što mu uklanja nule sa desne strane. Npr. 12000 transformiše u 12.
Program Transform;
var n: integer;
Begin
write ('Unesite broj:' ); readln (n);
while ( (n mod 10) = 0 ) do n:=n div 10;
writeln ( 'Broj je transformisan u ', n );
End.
Primer 2:
Napisati program koji određuje najveći zajednički delilac prirodnih brojeva m i n. (m>n). - Euklidov algoritam
Program NajveciZDelilac;
var m,n,r : integer;
Begin
readln (m,n);
while ( (m mod n) <> 0 ) do
begin
r:= m mod n;
m:= n;
n:= r;
end;
writeln (' NZD je ' , n);
end.
Kompletno objašnjenje Euklidovog algoritma nalazi se ovde.
Primer 3:
Prosti brojevi wikipedia
Eratostenovo sito (wiki eng)
Napisati program koji štampa trocifrene proste brojeve.
Program TrocifreniProsti;
Var i, n, koren : integer;
Begin
n:=101;
while (n<= 997) do
begin
koren:= round (sqrt (n)); {gornja granica za proveru deljivosti nekog trocifrenog broja}
i:= 3;
while ((i<=koren) and (n mod i <> 0)) do i:=i+2;
if (i>koren) then writeln (n:8); {ovaj if je tu da proveri zasto se desio izlazak
iz while ciklusa jer je izlazak mogao da bude zbog toga sto :
1. broj je prost- nema delitelja ili 2. nadjen je delitelj}
n := n+2; {prolazimo kroz neparne brojeve}
end;
End.
Pojašnjenje programa:
Postoji više algoritama za pronalaženje prostih brojeva. Ovaj algoritam po efikasnosti spada u osrednje, ali je opet sa druge strane dovoljno komplikovan da za potpuno razumevanje zahteva dobro znanje matematike. Program za konkretan trocifren (neparan) broj n proveravaće deljivost sa svim neparnim brojevima iz opsega 3.. round (koren (n)) i ukoliko ne nađe delitelj ispisaće broj n. Ukoliko pronađe delitelj program prelazi na proveru broja n+2 itd... Obratimo pažnju da će program proveravati deljivost brojevima 9, 15, 25, 27 .... čak i ako je već proverio da broj n nije deljiv ni brojem 3 ni brojem 5, zato kažemo da algoritam po efikasnosti spada u osrednje.
Zašto proveravamo deljivost samo do korena?
Predpostavimo da proveravamo da li je broj 101 prost. Početna pretpostavka je da je broj složen i da se zbog toga može zapisati kao proizvod barem dva prosta broja. Da li ćemo proveravati deljivost broja 101 brojevima iz opsega 51.. 99 ? Nećemo jer prost broj sigurno nije deljiv sa brojem 2. Ovakva analiza nam služi da algoritamu za određivanje prostih brojeva spustimo gornju granicu za proveru deljivosti tj. da program ubrzamo (kažemo još i optimizujemo). Detaljnijom analizom možemo videti da je dovoljno proveravati deljivost broja n samo od 2 do round (sqrt (n)) jer: jer ako postoji delitelj m broja n i ako je m > round (sqrt (n)) onda se n može predstaviti u obliku n= m * k , i pri tome bi bilo k < round (sqrt (n)). Dakle broj n bi imao delitelj koji je manji od round (sqrt (n)).
Za vežbu napisati algoritme na osnovu ovih programa.