Algoritmi i strukture podataka 13.02.2007. (Izrada zadataka:240 min. Svaki zadatak vredi po 20 poena.)

SVI ZADACI SEM TRECEG pod D SU SA VEZBI (Web-a). Zadatak 3 D) je preuzet iz knjige (poglavlje 6.2)

REŠENJA:

1.

slovo	A	N	S	D	I	T	L	R	H	U		V	J	E
kôd	000	001	0100	0101	0110	0111	1000	10010	10011	101	110	11100	11101	11111

L=83 bita

ASCII 7-bitni = 7*22=154

8-bitni 8*22=176

2.

Neka u prvom skupu ima k, a u drugom s-k elemenata.

1. Sortirajmo oba skupa u rastucem redosledu i oznacimo elemente prvog skupa posle sortiranja sa a1 a2 ... a_k.
Oznacimo elemente drugog skupa posle sortiranja sa b1 b2 ....b_n-k

2. Za svako i takvo da 1 <= i <= s - k: niz a1 + bi, a2 + bi, . . . , ak + bi je rastuci, pa se
binarnom pretragom pomocu O(log s) (preciznije [log k]+1) uporedjivanja medjuu ovim brojevima
pronalazi R, ili se utvrdjuje da ni jedan od njih nije jednak R.

Znaci, za proveru svih parova a_i + b_j dovoljno je O(s log s) uporedjivanja

SLOZENOST algoritma:
slozenost pocetnog sortiranja u koraku 1 je O(s log s)
za proveru svih parova a_i + b_j u koraku 2 dovoljno je O(s log s) uporedjivanja,

pa je ukupna slozenost algoritma O(s log s).

3.

A RESENJE. Složenost algoritma KMP O(n) zavisi od duzine teksta, a pomocni niz se trazi za O(m) tj. zavisi od velicine uzorka.

B RESENJE: On je primer „podeli pa vladaj“, dok backtracking je strategija sa traganjem unazad.

C RESENJE: Dovoljno je 7 mnozenja. Vdeti primer 8.5.2. iz knjige ili primer A3 sa vezbi

D RESENJE: Videti lemu 6.2 u knjizi.

4.

Pretpostavimo da je stablo građeno tako da je informaciono polje (ključ) desnog sina veće ili jednako od informacionog polja (ključa) oca.

Sledbenik zadatog čvora je čvor sa najmanjim ključem koji je veći od ključa datog čvora.

Koji čvor nema sledbenika? Samo najdešnji čvor u stablu (koji nema desnog sina i koji je desni sin svog oca), jer je on čvor sa maksimalnom vrednošću ključa. (Na primer a=12)

Karakteristični slučajevi za čvor v čije informaciono polje (ključ) ima vrednost elementa a iz skupa S su:

1. v ima desno podstablo => Sledbenik se traži kao ključ desnog sina, odnosno kao ključ najlevljeg čvora u desnom podstablu

Na primer: a=8 ili a=5 ili a=11

2. v nema desnog sina => Sledbenik se traži tako što se traži ključ najnižeg pretka w takvog da levi sin od w je predak čvora v.

Ova operacija se najefikasnije izvodi ako se za svaki čvor čuva i polje otac sa pokazivačem na oca čvora. Tako se ide od čvora v prema korenu sve dok se ne nađe čvor w koji je levi sin svog oca. U slučaju da nema takvog pretka w, onda je a najveći element skupa i nema svog sledbenika.

Na primer: a=12 ili a=3

U svakoj situaciji, sledbenik se nalazi bez poređenja ključeva zahvaljujući principu uređenosti stabla.

Sledi algoritam za nalaženje sledbenika za zadatu vrednost ključa čvora ukazanog sa v koji vraća adresu sledbenika ili NULL. Koristi se i poziv algoritma BST_MIN koji u BST (stablu binarnog pretraživanja) traži ključ sa minimalnom vrednošću.

Algoritam BST_MIN za BST čiji je koren ukazan argumentom node ide po lancu levih pokazivača sve dok ne dođe do čvora koji nema levog sina. .

int BST_MIN (Stablo koren) /* Najmanji u uredjenom stablu. */
 { return koren->levo ? BST_MIN (koren->levo ) : koren->broj; }

Algoritam BST_MIN pokriva 1. situaciju kada je potrebno pronači ključ sa minimalnom vrednošću u desnom podstablu čvora v.

Algoritam BST_SLEDBENIK (v)
 
ulaz: v
 
izlaz: q /* bilo da je NULL ili nije */
 
{
 
 pom=v
 
 if (right(pom) != NULL) return BST_MIN(right(pom)) /*1. situacija*/
 
 else /* 2. situacija*/
 
 {
 
 q=otac(pom)
 
 while (q != NULL ) and (pom == right(q)) do
 
 {
 
 pom=q
 
 q=otac(pom)
 
 }
 
 return q
 
 }
 
}
 
Napomena: x=right(y) <= > x=y- > right . . .
 

Operacije nalaženja minimalnog ključa, sledbenika imaju vreme izvršavanja srazmerno visini stabla h, tj. O(h), jer u svakoj od situacija prate putanju kroz stablo samo u jednom smeru.

5.

Dat je pseudo-kod (bez f-je ispisa)

int s; /* vrednost izraza */

int n; /* broj operanada */

int jeste; /*indikator 0/1 da li vrednost izraza je s*/

int a[50]; /* vrednosti operanada izraza */

int z[50]; /* niz operatora izraza */

void racunaj(int k, int ts)

{

//k= redni broj primenjen operacije

//ts = tekuca suma izraza

if(k==n)

{ if(ts==s) {pisi(); jeste=1;} }

else

{ /*formiranje operatora unutar izraza */

z[k]='+'; racunaj(k+1, ts+a[k+1]);

z[k]='-'; racunaj(k+1, ts-a[k+1]);

z[k]='*'; racunaj(k+1, ts*a[k+1]);

if(a[k+1]!=0)

{z[k]='/'; racunaj(k+1, ts/a[k+1]); }

}

}

main()

{

int i;

printf("Unesite vrednost izraza i broj operanada izraza\n");

scanf("%d%d",&s,&n);

printf("\nUnesite vrednost za %d operanada\n",n);

for(i=1; i<=n;i++) scanf("%d",&a[i]);

jeste=0;

racunaj(1,a[1]);

if (!jeste) printf("\nNema resenja\n");

}