Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Zadaci za wannabe pythoniste

[es] :: Python :: Zadaci za wannabe pythoniste

Strane: << < .. 6 7 8 9 10 11 12 13 14 15 ... Dalje > >>

[ Pregleda: 50991 | Odgovora: 629 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Zadaci za wannabe pythoniste19.01.2020. u 12:30 - pre 51 meseci
U redu, to je sasvim lepo, skolsko resenje. Ali da li ce program optimalno raditi i za 100,000,000 elemenata, ako prodjes kroz ceo niz da bi ustanovio da broj treba ubaciti negde pred sam kraj niza? Imas li neki bolji predlog?

Edit: uzgred, ne radi ti program kada je n > niz[-1] (npr. n=153), kao i kada se n poklapa sa nekim postojecim elementom u nizu.

[Ovu poruku je menjao B3R1 dana 19.01.2020. u 14:50 GMT+1]
 
Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
109.72.51.23



+1064 Profil

icon Re: Zadaci za wannabe pythoniste19.01.2020. u 14:49 - pre 51 meseci
Nego niz nije bas najsrecnija struktura za insertovanje elemenata pogotovo kad je veliki. Lista takodje nije ali dvostruko ulancana lista jeste.
No pitanje je koja je struktura podataka optimalna za ovaj zadatak? Necu reci ali to moze dati ideju kako resiti za niz :P
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste19.01.2020. u 15:07 - pre 51 meseci
Citat:
B3R1:
U redu, to je sasvim lepo, skolsko resenje. Ali da li ce program optimalno raditi i za 100,000,000 elemenata, ako prodjes kroz ceo niz da bi ustanovio da broj treba ubaciti negde pred sam kraj niza? Imas li neki bolji predlog?

Edit: uzgred, ne radi ti program kada je n > niz[-1] (npr. n=153), kao i kada se n poklapa sa nekim postojecim elementom u nizu.

[Ovu poruku je menjao B3R1 dana 19.01.2020. u 14:50 GMT+1]


Ne znam hoće li raditi, moram da ga testiram :D
Samo da mi ne zariba komp.

Nego, imam drugu ideju.

Šta ako prvo odredim sredinu niza i uporedim broj na sredini sa mojim.
Ako je veći idem desno, ako je manji, idem levo i uštedeo sam očas 50.000.000 prolaza.
Šta misliš? Mada još nemam ideju kakako to praktično da izvedem, ali kao koncept misli da može da prođe :)

Možda sa len(lista), pa podelim na pola i dobijem indeks broja u sredini... i onda uporedim.
Ako tako seckam na pola, doći ću i do liste od recimo 20 brojeva, a onda mogu da odradim kao ovo rešenje koje sam dao.
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste19.01.2020. u 15:14 - pre 51 meseci
E da, da se pohvalim :)
Išao dalje po onoj tvojoj knjizi, pa došao do zadatka:

za string
s = '1.23, 2.4, 3.123'
izračunaj zbir brojeva.

Code:
s = '1.23, 2.4, 3.123'
q = s.split(', ')
total = 0
for i in q:
    total = total + float(i)
print(total)

i radi!

6.753
 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Zadaci za wannabe pythoniste19.01.2020. u 17:44 - pre 51 meseci
Citat:
a1234567:
Šta ako prvo odredim sredinu niza i uporedim broj na sredini sa mojim. Ako je veći idem desno, ako je manji, idem levo i uštedeo sam očas 50.000.000 prolaza.
...
Ako tako seckam na pola, doći ću i do liste od recimo 20 brojeva, a onda mogu da odradim kao ovo rešenje koje sam dao.

Tacno tako! Uporedis broj na sredini sa zadatim. Ako je zadati broj veci, pomeris donju granicu niza na sredinu. Ako je broj maji pomeras gornju granicu na sredinu. Sada tu polovinu u kojoj se nalazi broj opet delis na pola. Ako je broj manji, gornju granicu pomeras na tu novu sredinu; ako je veci pomeras donju itd. Onda tu cetvrtinu delis na pola itd. dok ne dodjes do liste od dva broja.

Pokusaj da implementiras, nije tesko. Vidis kako ti lepo ide ...
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 02:22 - pre 50 meseci
Ništa nije teško, kad rešiš :)

Ali zato dok ne rešiš, muke Isusove.
Mislim, ideja za rešenje mi je bila jasna relativno brzo,
ali sam celo popodne lupao glavu oko implementacije.
No, mislim da sam došao do rešenja:

Code:
niz = [3, 7, 11, 21, 25, 38, 41, 95, 118, 129, 144, 153, 174]
niz_2 = niz.copy()
broj = 138

while len(niz) != 1:
    mid = int(len(niz)/2)
    if broj > niz[mid]:
        niz = niz[mid:]
    else:
        niz = niz[:mid]

br_niz = niz.pop(0)
indx = niz_2.index(br_niz)

if broj > br_niz:
    niz_2.insert(indx + 1, broj)
elif broj < br_niz:
    niz_2.insert(indx - 1, broj)
else:
    niz_2.insert(indx - 1, broj) #ovo u slučaju da je zadati broj isti kao i  neki u nizu

print(niz_2)


Dosta sam vremena izgubio oko while funkcije, jer sam prvo stavio
while len(niz) == 1:
misleći da će se izvršavati, dok len ne postane 1. Ali, naravno, ništa se nije dešavalo.
Posle n pokušaja i očajanja :) uzmem knjigu i pročitam o while funkciji, a tamo lepo piše da se izvršava
sve dok uslov nije ispunjen. I onda mi sine šta treba da menjam.

Imao sam takođe muku kad na kraju dobijem listu od jednog člana, recimo niz = [129], kako da vrednost
tog člana pretvorim u integer, da bih mogao da dobijem njegov index. I onda natrčim na niz.pop funkciju. Zlata vredi! :)

Eto tako. Ovo je rudarski posao. Korak po korak, kao da kopam tunel i pipam u mraku.
Ali zato kad ga prokopaš i na kraju te obasja svetlo rešenja! :))) Ništa lepše!
 
Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
109.72.51.23



+1064 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 06:59 - pre 50 meseci
E sad insert u niz je O(n)...
Koja struktura podataka je idealna za ovaj zadatak?
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 07:10 - pre 50 meseci
Šta ti je O(n)?

Koja vrsta?
Pa valjda lista.
 
Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
109.72.51.23



+1064 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 07:19 - pre 50 meseci
To znaci n operacija (linearno). Znaci kada umeces element u niz, onda moras sve elemente sa desne strane da pomeris za jedno mesto sto je O(n).
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 07:30 - pre 50 meseci
Aha, pa dobro, pomerio sam ih, naravno. Ne možeš drugačije da ubaciš.
A što je to bitno? I dalje ne razumem smisao pitanja. Što i nije čudo, kad se bolje razmisli :)
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 07:33 - pre 50 meseci
A evo i novog zadatka iz Guttagove knjige:

Napiši program koji traži od korisnika da unese neki integer,
a potom štampa dva druga integera, root i pwr, tako da 0 < pwr < 6,
a root**pwr je jednako integeru koji je uneo korisnik.
Ako takav par inetegera ne postoji, program ispisuje odgovarajuću poruku.
 
Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
109.72.51.23



+1064 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 11:43 - pre 50 meseci
Citat:
a1234567:
Aha, pa dobro, pomerio sam ih, naravno. Ne možeš drugačije da ubaciš.
A što je to bitno? I dalje ne razumem smisao pitanja. Što i nije čudo, kad se bolje razmisli :)


Pitanje je koja je struktura podataka idealna za ovaj zadatak ;)?
 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 12:07 - pre 50 meseci
Citat:
a1234567:
Aha, pa dobro, pomerio sam ih, naravno. Ne možeš drugačije da ubaciš.
A što je to bitno? I dalje ne razumem smisao pitanja. Što i nije čudo, kad se bolje razmisli :)

Branimir je mislio da te natera da pogledas kako su liste u Pythonu implementirane interno ... bas kao sto je onomad bila diskusija o tome kako su implementirani dict-ovi, pa si naucio da je to hash tabela, sto te je nateralo da naucis malo vise o hashevima ... Nije tesko pronaci i ovo o listama, dovoljno je da odes na Gugl i otkucas: python lists implementation ... i izaci ce ti gomila clanaka na tu temu. Tu ces videti tacno kako radi insert(), pop() itd.

U tim clancima su ponedge ponudjene i alternative. Ali mislim da si u ovom trenutku suvise daleko od tih alternativa. To je neki intermediate nivo ...
 
Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
109.72.51.23



+1064 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 12:15 - pre 50 meseci
Mislio sam na binarno stablo al ajde ;)
Nego, jel u pythonu ispod lista ili niz? U haskell-u je lista, pa je pristup preko index-a O(n) a insert jedino moguc na pocetak...
il opet O(n).
Znaci bilo lista bilo niz insert ce da uzme O(n), tako da sam mislio da implementira binarno stablo :P
Binarno stablo pretrazivanja je 1) sortirano 2) insert uzima O(log n)
Idealno za niz od 100_000_000 elemenata.
 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 12:27 - pre 50 meseci
Citat:
Branimir Maksimovic:
Nego, jel u pythonu ispod lista ili niz? U haskell-u je lista, pa je pristup preko index-a O(n) a insert jedino moguc na pocetak...

https://www.laurentluce.com/posts/python-list-implementation/
Insert je O(n).
Citat:
Znaci bilo lista bilo niz insert ce da uzme O(n), tako da sam mislio da implementira binarno stablo :P

Linkovane liste, dvostruko ulinkovane liste, binarna stabla ... su vec napredniji kurs, a covek je tek na pocetku pocetaka. :-)

Inace za sve te strukture postoje moduli.
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 12:57 - pre 50 meseci
Ja tek seo na bicikl, a Branimir bi već da me posadi u bolid.
Polako čoveče, trebal negde da se skrljam!? :)))

Binarna i druga listopadna stabla... doći će i to na red jednog dana.
Sad smo još kod zimzelenih stringova, lista, rečnika i tupli. Zimski period :)
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 13:02 - pre 50 meseci
Berislave, jesi pogledao rešenje za tvoj zadatak koje sam dao?
Ima li neki bag ili da ga štrikliram?
 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Zadaci za wannabe pythoniste20.01.2020. u 14:03 - pre 50 meseci
Citat:
a1234567: Berislave, jesi pogledao rešenje za tvoj zadatak koje sam dao?
Ima li neki bag ili da ga štrikliram?

Ako si ga dobro testirao i ako radi nema razloga da ti ne verujemo. :-) Testiranje bi trebalo da obuhvati broj manji od niz[0], broj veci od niz[-1] i neki broj u sredini. Potom da vidis kako ce program reagovati za niz tipa [ 5, 5, 5, 5, 5 ] a da je zadata vrednost 4, 5 ili 6. Potom da testiras za niz [ 5 ] i niz [ 5, 5 ] i [ 5, 6 ]. Ako za sve te slucajeve radi, resio si problem. Izmisli jos slucajeva. Testiranje softvera je nauka za sebe, inace ...

Moja jedina zamerka bi bila da su ti dva niza visak. Motivacija za to ti je verovatno bila da sacuvas prvobitni niz kako bi ga kasnije modifikovao, a da nad originalnim nizom radis svu "hirurgiju". Nema nikakve potrebe za hirurgijom, imajuci u vidu da ti vec rukujes indeksima. Niz menjas tek na kraju. Evo alternativnog resenja:
Code:
niz = [3, 7, 11, 21, 25, 38, 41, 95, 118, 129, 144, 153, 174]
broj = 138

if broj < niz[0]:
    niz.insert(0, broj)
elif broj > niz[-1]:
    niz.append(broj)
else:
    levo = 0
    desno = len(niz)

    while desno-levo > 1:
        mid = (levo + desno) / 2
        if broj >= niz[mid]:
            levo = mid
        else:
            desno = mid
    niz.insert(desno, broj)
print niz
 
Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
109.72.51.23



+1064 Profil

icon Re: Zadaci za wannabe pythoniste21.01.2020. u 01:37 - pre 50 meseci
Mislim da generalno da radis binary search tako sto ces da slajsujes, a onda pozoves index nad elementom nije nesto sto ima intellectual merit :P
 
Odgovor na temu

a1234567

Član broj: 46801
Poruke: 297
136.228.174.*



+3 Profil

icon Re: Zadaci za wannabe pythoniste22.01.2020. u 17:16 - pre 50 meseci
Novi, zanimljiv zadatak broj 15:

Napiši program koji će dešifrovati poruku pisanu Morzeovom azbukom?

U slučaju da možda, eventualno, ipak ne znate znakove ove azbuke, ovde su:

morse = {"A" : ".-", "B" : "-...", "C" : "-.-.", "D" : "-..", "E" : ".", "F" : "..-.", "G" : "--.", "H" : "....", "I" : "..", "J" : ".---", "K" : "-.-", "L" : ".-..", "M" : "--", "N" : "-.", "O" : "---", "P" : ".--.", "Q" : "--.-", "R" : ".-.", "S" : "...", "T" : "-", "U" : "..-", "V" : "...-", "W" : ".--", "X" : "-..-", "Y" : "-.--", "Z" : "--..", "0" : "-----", "1" : ".----", "2" : "..---", "3" : "...--", "4" : "....-", "5" : ".....", "6" : "-....", "7" : "--...", "8" : "---..", "9" : "----."}

Poruka koju treba dešifrovati je:

".... . .-.. .-.. --- .-- --- .-. .-.. -.."

Ja sam svoje rešenje sačuvao ovde.

Naravno, kad napravimp ovaj program, naredni zadatak može biti njegova nadogradnja, da prevodi u ova smera.
Ali polako, korak po korak :)
 
Odgovor na temu

[es] :: Python :: Zadaci za wannabe pythoniste

Strane: << < .. 6 7 8 9 10 11 12 13 14 15 ... Dalje > >>

[ Pregleda: 50991 | Odgovora: 629 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.