Algoritmi i strukture podataka - II KOLOKVIJUM 5.02.2007.
NAPOMENA: Svi zadaci sem treceg su vec uradjeni na
vezbama!!!
1. Zadat je
prirodan broj n i pozitivni realni
brojevi c, wi i pi(i=1,2,…,n) pri čemu
je sa c označena vrednost
kapacitet nekog ranca, sa wi
su označene težine predmeta koje se mogu staviti u ranac, dok pi
su vrednosti tih predmeta. Predmeti se mogu rezati. Potrebno je odrediti realne
brojeve xi (i=1,2,…,n)
koji označavaju koji se deo i-tog predmeta stavlja u ranac tako da
ukupna težina predmeta stavljenih u ranac, ∑i=1...n wi*xi
, ne bude veća od c, a da ukupna vrednost predmeta ranca ∑i=1...n
pi*xi bude maksimalna.
l
IDEJA:
za svaki predmet se
izračuna profitabilnost pi/wi (vrednost po jedinici težine). Predmeti se
sortiraju silazno po profitabilnosti te se u tom redosledu stavljaju u ranac
dokle ima mesta. Kod svakog stavljanja u ranac nastoji se staviti što veći
deo predmeta.
/* prethodno su nizovi sortirani po
profitabilnosti */
#define MAXLEN
30
float
w[MAXLEN], p[MAXLEN], x[MAXLEN];
void
smestanjePredmeta (int n, float c) {
float cu;
int i;
for (i=1;
i<=n; i++) x[i] = 0.0;
cu = c;
for (i=1;
i<=n && cu>0; i++) {
if
(w[i] > cu) {
x[i]
= cu/w[i];
return; }
x[i]=1.0;
cu -=
w[i];}
return; }
Primer: n=3, wi=(2,3,4),
pi=(1,7,8), c=6. Profitabilnosti predmeta pi/wi=(1/2,7/3,2). Algoritam stavlja
u ranac ceo drugi predmet, pa ga popunjava s ľ trećeg predmeta, te je rešenje
xi=(0,1,3/4) i maksimalna vrednost u rancu je 13.
2. Dat je
neusmereni povezani graf G=(V,E) sa n
čvorova. Potrebno je ustanoviti da li u grafu G postoji trougao (tj. takva
tri čvora da između svaka dva od njih postoji grana). Konstruisati
algoritam složenosti O(nlog2 7) koji daje
odgovor na ovo pitanje.
Neka je A matrica
povezanosti grafa G. Posto je graf G neusmeren,
matrica A je
simetricna. Razmotrimo vezu elemenata matrice B =AA (proizvod matrica) i grafa G. Prema definiciji
proizvoda matrica je
B[i; j] =
Iz ove jednakosti sledi
da je uslov B[i;
j] > 0 ispunjen
akko postoji indeks k,
takav da su oba elementa
A[i;
k] i A[k; j] jedinice. Drugim recima, B[i; j] > 0
je ispunjeno ako i samo
ako postoji cvor vk, takav da je k != i, k != j i da su
oba qvora vi i vj povezana sa vk. Prema tome, u grafu postoji trougao koji sadrzi
temena vi i vj akko je vi povezan sa vj i
B[i;
j] > 0. Konacno,
u G postoji trougao
akko postoje takvi
indeksi i, j da je A[i; j] = 1 i B[i; j] > 0.
Navedena analiza sugerise
algoritam. Treba izracunati matricu B = A A
i proveriti ispunjenost
uslova A[i;
j] = 1, B[i; j] > 0 za sve parove(i; j). Slozenost provere ovog uslova
je O(n2), te
preovladjujuci deo vremenske slozenosti algoritma potice od mnozenja matrica.
Time je problem nalazenja trougla u grafu sveden na problem mnozenja matrica.
Za mnozenje matrica moze se iskoristiti Strasenov algoritam i tako dobiti
algoritam za nalazenje trougla u grafu slozenosti O(n2:81).
3. Odredite pomocni niz za KMP algoritam za
uzorak P=cgccgcg iz 2 slovne azbuke {c,g}.
STRANA 119 u knjzi: algoritam i primer
H[i]: 001123
4. Implementirajte
rekurzivnu funkciju za INORDER obilazak binarnog stabla, a potom
implementirajte iterativnu (nerekurzivnu) verziju funkcije koja realizuje
INORDER obilazak binarnog stabla.
Neka je stablo
uvedeno kao:
typedef struct cvor { int
broj; struct cvor *levo, *desno;
} drvo;
Rekurzivna
verzija:
void pisi_lkd
(drvo* koren) { /* Infiksno
ispisivanje. */
if (koren) {
pisi_lkd (koren->levo); printf ("%d
", koren->broj); pisi_lkd (koren->desno);
}
}
Iterativna
verzija:
void
INORDER_I(drvo *koren)
{
drvo *cvor;
cvor=koren;
while (1)
{
while (cvor) //spustanje u stablu po lancu
levih pokazivaca
{
PUSH(stek, cvor);
cvor=cvor->levo;
}
//kad se dodje do praznog levog
podstabla, uzima se cvor sa vrha steka i posecuje (stampa)
if (!prazan(stek))
{
cvor=POP(stek);
printf(”%d”, cvor->broj);
cvor=cvor->desno;
//ponavlja se postupak za desno podstablo
}
else return; //algoritam zavrsava
rad kad se stek isprazni
}
}
5. Konstruisati algoritam linearne složenosti
koji za datih n
tačaka i datu pravu p
pronalazi pravu paralelnu sa p koja dati skup tačaka deli na dva podskupa jednake
veličine (tačka prave se može uračunati u bilo koji od
podskupova).
Jednačina
prave p: y=ax + m
Jednačina prave q paralelne sa p: y=ax + m'
Za k=1..n
rastojanje tačke A(xk,yk) od tačkeA'(xk,axk
+ m')
(A' je projekcija od A u vertikalnom smeru na pravu q u pravcu y-ose)
jeste:
d(A,A')=dk=yk-axk -m' (dkje
pozitivno/negativno ako je tačka iznad/ispod prave q)
Da bi se zadovoljio zahtev iz formulacije onda se m' bira tako da polovina
brojeva dk bude veća ili jednaka od nule. Zapravo to znači
da polovina brojeva yk-axk će biti veća ili
jednaka od m' .
Otuda, za k=1..n se problem svodi na traženje medijane za yk-axk,o
čemu je bilo reči kod rangovskih statistika u petoj glavi. To jest
tada se ukazalo da algoritam rangovskih statistika moze naci n/2-ti po velicini
clan za O(n) vreme. Otuda je ovaj algoritam linearne slozenosti.
Izrada
zadataka:180 min
Svaki zadatak
vredi po 10 poena.