Nedostajući broj-uputstvo
Zadatak može da se reši linearnom pretragom, što nije najbolji način da se ovaj zadatak reši. Korišćenjem petlji se prolazi kroz niz i poredi se tekući element sa traženim(if nareba). Prolazak se prekida u slučaju da se pronađe traženi broj. U najgorem slučaju će se proći kroz sve elemente od početka do kraja niza i konstatovati da traženog elementa nema u nizu. Koristiti logičke promenljive (bool ili int u jeziku C)za konstatovanje da li, ili ne, se traženi element nalazi u nizu. Npr. ova promenljiva se može postaviti na false(0) pre prolaska kroz petlju. U slučaju da se element pronađe, vrednost promenljive se promeni na true(1), a ako se ne pronađe do kraja niza, ne ostaće false(0).
Više o linearnoj i binarnoj pretrazi možete pročitati na webstrani: Binarna pretraga
Više o linearnoj i binarnoj pretrazi možete pročitati na webstrani: Binarna pretraga
Prednosti i mane:
- Prednosti: Jednostavna implementacija; ne zahteva dodatne strukture podataka.
- Mane: Niska efikasnost, posebno za velike nizove, jer se u najgorem slučaju prolazi kroz sve elemente niza.
Praktična primena
bool pronađen = false;
for (int i = 0; i < veličina_niza; i++) {
for (int i = 0; i < veličina_niza; i++) {
if (niz[i] == traženi_broj) {
}
pronađen = true;
break;
}break;
Rešavanje zadatka -korišćenjem formule
Brži i bolji način da se zadatak reši da se nađe zbir svih članova učitanog niza ZbirUcitanih, kao i zbir koji bi trebao da bude kada element ne bi nedostajao( ZbirSvih).
Razlika ova dva zbira je zapravo traženi element X jer je: X+ZbirUcitanih= ZbirSvih
Npr Ako je niz:
0, 1,2,4,5
ZbirUcitanih=0+1+2+4+5=12
ZbirSvih=0+1+2+3+4+5=16
Traženi broj X=ZbirSvih-ZbirUcitanih=16-12=4
Razlika ova dva zbira je zapravo traženi element X jer je: X+ZbirUcitanih= ZbirSvih
- Izračunavanje zbiru svih brojeva: Ako niz sadrži sve brojeve od 0 do n, zbir ovih brojeva je dat formulom:
ZbirSvih=n*(n+1)/2
- Izračunavanje zbiru pročitanih brojeva: Prođite kroz niz i sabirajte sve brojeve koji su prisutni:
ZbirUcitanih=Suma brojeva u pročitanom nizu
- Pronalazak nedostajućeg broja: Razlika između zbir svih brojeva i zbir pročitanih brojeva daje nedostajući broj:
Npr Ako je niz:
0, 1,2,4,5
ZbirUcitanih=0+1+2+4+5=12
ZbirSvih=0+1+2+3+4+5=16
Traženi broj X=ZbirSvih-ZbirUcitanih=16-12=4