Standardni algoritmi

1. Uvod

Prema obrazovnim ishodima definiranim u ispitnom katalogu potrebno jepoznavati i primijeniti standardne algoritme:

• - za zamjenu sadržaja dviju varijabli
• - za prebrojavanje prema zadanome kriteriju
• - za zbrajanje prema zadanome kriteriju
• - za pretraživanje prema zadanome kriteriju
• - za izračun srednje vrijednosti brojeva
• - za traženje najmanjega i najvećega među (učitanim) brojevima
• - za rad s prirodnim brojevima

2. Zamjena sadržaja dviju varijabli

Ovaj problem u praksi najčešće rješavamopomoću treće (pomoćne) varijable (kao kada želimo sadržaje dviju posuda zamijeniti pa uzmemo treću posudu).

Pomoću treće varijable

ulaz (a,b);
c:=a;
a:=b;
b:=c;
izlaz (a,b);

Objašnjenje:
U treću „posudu”, c, privremeno smo spremili sadržaj jedne varijable (neka je to sadržaj varijable a). Sada slobodno možemo „prepisati” preko sadržaja varijable a novu vrijednost jer smo „napravili kopiju” stare vrijednosti. Dakle, slobodno možemo napisati a:=b;. Sadržaj varijable a postaje jednak sadržaju varijable b. I na kraju „dohvatimo” vrijednost iz pomoćne varijable c i pridružimo je varijabli b.

U tablici pogledajte kako se mijenjaju vrijednosti varijabli a, b i c, nakon izvođenja naredbi. Neka su početne vrijednosti varijabli a = 3, a b = 5:

Bez treće varijable (primjenom zbrajanja i oduzimanja)

ulaz (a,b);
a := a + b;
b := a - b;
a := a - b;
izlaz (a,b);

3. Najmanji od tri unesena broja

ulaz (a, b, c);
najmanji:=a;
ako je b<najmanji onda
                najmanji:=b;
ako je c<najmanji onda
                najmanji:=c;
izlaz (najmanji);

4. Prebrojavanje prema zadanom kriteriju

br:=0;
ulaz ( n);
za b:= 1 do n činiti
    ako je b mod 3 = 0 onda
        br:=br+1;
izlaz (br);

5. Zbrajanje prema zadanom kriteriju

Na primjer, zbroj brojeva iz intervala 1 do n koji su djeljivi s 3

6. Pretraživanje prema zadanom kriteriju

Algoritam koji traži unos broja učenika, njihove bodove u testu i ispisuje učenike koji imaju više od 25 bodova, te broj tih učenika.

broj=0;
ulaz (broj_učenika);
za učenik:= 1 do broj_učenika činiti
{              ulaz (bodovi);
                ako je bodovi>25 onda
                {
                               izlaz (učenik);
                               broj:=broj+1;
                }
izlaz (broj);

7. Srednja vrijednost (unesenih) brojeva

Srednja ocjena nekog predmeta ili učenika

s:=0;
ulaz ( n);
za b:= 1 do n činiti
{
      ulaz (ocjena);
      s:=s+ocjena;
}
srednja:=s/n;
izlaz (srednja);

8. Traženje najmanjega i najvećega među (učitanim) brojevima

Ispis najvećeg broja bodova na nekom testu ili natjecanju:

najveći := 0;
ulaz ( n);
za b:= 1 do n činiti
{
                ulaz (bodovi);
                ako je bodovi>najveći onda
                               najveći := bodovi;
}
izlaz (najveći);

Traženje najnižeg učenika u razredu i ispis njegove visine.

najmanji := 10000;
ulaz ( n);
za b:= 1 do n činiti
{
                ulaz (visina);
                ako je visina<najmanji onda
                               najmanji := visina;
}
izlaz (najmanji);

9. Rastavljanje troznamenkastog broja na znamenke

ulaz (a);
stotica := a div 100;
desetica:=a div 10 mod 10;
jedinica:=a mod 10;
izlaz (stotica, desetica, jedinica);

10. Zbroj znamenki unesenog broja

ulaz (broj);
zbroj:=0;
dok je broj<>0 činiti
{

   zadnja:=broj mod 10;
   zbroj:=zbroj+zadnja;
   broj:=broj div 10;
}
izlaz (zbroj);

11. Euklidov algoritam za traženje NZM dva broja

ulaz (n,m);
dok je n<>m činiti
{
        ako je n>m onda
                    n:=n-m;
        inače
                    m:=m-n;
}
izlaz ( n);

12. Rastavljanje unesenog broja na proste faktore

ulaz  ( n);
f:=2;
dok je n>=f činiti
{
      ako je n mod f = 0 onda
      {
               izlaz (f);
               n:=n div f;
      }
      inače
              f:=f+1;
}

13. Zadatci s provedenih ispita - pisanje algoritama

1. (2012., ljetni rok, zadatak 35.) Jakov ima p prijatelja koje želi počastiti. Počastit će ih s ukupno k kolača. Jakov svoje prijatelje želi počastiti tako da svi dobiju podjednak broj kolača pa ih je poslagao u red. Prvom u redu dao je prvi kolač, drugom u redu dao je drugi kolač i tako redom do posljednjeg (p-tog) prijatelja.

   Nakon toga vratio se na početak reda i nastavio dijeliti kolače istim redom sve dok nije podijelio sve kolače. Očito je da se na ovaj način moglo dogoditi da su neki prijatelji dobili po jedan kolač više od ostalih prijatelja.
   Jakova na kraju zanima koliko je najmanje kolača b dobio svaki prijatelj te koliko je prijatelja m dobilo jedan kolač manje od drugih prijatelja.
   Napišite program u pseudojeziku koji učitava broj prijatelja p i broj kolača k te ispisuje podatke koji zanimaju Jakova.
   
   Analiza
   
   

   p – broj prijatelja
   k – broj kolača
   - svaki prijatelj dobio je najmanja k div p kolača
   - (p - k mod p) prijatelja je dobilo jedan kolač manje
   
   Primjer:
   
   neka je p:=5, a k:=27 => svaki prijatelj dobio je najmanje 27 div 5 = 5 kolača, a 27 - 27 mod 5 = 25 prijatelja je dobilo kolač manje.
   
   Rješenje:
   
   

   ulaz (p, k);
   broj_kolaca := k div p;
   ostalo_je := k mod p;
   ako je (ostalo_je > 0) onda
                   manje := p – ostalo_je;
   izlaz (broj_kolaca, manje);

2. (2012., ljetni rok, zadatak 36.) Jedna specijalna vrsta virusa razmnožava se na način da se svakih sat vremena svaki virus podijeli na točno tri nova virusa. U laboratoriju su nabavili jedan takav virus.
   Napišite program u pseudojeziku koji će ispisivati koliko najmanje sati s djelatnici laboratorija moraju čekati kako bi imali n takvih virusa.
   
   Rješenje:
   
   

   ulaz ( n);
   s:=0;
   ima_ih:=1;
   dok je (ima_ih < n) činiti
   {
        s:=s+1;
        ima_ih:=ima_ih*3;
   }
   izlaz (ima_ih);
   

3. (2012., jesenski rok, zadatak 35.)Mještani su odlučili uz rijeku koja prolazi kroz njihovo mjesto postaviti niz naizmjenično plavih i crvenih klupa s tim da prva klupa u nizu bude plava. Izračunali su da trebaju postaviti točno n klupa. Napišite program u pseudojeziku koji će za učitani broj klupa n ispisati koliko im treba plavih p, a koliko crvenih c klupa.
   
   Rješenje:
   

   
   ulaz ( n);
   c:=n div 2;
   p:= n div 2 + n mod 2;
   izlaz (p, c);

4. (2012., jesenski rok, zadatak 36.)Osoba A je u banku uložila x kuna. Za točno mjesec dana banka će na njezin iznos dodati kamatu u iznosu od p%. Svaki sljedeći mjesec kamata se dodaje na prethodno uvećani iznos. Osobu A zanima koliko minimalno mjeseci treba ostaviti novac u banci kako bi imala na računubar y kuna. Pomognite osobi A i napišite program u pseudojeziku koji će unositi vrijednosti x, p i y te će računati i ispisati minimalni broj mjeseci m iz teksta zadatka.
   
   Rješenje:
   

   ulaz (x, p, y);
   m:=0;
   dok je x<y činiti
   {
                   x:=x+x*p/100;
                   m:=m+1;
   }
   izlaz (m);

5. (2013., ljetni rok, zadatak 35.) Napišite program u pseudojeziku koji učitava tri broja a, b, c i ispisuje najvećega od njih. Učitana tri broja sigurno su različita.
   
   Rješenje:
   
   ulaz (a, b, c);
   najveći:=a;
   ako je b>najveći onda
               najveći:=b;
   ako je c>najveći onda
               najveći:=c;
   izlaz (najveći);
   

6. (2013., ljetni rok, zadatak 36.) Provjeri znanja iz Informatike pristupilo je N učenika. Za ocjenu odličan trebali su postići barem 80 bodova. Napišite program u pseudojeziku kojim će se unositi broj učenika N i broj bodova B svakoga učenika te koji će ispisati broj učenika koji su postigli ocjenu odličan na provjeri znanja iz Informatike.
   
   Rješenje:
   
   ulaz(N);
   s := 0;
   za i := 1 do N činiti
   {
         ulaz(B);
         ako je B >= 80 onda
              s := s + 1;
   }
   izlaz(s);

7. (2013., jesenski rok, zadatak 35.) Za jednu je tortu, između ostaloga, potrebno tri jaja. U hladnjaku imamo J jaja. Napišite program u pseudojeziku koji će učitavati broj raspoloživih jaja J, provjeriti koliko je torti moguće ispeći i ispisati odgovarajuću poruku: „Možete ispeći barem dvije torte”, „Možete ispeći najviše jednu tortu” ili „Ne možete ispeći niti jednu tortu”.
   
   Rješenje:
   
   ulaz(j);
   a :=j div 3;
   ako je (a > = 2) onda
             izlaz ('Možete ispeći barem dvije torte');
   inače ako je (a > = 1) onda
             izlaz ('Možete ispeći najviše jednu tortu');
   inače
             izlaz ('Ne možete ispeći niti jednu tortu'); 

8. (2013., jesenski rok, zadatak 36.) U razredu ima N učenika. Na početku nastavne godine nastavnik Tjelesne i zdravstvene kulture izmjerio je visine svih učenika te ih zapisao na papir. Za potrebe statistike nastavnik treba odrediti najvišega učenika. Napišite program u pseudojeziku koji će unositi broj učenika N i visinu svakoga učenika V, a ispisat će visinu najvišega učenika.

   Rješenje:
   
   ulaz (N);
   max := 0;
   za i := 1 do N činiti
   {
         ulaz(V);
         ako je V > max onda
                 max := V;
   }
   izlaz(max);

9. (2014., ljetni rok, zadatak 35.) Napišite pseudokôd koji će unositi troznamenkasti prirodni broj n i ispisivati njegovu najveću znamenku
   
   Rješenje:
   
   ulaz (broj);
   ako je (broj>=100) I (broj <=999) onda
   {
      stotica:=broj div 100;
      desetica:=broj div 10 mod 10;
      jedinica:=broj mod 10;
      najveća:=stotica;
      ako je desetica>najveća onda
              najveća:=desetica;
      ako je jedinica>najveća onda
              najveća:=jedinica;
      izlaz (najveća);
   }
   inače
     izlaz (‘Niste upisali troznamenkasti broj’);

10. (2014., ljetni rok, zadatak 36.) Hotelski lanac nabavlja ribu. Želi kupiti 100 kg ribe. Napišite program u pseudojeziku koji će unositi masu pojedine ribe sve dok ukupna masa ne prijeđe 100 kg. Program treba ispisati koliko je ukupno komada riba kupio hotelski lanac.
    
    Rješenje :
    
    s := 0;
    k := 0;
    dok je s <= 100 činiti
    {
           ulaz (m);
           s := s + m;
           k := k + 1;
    }
    izlaz (k);

11. (2014., jesenski rok, zadatak 35.) Neka je n troznamenkasti prirodni broj. S x označimo broj sastavljen od prvih dviju znamenaka broja n, a s y broj sastavljen od posljednjih dviju znamenaka broja n. Ako je, primjerice, n = 158, onda je x = 15, a y = 58. Napišite pseudokôd koji će unositi troznamenkasti prirodni broj n i ispisivati veći broj od brojeva x i y.
    
    Rješenje
    
    ulaz ( n); x := n div 10;
    y := n mod 100;
    ako je x > y onda
            izlaz (x)
    inače
            izlaz (y );
    
    
12. (2014., jesenski rok, zadatak 36.)  Napišite program u pseudojeziku koji će učitavati cijele brojeve dok se ne unese 100 pozitivnih brojeva. Program treba na kraju ispisati zbroj svih učitanih brojeva. b := 0;
    
    Rješenje:
    
    s := 0;
    dok je b < 100 činiti
    {
         ulaz ( n);
         ako je n > 0 onda
                  b := b + 1;
                  s := s + n;
    }
    izlaz (s);
    
    
13. (2015., ljetni rok, zadatak 35.) Neka je T broj koji se dobiva iz dvoznamenkastoga broja D tako da se zamijene mjesta znamenkama jedinice i desetice. Napišite program u pseudojeziku koji će učitati dvoznamenkasti prirodan broj D, a ispisati veći od brojeva D i T.
    (Napomena: Ne treba provjeravati je li broj dvoznamenkast.)
    
    Rješenje:
    
    ulaz (D);
    z1 := D div 10;
    z2 := D mod 10;
    T := z2 * 10 + z1
    ako je D > T onda
        izlaz (D)
    inače
        izlaz (T);
    
    
14. (2015., ljetni rok, zadatak 36.) Dva igrača igraju igru u kojoj naizmjence stavljaju kamenčiće na niz polja. Prvi igrač stavlja jedan kamenčić na prvo polje i nakon toga drugi igrač stavlja dva kamenčića na drugo polje.
    U svakome sljedećem koraku igrač koji je na redu stavlja na sljedeće polje dva puta više kamenčića nego što je stavljeno na prethodno polje. Igra završava kada je broj kamenčića koje je stavio neki igrač u posljednjemu koraku veći ili jednak zadanomu broju N.
    Napišite program u pseudojeziku koji će učitati prirodan broj N, a ispisati u kojemu će koraku K završiti igra.
    
    Rješenje:
    
    ulaz (N);
    K := 1;
    B := 1;
    dok je B < N činiti
    {
        B := 2 * B;
        K := K + 1;
    }
    izlaz (K)
    
    
15. (2015., jesenski rok, zadatak 35.) Napišite program u pseudojeziku koji će učitati dvoznamenkasti broj D i ispisati je li zbroj njegovih znamenaka paran ili neparan.
    (Napomena: Ne treba provjeravati je li broj dvoznamenkast.)
    
    Rješenje:
    
    ulaz (D);
    z := D div 10 + D mod 10;
    ako je z mod 2 = 0 onda
        izlaz ('paran')
    inače
        izlaz ('neparan')
    
    
16. (2015., jesenski rok, zadatak 36.) Skupina od N učenika pristupila je provjeri znanja iz Informatike.
    Napišite program u pseudojeziku koji će učitati broj učenika N i ocjenu za svakoga učenika te će ispisati srednju ocjenu cijele skupine.
    
    Rješenje:
    
    ulaz (N);
    s := 0;
    za i := 1 do N činiti
    {
        ulaz (M);
        s := s + M;
    }
    izlaz (s/N)
    
    
17. (2016., ljetni rok, zadatak 35) Na maturalnoj večeri ukupno je D djevojaka i M mladića i svi žele zaplesati. Pleše se u parovima (jedna djevojka i jedan mladić). Budući da broj djevojaka i mladića nije jednak, oni koji nemaju svojega para stajat će sa strane.
    Napišite program u pseudojeziku koji će učitavati broj djevojaka D i mladića M, a zatim će ispisati koliko učenika neće plesati.
    
    Rješenje:
    
    ulaz (D);
    ulaz (M);
    ako je D > M onda
        izlaz (D - M)
    inače
        izlaz (M – D);
    
    
18. (2016., ljetni rok, zadatak 36) Napišite program u pseudojeziku koji upisuje brojeve dok se ne upiše broj 999. Program na kraju treba ispisati umnožak apsolutnih vrijednosti svih upisanih brojeva.
    
    Rješenje:
    
    ulaz (x);
    p := abs(x);
    dok je x <> 999 činiti
    {
        ulaz (x);
        p := p * abs(x);
    }
    izlaz (p);