Uvod
Jedna od najvažnijih osobina dobrog programera (možda i najvažnija), je težnja ka pronalaženju najoptimalnijeg rešenja za dati problem.
Krajnji cilj, u većini slučajeva, nije lako postići, ali, svakako se možemo (i moramo!) potruditi.
Kroz svojevrstan šematski prikaz (uz upotrebu veoma jednostavnog primera), ilustrovaćemo kako ovaj proces često izgleda u praksi.
Problem
Problem koji ćemo koristiti za primer u ovom članku je sledeći: pronađimo koliko puta se u unetom broju ponavlja najveća cifra datog broja.
Recimo, u broju 98888817, najveća cifra (9) ponavlja se jednom, a u broju 41322224, najveća cifra (4) ponavlja se dvaput.
Zadatak nije ni malo težak (ali ni baš skroz jednostavan), a glavni problem je što u programskim jezicima (u većini slučajeva) ne postoji način da se direktno pristupi ciframa brojčanih promenljivih.
Ciframa ćemo lako pristupiti na sledeći način: preko operatora % izdvojićemo desnu cifru (cifru jedinica) ....
int broj = 587;
desna_cifra = broj % 10;
// desna cifra dobija vrednost 7
.... a prostim deljenjem sa 10 (budući da je u pitanju celobrojna promenljiva ....
broj = broj / 10;
// promenljiva broj dobija vrednost 58
.... praktično ćemo ukloniti cifru jedinica iz celobrojne promenljive (osim naravno u slučaju jednocifrenih vrednosti, kada deljenje sa 10 neće vratiti "ništa", već nulu).
Rešenje #1 - Naivno rešenje
Ukoliko nismo u stanju da odmah iznedrimo najoptimalnije rešenje, moramo se prvo potruditi da rešimo problem "nekako" (bilo kako). U takvom slučaju, algoritam koji nastaje u početnom stadijumu obično je vrlo 'grub' i neefikasan i ovakvo rešenje se često naziva "naivno rešenje".
Naravno, kada kažemo da se problem mora prvo rešiti "bilo kako", podrazumeva se ipak da i takvo rešenje mora biti u granicama razuma u smislu memorijskog zauzeća, vremena izvršavanja i kompleksnosti algoritma.
U našem slučaju, naivno rešenje moglo bi izgledati ovako:
- kopiraćemo unetu vrednost da bismo je sačuvali za kraj (jer sam postupak izdvajanja cifara podrazumeva 'uništavanje' početne vrednosti unetog broja)
- potom ćemo dvaput proći kroz cifre unetog broja
- prvi put ćemo, poređenjem cifara, ustanoviti koja cifra unetog broja je najveća (a datu vrednost ćemo zapamtiti)
- u drugom prolasku ćemo prebrojati koliko puta se data cifra pojavljuje
.... čemu odgovara sledeći kod:
#include<stdio.h>
void main()
{
int broj, cifra, p, brojac = 0, max_cifra = -1;
scanf("%d", &broj);
p = broj;
// Pronalazimo najvecu cifru:
while (p > 0)
{
cifra = p % 10;
p /= 10;
if (cifra > max_cifra) max_cifra = cifra;
}
// Proveravamo koliko puta se najveca cifra
// pojavljuje u unetom broju:
p = broj;
while (p > 0)
{
cifra = p %10;
p /= 10;
if (cifra == max_cifra) brojac++;
}
printf("Najveca cifra broja %d je %d.\n", broj, max_cifra);
printf("Broj ponavljanja najvece cifre: %d.\n", brojac);
}
Ovakav program ni izdaleka nije posebno problematičan i neefikasan (sam po sebi) i sasvim bi "mogao da prođe", ali, budući da je u pitanju (kao što smo već naveli) svojevrstan šematski prikaz procesa optimizacije algoritama u optem smislu, nastavljamo sa pretpostavkom da je neprihvatljivo da dvaput prolazimo kroz broj (posle jednog pregleda svih cifara, moramo biti u stanju da damo odgovor na pitanje koliko puta se najveća cifra pojavljuje u unetom broju).
Rešenje #2 - Optimizacija upotrebom pomoćnih struktura podataka
Ukoliko je u implementaciji algoritma prihvatljivo da povećamo memorijsko zauzeće u određenoj meri (na šta ćemo se dodatno osvrnuti posle pregleda oba optimalna algoritma), problem se lako rešava u jednom prolasku kroz cifre broja, upotrebom pomoćnog niza od deset elemenata čiji indeksi od 0 do 9 odgovaraju ciframa dekadnih brojeva:
#include<stdio.h>
void main()
{
int broj, p, max_cifra = -1;
int cifre[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
scanf("%d", &broj);
p = broj;
// Prolazimo jednom kroz cifre promenljive p:
while (p > 0)
{
cifra = p % 10;
p /= 10;
cifre[cifra]++; // Povećavamo vrednost u nizu koja se nalazi
// na indeksu koji odgovara trenutno očitanoj
// cifri (ako je trenutno očitana cifra 4, mi
// praktično "gađamo" poziciju cifre[4] i
// povećavamo "brojač četvorki" za jedan;
// navedeno važi i za ostale cifre)
if (cifra > max_cifra) max_cifra = cifra;
}
// Odgovor na pitanje koliko puta se najveca cifra
// pojavljuje u unetom broju zabelezen je na adresi:
// cifre[max_cifra]
printf("Najveca cifra broja %d je %d.\n", broj, max_cifra);
printf("Broj ponavljanja najvece cifre: %d.\n", cifre[max_cifra]);
}
Međutim, ukoliko ne smemo povećavati memorijsko zauzeće (ne smemo koristiti pomoćne strukture), moramo smisliti još efikasniji algoritam.
Rešenje #3 - Dodatna optimizacija algoritma
Ako je algoritam potrebno "zategnuti" koliko god je moguće u odnosu na krajnje prihvatljiva rešenja (kao što je algoritam #2 koji smo videli), u opštem smislu ćemo najčešće dolaziti u situacije gde se moramo dosta potruditi.
Ipak, u slučaju našeg algoritma sa brojem ponavljanja najveće cifre, nećemo se previše mučiti i lako ćemo zaključiti sledeće:
- kada u određenom koraku očitamo cifru jedinica, doći ćemo u jednu od samo tri situacije: cifra će biti manja od najveće pronađene cifre, veća od nje, ili identična
- ako je trenutno očitana cifra jedinica veća od do tada najveće pronađene cifre, odmah možemo zanemariti sve informacije o prethodno pronađenoj najvećoj cifri (brojač ponovo kreće od 1, tako da se i dalje koristi ista promenljiva)
- ako je pronađena cifra jednaka najvećoj pronađenoj cifri, samo ćemo uvećaćeti brojač za jedan
- ako je pronađena cifra manja od najveće pronađene cifre, zanemarićemo je
.... što ćemo lako pretočiti u konkretnu implementaciju:
#include<stdio.h>
void main()
{
int broj, cifra, p, brojac = 0, max_cifra = -1;
scanf("%d", &broj);
p = broj;
// Prolazimo kroz cifre broja p jedanput:
while (p > 0)
{
cifra = p % 10;
p /= 10;
// Ukoliko smo pronašli novu max_cifru
// možemo u potpunosti zanemariti prethodnu i ....
if (cifra > max_cifra)
{
max_cifra = cifra;
// .... započeti brojanje od 1!
brojac = 1;
}
else
{
// Ako je trenutna cifra identična maksimalnoj
if (cifra == max_cifra)
{
// .... uvećaćemo brojač za 1.
brojac++;
}
}
}
p = broj;
printf("Najveca cifra broja %d je %d.\n", broj, max_cifra);
printf("Broj ponavljanja najvece cifre: %d", brojac);
}
Rešenje je sada skroz 'utegnuto': cifre unetog broja smo posmatrali samo jedanput i, po završetku prolaska kroz cifre, imamo informaciju o broju ponavljanja najveće cifre.
Šta je najoptimalnije rešenje
Na kraju nam ostaje da se pozabavimo pitanjem šta je najoptimalnije rešenje za određeni zadatak? Jednostavnog, nedvosmislenog odgovora i rešenja koje paše u svim situacijama - nema. Optimizacija programa zahteva iskustvo i poznavanje konkretne implementacije u najširem kontekstu.
U obzir moramo uzeti što više stvari: ne samo da li je algoritam optimizovan koliko god je moguće, već i jednostavnost / preglednost koda (što posebno igra ulogu u timskom programiranju, kada na jednom projektu sarađuje više programera), sposobnost / nesposobnost određenog rešenja da bude prošireno ili dopunjeno u situaciji kada se stvore novi uslovi koji do tada nisu postojali i tome slično.
U tom smislu (ako se vratimo na primer sa prebrojavanjem cifara), iako poslednji algoritam koji smo videli jeste najoptimalniji sam po sebi, možda bi u određenoj situaciji (ako zaključimo da se dodatno memorijsko zauzeće može zanemariti), bolji izbor bilo izrazito jednostavno i pregledno rešenje, kao što je algoritam #2 koji koristi dodatni niz.
Sve zavisi od toga kako ćemo proceniti ravnotežu između dodatnog memorijskog zauzeća, povećanja kompleksnosti i ostalih stavki koje smo prethodno naveli: dodavanje niza od 40 bajta (niz od deset int promenljivih) kao u primeru #2, koje je ovde simbolički predstavljalo situaciju u kojoj određeni algoritam unosi nedopustivo povećanje memorijskog zauzeća, zbog čega ga je bilo potrebno optimizovati - u praksi je praktično zanemarljivo i ne bi bilo na teret algoritma #2 (pa bismo odluku doneli na osnovu ostalih okolnosti).
Nije uvek ovako lako doći do najoptimalnijeg rešenja, ali, temeljitim proučavanjem teorije programiranja (algoritama i struktura podataka) i uz iskustvo koje se stiče pisanjem velikog broja kvalitetnih programa, polako i postepeno dolazićete do sve boljih i boljih rešenja za programerkse probleme koje treba rešiti ....