Choose jour language!

---

|

SLOŽENOST ALGORITMA.
ZAMENA ITERACIJA FORMULOM

Vreme izvršavanja nekog algoritamskog problema i te kako zavisi od načina na koji je taj algoritam rešen tj. od toga koliko je elementarnih operacija potrebno izvršiti da bi se problem do kraja rešio.
Neke probleme koji se mogu rešiti iterativno, upotrebom petlji obično je moguće rešiti pomoću neke odgovarajuće formule i na taj način vreme izvršenja aplikacije drastično ubrzati, ako je u pitanju velik broj ulaznih podataka. Npr. ako posmatramo sledeći zadatak:

 Atletičari učestvuju na pripremama za takmičenje u trajanju od n dana. Prvog dana priprema sportista pretrči a1 metara, a svakog sledećeg dana za d metara više nego prethodnog dana. Napisati program kojim određuje koliko metara sportista  pretrči poslednjeg dana priprema.

​Ovaj primer može da se reši iterativno upotrebom petlji tako što se u svakom ciklusu čuva koliko je sportista pretrčao tekućeg dana, a da tekući ciklus zapravo simulira tekući dan priprema. Pa ako damo početnu vrednost a=a1, koliko je sportista pretrčao prvog, za svaki sledeći važi:
a=a+d, i to umetnuti u telo for petlje:

#include < stdio.h >

int a, a1;
scanf(“%d%d”,&n, &a1);
a = a1;//Inicijalizuje broj pređenih km(a) na početnu vrednost a1
for(int i=0; i {

a = a+d;

}
printf("%d\n",a);

Vidi se da je za izvršavanje petlje potrebno n-iteracija. Drugi način koji skraćuje znatno vreme izvršenja je da umesto petlje izračunamo broj pređenih km sportiste u poslednjem danu pomoću formule za n-ti član aritmetičkog niza.
Ako brojevima obeležimo pređene kilometre, dobićemo aritmetički niz. Npr. za n=5 i a1=3 i d=2 imali bi niz:
​

3 5 7 9 11,

a to je aritmetički niz čiji je prvi član jednak a1=3, razlika između susednih članova niza d=2, a broj elemenata niza n=5.
n-ti član aritmetičkog niza se može dobiti po formuli
an=a1+(n-1)*d, gde bi se i zbir uloliko je to potrebno mogao odrediti po formuli za zbir elemenata aritmetičkog niza: Sn=n*(a1+an)/2
​

a_n = a₁ + (n-1)*d, gde bi se i zbir uloliko je to potrebno mogao odrediti po formuli za zbir elemenata aritmetičkog niza: S_n=n*(a₁+a_n)/2
Dakle u našem primeru
a₅ = a₁ + 4*d ​

Kod bi onda izgledao:
​

int a, an;
scanf(“%d%d”,&n, &a1);
an + a1+(n-1)*d
printf("%d\n",an);

​Možemo zaključiti da se iterativni postupak može zameniti odgovarajućom formulom. U prethodno primeru je primenjena formula za računanje n-tog člana aritmetičkog niza.
Često koristi i primena kombinatorike za rešavanje takvih algoritamskih problema. Npr. često je potrebno izračunati broj varijacija ili kombinacija bez ponavljanja od n elemenata k-te klase:
Broj varijacija bez ponavljanja od n elemenata k-te klase: 

V_n^k = n * (n-1) *.... * (n-k+1)

​Broj permutacija: 

N=n!=n*(n-1)*(n-2)*...*1

​Broj kombinacija bez ponavljanja od n elemenata k-te klase: 

C_n^k = n * (n-1) *.... * (n-k+1 )/ n!

---

​Sledeći primer ilustruje ovo:

Primer: Dat je binarni string (niska karaktera koja se sastoji od karaktera 0 i 1). Napisati program kojim se određuje broj segmenata (podstring uzastopnih elemenata), dužine najmanje 2, koji počinju i završavaju sa 1.
​

​Neka je dat npr string s:

s=“010010001“

Traženi segmenati koji se može izdvojiti između dve jedinice bi bili sledeći:

010010001
010010001
010010001

​Zadatak se može rešiti iterativnim postupkom, upotrebom petlji ili na drugi način, sa manje elementarnih operacija, ako se primeni formula za broj kombinacija za 3 elementa druge klase. Tri elementa jer je broj jedinica u stringu 3, a klasa je dva jer dve jedinice određuju traženi segment, jedna na početku a jedna na kraju

N=C₃² = n * (n-1)/ n! = 3 * 2/ (2 * 1) = 3

​A to su 3 prikazana segmenta iznad.
Ako uopštimo zadatak da korisnik unese string, kao i da se programski izbroji koliko jedinica ima u unetom stringu, kod bi bio(u jeziku C):

"C" code

#include < stdio.h >

int b = 0;
char c;
while((c = getchar()) != EOF)
{

/*Broji jedinice u stringu*/
if(c=='1')

b++;

}
c = b * (b-1) / 2;/*Broj traženih segmenata*/
printf("%d\n",c);

"C++" code

#include < iostream >
#include < string >
using namespace std;

int b = 0,N;
string s;
cin >> s;

for(char c: s)
{

/*Broji jedinice u stringu*/
if(c=='1')

b++;

}
N = b * (b-1) / 2;/*Broj traženih segmenata*/
cout << N << endl;

Posle učitavanja karaktera u promenljivu c tipa char kroz while petlju, proverava se da li je tekući karakter jedinica. Ako jeste brojač jedinica se uveća za 1.
Po izlasku iz petlje imamo određen broj jedinica u stringu. Broj traženih segmenata je jednak, dalje broju mogućnosti da napišemo početnu i krajnju poziciju na kojoj se nalazi jedinica(broj kombinacija bez ponavljanja od n elemenata k-te klase). Ako formiramo skup mogućih pozicija, koristeći prethodni primer:

N = { 2, 5, 9 }

​Na ovim pozicijama se nalaze pozicije jedinica u datom stringu. Sada dalje formiramo kombinacije početne i krajnje pozicije

2 , 5 -segment: 010010001
2 , 9 - segment: 010010001
5 , 9 - segment: 010010001

Broj kombinacija vidimo da je 3 i to bi dobili pomoću ranije navedene formule za broj kombinacija od n elemenata k-te klase bez ponavljanja gde je u ovom primeru n=3 a k=2. ​Formula dakle glasi:    

c = b * (b-1) / 2;

Druga varijanta rešavanja(lošiji način) je upotrebom petlji:

#include < stdio.h >
#include< string.h >


int br=0,n;
char s[100000];
gets(s);
n=strlen(s);

for(int i=0; i < n-1; i++)
{

/*Početak posmatranog segmenta*/
if(s[i]=='1')
{

for(int j=i+1; j < n; j++)
{

/*trazeni broj segmenta se uvecava za 1 jer smo došli do jedinice na kraju*/
if(s[j]=='1')

b++;

}

}

}
printf("%d\n",b);

---

Prethodno
​|< Rekurzivni algoritmi

---