Algoritmi sa brojevima

Ovo poglavlje sadrži nekoliko opštih algoritama sa brojevima, kao i još neke druge korisne informacije.

Prebrojavanje (Counting)

Vrlo često želimo da naš program prebroji koliko se puta nešto dogodilo. Na primer, video igrica treba da prati koliko je poteza napravio igrač, ili matematički program koji želi da prebroji koliko ima brojeva sa određenom osobinom. Ključna stvar pri brojanju je korišćenje varijable koja pamti taj broj.

Primer 1

Sledeći program dobija 10 brojeva od korisnika i prebrojava koliko od tih brojeva je veće od 10.

brojac = 0
for i in range(10):
    num = eval(input('Unesite broj: '))
    if num > 10:
        brojac = brojac + 1  # brojac += 1
print('Ima', brojac, 'brojeva većih od 10.')

Razmišljajmo o varijabli brojac kao belešci na papiru. Svaki put kada dobijemo broj veći od 10, mi dodamo jedan u našu belešku. U programu to se postiže u liniji brojac = brojac + 1. Prva linija programa, brojac = 0, je posebno važna. Bez nje Python interpreter bi naišao na naredbu brojac = brojac + 1 i izbacio grešku koja kaže da mu nije poznato šta je brojac. To je zbog toga što kada prvi put dođe na tu liniju, interpreter pokušava da uradi ono što piše: uzmi staru vrednost za brojac, dodaj 1 na nju, i sačuvaj rezultat u brojac. Ali kada program po prvi put dođe ovde, nema stare vrednosti za brojac koju bi koristio, pa Python interpreter ne zna šta da radi. Da izbegnemo grešku, potrebno je da definišemo brojac, i to je ono što prva linija programa radi. Tu postavljamo brojac na 0 čime označavamo da na početku programa nije nađen nijedan broj veći od 10.

Prebrojavanje se veoma često pojavljuje u raznim situacijama. Za prebrojavanje su ključne dve naredbe:

brojac = 0             # Početak brojanja od 0
brojac = brojac + 1    # Povećanje brojača za 1

Primer 2

Sledeća modifikacija prethodnog primera prebrojava koliko ima brojeva koje je korisnik uneo a koji su veči od 10, a takođe i koliko je uneto nula. Da prebrojimo dve različite stvari potrebne su nam dve brojac varijable za brojanje.

brojac1 = 0
brojac2 = 0
for i in range(10):
    num = eval(input('Unesite broj: '))
    if num > 10:
        brojac1 = brojac1 + 1
    if num == 0:
        brojac2 = brojac2 + 1
print('Ima', brojac1, 'brojeva većih od 10.')
print('Ima', brojac2, 'nula.')

Primer 3

Evo sada jednog malo složenijeg problema. Ovaj program prebrojava koliko se kvadrata 12 do 1002 završava cifrom 4.

brojac = 0
for i in range(1,101):
    if (i**2) % 10 == 4:
        brojac = brojac + 1
print(brojac)

Nekoliko napomena uz ovaj program: Prvo, zbog ranije navedene specifičnosti range funkcije, potrebno je da upotrebimo range(1,101) da bi u petlji prošli kroz brojeve od 1 do 100. Varijabla petlje, i dobija te vrednosti, dok se kvadrati 12 do 1002 mogu dobiti kao i**2. Kao sledeće, za proveru da li se broj završava sa cifrom 4, koristimo lep matematički trik kojim proveravamo da li je postoji ostatak jednak 4 kada broj podelimo sa 10. Operator % smo iskoristili da dobijemo ostatak pri deljenju.

Sabiranje (Sumiranje)

Prebrojavanju je veoma slična operacija sabiranja ( sumiranja ) niza brojeva.

Primer 1

Ovaj program će sabrati sve brojeve od 1 do 100. Program radi na taj način da svaki put kada se genriše novi broj, taj se broj doda na već postojeću vrednost varijable s. Naravno pre početka generisanja i sumiranja brojeva verijablu s treba postaviti na 0, kako bi prvi generisani broj imao već poznatu početnu vrednost varijable na koju će biti dodat.

s = 0
for i in range(1,101):
    s = s + i
print('Suma je', s)

Primer 2

U ovom programu od korisnika se traži da unese 10 brojeva a onda se izračunava i štampa njihova srednja vrednost.

s = 0
for i in range(10):
    num = eval(input('Unesite broj: '))
    s = s + num
print('Srednja vrednost je', s/10)

Primer 3

Jedna česta upotreba sumiranja je da se prati skor u nekoj igri. Na početku igre se skor varijabla postavlja na 0. Zatim, kada treba dodati skor to se radi kao u sledećoj liniji:

skor = skor + 10

Zamena vrednosti (swapping)

Često ćemo hteti da zamenimo vrednosti dve varijable, recimo x i y. Mogli bi da pokušamo da to uradimo ovako:

x = y
y = x

Ali ovo nije ispravan način. Pretpostavimo da x ima vrednost 3, a y vrednost 5. U prvoj liniji koda x će biti postavljeno na 5, što je u redu, ali u drugoj liniji će y biti postavljeno takođe na 5, jer je sada x zapravo 5. Trik je u tome da se koristi treća varijabla koja će sačuvati vrednost za x, pre nego što ona bude promenjena:

sacuvaj = x
x = y
y = sacuvaj

U većini programskih jezika to je jedini način zamene vrednosti dve varijable. Python, međutim, i ovde ima skraćeni način, tako da se zamena vrednosti može postići i ovako:

x,y = y,x

Kasnije ćemo videti zašto je to moguće. Za sada, na vama je da korsitite ove dve mogućnosti po vašem izboru. Drugi metod, međutim, ima prednost jer je kraći i jednostavniji za razumevanje.

Zastavice (flag)

Flag varijabla se može koristiti da omogući jednom delu vašeg programa da zna da se nešto dogodilo u drugom delu programa. Evo jednog primera kojim se određuje da li je neki broj prost ili ne.

num = eval(input('Unesite broj: '))

flag = 0
for i in range(2,num):
    if num % i == 0:
        flag = 1

if flag == 1:
    print('Nije prost')
else:
    print('Prost')

Setimo se da je neki broj prost ako je deljiv samo sa 1 i sa samim sobom. Način na koji gornji program radi je da započinje postavljanjem varijable flag na 0. Zatim idemo kroz petlju sa brojevima od 2 to num-1. Ako je neka od ovih vrednosti delilac unetog broja, varijablu flag postavljamo na 1, čime označavamo događaj da je nađen delioc. Kada petlja završi, proveravamo da li je flag setovan (postavljen na 1) ili ne. Ako jeste, znamo da je bio pronađen delioc i da broj num nije prost. U suprotnom, broj je prost.

Maksimumi i minimumi

Čest programski zadatak je da se nađe najveći ili najmanji broj u nizu brojeva. Ovde dajemo primer programa u kojem se od korisnika traži da unese deset pozitivnih brojeva, a zatim se štampa najveći od njih.

najveci = eval(input('Unesite pozitivan broj: '))
for i in range(9):
    num = eval(input('Unesite pozitivan broj: '))
    if num > najveci:
        najveci = num
print('Najveci broj:', najveci)

Ključna stvar je ovde varijabla najveci koja prati koji je do tada nađeni najveći broj. Počinjemo postavljanjem ove varijable na prvi broj koji korisnik unese. Zatim, svaki put kada korisnik unese novi broj, proveravamo da li je taj broj veći od trenutno najvećeg (koji je zapamćen u varijabli najveci). Ako jeste, postavljamo varijablu najveci na vrednost tog korisnikovog broja.

Ako umesto najvećeg tražimo najmanji, sve što treba da uradimo je da zamenimo znak > sa znakom <, a možda bi bilo dobro i da promenimo ime varijable najveci u najmanji.

Kasnije kada se budemo bavili listama ( struktura podataka ) videćemo i kraće načine za nalaženje najvećeg i najmanjeg broja, ali tehnika koju smo prikazali može biti korisna u situaciji kada liste ne mogu da urade sve ono što biste želeli.

Komentari u programu

Komentar je poruka za one koji čitaju vaš program. Komentari se često koriste da opišu šta vaš program radi ili kako to radi, a posebno u onim delovima koda koji su malo zagonetniji. Komentari nemaju uticaj na tok izvršavanja programa.

Jednolinijski komentari (single-line comments)

Za jednolinijske komentare koristi se znak # kao u sledećem primeru:

# jedan malo zagonetan nacin za istovremeni unos dva broja
num1, num2 = eval(input('Unesite dva broja razdvojena zarezom: '))

Jednolinijski komentar možete postaviti i na kraj linije kao u ovom primeru:

brojac = brojac + 1  # svaki delioc dodaje 1 na brojac

Višelinijski komentari (multi-line comments)

Za kometare koji se protežu na više linija koristimo trostruki navodnik kao u sledećem primeru:

""" Ime programa: Pozdrav
    Author: Milan Popovic
    Datum: 17.11.2016 """

print('Pozdrav svima!')

Jedna lepa upotreba višelinijskih komentara je da pod njima stavimo deo programa. Često kada modifikujemo kod, staru verziju želimo da sačuvamo u slučaju da promena ne funkcioniše kako treba. U takvim slučajevima možemo stari kod da stavimo pod komentar tako da bude tu ako nam zatreba, a biće ignorisan kada izvršavate novi kod. Evo jedan prost primer:

"""
print('Ova i sledeća linija se stavljene pod komentar.')
print('Ove linije se neće izvršavati.')
"""
print('Ova linija nije komentar pa će biti izvršena.')

Jednostavno debagiranje

Ovde prikazujemo dve jednostavne tehnike za otkrivanje zašto program ne radi:

  1. Korišćenje Python shell-a. Nakon što program završi sa radom možete da unosom imena varijabli ispitate njihove vrednosti i da vidite da li te vrednosti odgovaraju onima koje ste očekivali. Shell možete takođe koristiti da unesete kratke segmente vašeg programa i proverite da li rade korektno.

  2. Dodavanje print naredbi u program. Možete ih dodati u bilo kojoj liniji vašeg programa da na taj način vidite koje su vrednosti varijabli. Možete dodavanjem print naredbe da proverite i da li program tokom izvršavanja ulazi u neki deo koda ili ne. Na primer, ako sumnjate da imate grešku u postavljenom uslovu if naredbe, možete dodati print naredbu u bloku te if naredbe da proverite da li se taj blok izvršava ili ne. Evo jednog primera iz programa za određivanje prostih brojeva koji smo ranije videli. Dodali smo print naredbu u for petlji da vidimo sve slučajeve kada se flag varijabla setuje:

    flag = 0
    num = eval(input('Unesite broj: '))
    for i in range(2,num):
        if num % i == 0:
            flag = 1
        print(i, flag)
    
  3. Prazna input naredba, kao u donjem primeru, može biti dodata da privremeno zaustavi izvršavanje programa u nekoj karakterističnoj liniji:

    input()
    

Čitanje programa

Korisno je razvijati sposobnost čitanja programa ( tuđih i vlastitih ). Ovde ćemo malo dublje posmatrati neke proste programe i pokušati da razumemo šta i kako rade.

Primer 1

Sledeći program štampa Hello slučajan broj ( između 5 i 25 ) puta.

from random import randint

rand_num = randint(5,25)
for i in range(rand_num):
    print('Hello')

U prvoj liniji je import naredna. Ona se pojavljuje samo jednom (za svaki modul koji nam je potreban), obično na početku programa. Sledeća linija generiše slučajan broj između 5 i 25. Setite se da za ponavljanje nečega određeni broj puta koristimo for petlju. Da nešto ponovimo 50 puta, koristimo range(50) u for petlji. Da nešto ponovimo 100 puta koristi li bi range(100). Da ponovimo nešto slučajan broj buta koristimo range(rand_num), gde je rand_num varijabla u kojoj se čuva generisani slučajan broj. Mogli smo, međutim, i da preskočimo upotrebu varijable i da randinit naredbu stavimo direktno u range funkciju kao što sledi:

from random import randint

for i in range(randint(5,25)):
    print('Hello')

Primer 2

Uporedite ova dva programa.

from random import randint        from random import randint

rand_num = randint(1,5)           for i in range(6):
for i in range(6):                    rand_num = randint(1,5)
    print('Hello'*rand_num)           print('Hello'*rand_num)

Izlaz:

Hello Hello                       Hello Hello Hello
Hello Hello                       Hello
Hello Hello                       Hello Hello Hello Hello
Hello Hello                       Hello Hello Hello
Hello Hello                       Hello Hello
Hello Hello                       Hello

Jedina razlika između programa je u poziciji rand_num naredbe. U prvom programu ona se nalazi van for petlje, a to znači da se varijabla rand_num setuje samo jednom na početku programa i da zadržava istu vrednost tokom celog života (izvršavanja) programa. Zato će svaka print naredba štampati Hello isti broj puta u svakoj liniji. U drugom programu, rand_num naredba je unutar petlje. Pre svake print naredbe rand_num varijabla dobija novu vrednost pa broj puta ponavljanja Hello varira od linije do linije.

Primer 3

Hajde da napišemo program koji generiše 1000 slučajnih brojeva između 1 i 100, pa da broji koliko je onih koji su deljivi sa 12. Evo šta nam je za to potrebno:

Pošto koristimo slučajne brojeve u prvoj liniji nam treba import naredba za random modul. Trebaće nam for petlja za 1000 ponavljanja. Unutar petlje treba da generišemo slučajan broj, da proverimo da li je deljiv sa 12, pa ako jeste da dodamo 1 na brojač. Pošto prebrojavamo moraćemo pre prebrojavanja da postavimo brojač na 0. Da proverimo deljivost sa 12 koristićemo operator modulo, %.

Kada sve ovo spojimo u jednu programsku celinu dobijamo:

from random import randint

brojac = 0
for i in range(10000):
    num = randint(1, 100)
    if num % 12 == 0:
        brojac = brojac + 1
print('Broj brojeva deljivih sa 12:', brojac)

Razmaci (indentation) na početku linija su važni!

Česta greška je neispravna indentikacija. Pretpostavimo da u gornjem programu promenimo indentikaciju u zadnjoj liniji programa dako da on sada izgleda kako je prikazano dole. Program će i dalje da radi, ali ne onako kako smo očekivali.

from random import randint

brojac = 0
for i in range(10000):
    num = randint(1, 100)
    if num%12==0:
        brojac=brojac+1
    print('Broj brojeva deljivih sa 12:', brojac)

Kada izvršimo ovaj program, dobičemo čitavu gomilu brojeva. Razlog za to je što smo dodali razmak na početak print naredbe i time je učinili delom for petlje pa se print naredba izvršava 10000 puta ( umesto samo jedanput, kako smo očekivali )

Pretpostavimo da smo print naredbu pomerili (indentikovali) još više udesno, kao što je prikazano dole.

from random import randint

brojac = 0
for i in range(10000):
    num = randint(1, 100)
    if num%12==0:
        brojac=brojac+1
        print('Broj brojeva deljivih sa 12:', brojac)

Sada je ona ponovo deo for petlje, ali je i deo if naredbe. Ono što će se sada dešavati je da kad god naiđemo na broj deljiv sa 12 štampaćemo vrednost varijable brojac. Ni ovaj ni predhodni primer ne štampaju vrednost brojac na kraju programa, zato ova print naredba ne treba da bude uopšte indentiikovana.

Vežbe

5.1 Napišite program koji prebrojava koliko kvadrata brojeva od 1 do 100 završava cifrom 1.

5.2 Napišite program koji prebrojava koliko kvadrata brojeva od 1 do 100 završava cifrom 4 a koliko cifrom 9.

5.3 Napišite program koji traži od korisnika da unese vrednost varijable n, a zatim izračunava izraz (1+1/2+1/3+…+1/n)-ln(n). ln je funkcija log u math modulu.

5.4 Napišite program koji izračunava sumu 1-2+3-4+…+1999-2000.

5.5 Napišite program koji traži od korisnika da unese neki broj, a zatim štampa sumu svih delioca toga broja. Suma svih delioca nekog broja je važna funkcija u teoriji brojeva.

5.6 Neki broj se naziva perfektnim ako je jednak sumi svih svojih delioca, ne uključujuci njega samog. Na primer broj 6 je perfektan jer su delioci broja 6 brojevi 1,2,3,6 a 6=1+2+3. Još jedan primer je broj 28 čiji su delioci 1, 2, 4, 7, 14, 28 a 28=1+2+4+7+14. Međutim 15 nije perfektan jer su njegovi delioci 1, 3, 5, 15 a 15≠1+3+5. Napišite program koji pronalazi sve perfektne brojeve manje od 10000.

5.7 Ceo broj se naziva bezkvadratnim ako nije deljiv ni sa jednim kvadratom većim od 1. Na primer 42 je bezkvadratan jer su njegovi delioci 1,2,3,6,7,21,42 a ni jedan od njih nije kvadrat celog broja ( osim 1 – što se po definiciji ne računa ). S druge strane 45 nije bezkvadratan jer ima delioc 9 koji je kvadrat broja 3. Napišite program koji traži od korisnika da unese ceo broj a zatim mu kaže da li je taj broj bezkvadratan ili ne.

5.8 Napišite program koji zamenjuje vrednosti tri varijable x, y, i z, tako da x dobije vrednost y, y dobije vrednost z, a z dobije vrednost x.

5.9 Napišite program koji prebrojava koliko celih brojava između 1 i 1000 nisu ni kvadrati, ni kubovi ni peti stepeni celih brojeva.

5.10 Tražite od korisnika da unese 10 rezultata nekog testa. Napišite program koji radi sledeće:

  • Štampa najveći i najmanji rezultat.
  • Štampa prosečan rezultat.
  • Štapma drugi najveći rezultat.
  • Ako je bilo koji rezultat veći od 100, nakon što su svi rezultati učitani, štampa poruku upozorenja da je uneta vrednsot veća od 100.
  • Odbacuje dve najmanje vrednosti i štampa srednju vrednost ostalih.

5.11 Napišite program kojim se izračunava faktorijel nekog broja. Faktorijel, n!, nekog broja n je proizvod svih celih brojava između 1 i n, uključijući n. Na primer, 5!=1·2·3·4·5=120. [ Pomoć: Pokušajte da napravite multiplikativnu varijantu tehnike sumiranja koja je ranije pokazana.]

5.12 Napišite program koji traži od korisnika da pogodi slučajan broj između 1 i 10. Ako pogodi dobija 10 poena koji se dodaju na njegov skor, a gubi 1 poen ako da pogrešan odgovor. Dajte korisniku priliku da pogodi pet brojeva, pa mu štampajte skor na kraju svih pokušaja.

5.13 U jednom od prethodnih poglavlja postoji vežba u kojoj ste trebali da kreirate igru množenja za decu. Poboljšajte taj program tako da vodi evidenciju o broju tačnih i pogrešnih odgovora. Na kraju programa štampajte poruku koja je prilagođena broju tačnih odgovora.

5.14 Ova vežba je u vezi sa poznatim „Monty Hall“ problemom. U ovom problemu vi ste jedan takmičar u kvizu. Voditelj, Monty Hall, vam pokazuje troje vrata. Iza jednih od njih je nagrada, a iza drugih dvoje vrata su koze. Vi birate vrata. Monty Hall koji zna iza kojih vrata je nagrada, otvara jedna od preostalih dvoje vrata iza kojih nije nagrada. Sada su preostala dvoje zatvorenih vrata, i Monty Hall vam nudi mogućnost da promenite svoju prvobitnu odluku. Da li treba da ostanete pri svom izboru, da promenite odluku, ili to nije uopšte bitno? Napišite program kojim se simulira ova igra 10000 puta i izračunajte procenat dobitka ukoliko promenite i u koliko ne promenite odluku. Pokušajte isto, ali sa četvoro vrata. I dalje je samo jedna nagrada, a Monty otvara jedna vrata i daje vam mogućnost da promenite odluku.

5.15 Nekada je bila popularna sledeća igra sa drvcima. Igraju je dva igraca. Igra počinje sa gomilom od 21 drvceta. Prvi igrač uklanja od 1 do 4 drvceta sa gomile. Zatim drugi igrac radi isto, uklanja 1 do 4 drvca sa gomile. Igrači naizmenično vrše uklanjanje, svaki put od 1 do 4 drvca. Onaj ko poslednji ukloni sva drvca sa gomile gubi igru. Napišite program za igranje ove igre između čoveka i kompjutera, u kojem kompjuter bira slučajan broj kada je na potezu. Možete li da pronađete pobedničku strategiju za igrače u ovoj igri?