Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Još jedan zadatak s natjecanja (objasnjenje gradiva)
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Osnove algoritama
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
krcko
Forumaš nagrađen za životno djelo
Forumaš nagrađen za životno djelo


Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
Sarma = la pohva - posuda
655 = 759 - 104
PostPostano: 7:32 čet, 25. 1. 2018    Naslov: Još jedan zadatak s natjecanja Citirajte i odgovorite
Prošli tjedan održano je još jedno školsko natjecanje iz informatike. Ovo je po mojem sudu najzanimljiviji zadatak za 8. razred OŠ.

[quote][b]Zadatak: Drvored[/b] (90 bodova)

Želimo posaditi drvored koji će imati stabla bukve (B), hrasta (H) i jele (J). Drvored je zamišljen tako da su sva stabla istog tipa uvijek uzastopna. Npr. drvoredi BBHHJJ, HJJBB i JJHHBB zadovoljavaju navedeno pravilo, dok drvored HJH ne zadovoljava pravilo, budući da hrastovi nisu susjedni.

Radnik Dudo je posadio drvored stavljajući zrno po zrno sjemena u zemlju. Nažalost, tek je po završenom poslu saznao da je drvored morao poštovati navedeno pravilo. Sada mora presložiti sjeme.

Dudo raspolaže samo sjemenom koje je već u zemlji, a s njim može činiti dvije stvari:

1. izvaditi sjeme iz zemlje s nekog mjesta i spremiti ga u torbu;

2. posaditi sjeme iz torbe u zemlju na neko mjesto s kojeg je sjeme izvađeno.

Svaka od ove dvije aktivnosti traje točno [b]jednu minutu[/b].

Pomozite Dudi i odredite koliko mu je najmanje minuta potrebno da završi posao.

[b]ULAZNI PODACI[/b]

U prvom i jedinom retku nalazi se niz znakova od barem jednog znaka čija duljina neće prelaziti 20 - početno stanje drvoreda. Niz će se sastojati samo od velikih slova B, H i J.

[b]IZLAZNI PODACI[/b]

U jednom retku treba ispisati traženu vrijednost iz teksta zadatka.

[b]PRIMJERI TEST PODATAKA[/b]

[b]ulaz[/b]
HJHHBBH
[b]izlaz[/b]
4
Optimalno bi bilo: izvadi sjeme jele s drugog mjesta; izvadi sjeme hrasta sa sedmog mjesta; posadi sjeme jele na sedmo mjesto; posadi sjeme hrasta na drugo mjesto.

[b]ulaz[/b]
HHBJ
[b]izlaz[/b]
0

[b]ulaz[/b]
JBJBHJBHJH
[b]izlaz[/b]
10
[/quote]

Ponovit ćemo [url=http://degiorgi.math.hr/forum/viewtopic.php?t=20943]natjecanje od lani[/url] za studente koji su upisali OA 2017./18. Tko prvi napiše rješenje ovdje na forumu, dobiva peticu za zalaganje i celebrity status na usmenom :D Priznaju se rješenja u Pythonu ili nekom drugom programskom jeziku, ili samo opis algoritma. Hint je da proučite [url=https://en.wikipedia.org/wiki/Hamming_distance]Hammingovu metriku[/url].
Prošli tjedan održano je još jedno školsko natjecanje iz informatike. Ovo je po mojem sudu najzanimljiviji zadatak za 8. razred OŠ.

Citat:
Zadatak: Drvored (90 bodova)

Želimo posaditi drvored koji će imati stabla bukve (B), hrasta (H) i jele (J). Drvored je zamišljen tako da su sva stabla istog tipa uvijek uzastopna. Npr. drvoredi BBHHJJ, HJJBB i JJHHBB zadovoljavaju navedeno pravilo, dok drvored HJH ne zadovoljava pravilo, budući da hrastovi nisu susjedni.

Radnik Dudo je posadio drvored stavljajući zrno po zrno sjemena u zemlju. Nažalost, tek je po završenom poslu saznao da je drvored morao poštovati navedeno pravilo. Sada mora presložiti sjeme.

Dudo raspolaže samo sjemenom koje je već u zemlji, a s njim može činiti dvije stvari:

1. izvaditi sjeme iz zemlje s nekog mjesta i spremiti ga u torbu;

2. posaditi sjeme iz torbe u zemlju na neko mjesto s kojeg je sjeme izvađeno.

Svaka od ove dvije aktivnosti traje točno jednu minutu.

Pomozite Dudi i odredite koliko mu je najmanje minuta potrebno da završi posao.

ULAZNI PODACI

U prvom i jedinom retku nalazi se niz znakova od barem jednog znaka čija duljina neće prelaziti 20 - početno stanje drvoreda. Niz će se sastojati samo od velikih slova B, H i J.

IZLAZNI PODACI

U jednom retku treba ispisati traženu vrijednost iz teksta zadatka.

PRIMJERI TEST PODATAKA

ulaz
HJHHBBH
izlaz
4
Optimalno bi bilo: izvadi sjeme jele s drugog mjesta; izvadi sjeme hrasta sa sedmog mjesta; posadi sjeme jele na sedmo mjesto; posadi sjeme hrasta na drugo mjesto.

ulaz
HHBJ
izlaz
0

ulaz
JBJBHJBHJH
izlaz
10


Ponovit ćemo natjecanje od lani za studente koji su upisali OA 2017./18. Tko prvi napiše rješenje ovdje na forumu, dobiva peticu za zalaganje i celebrity status na usmenom Very Happy Priznaju se rješenja u Pythonu ili nekom drugom programskom jeziku, ili samo opis algoritma. Hint je da proučite Hammingovu metriku.



_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
shranj
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 03. 02. 2018. (23:22:20)
Postovi: (1)16
Sarma = la pohva - posuda
0 = 0 - 0
PostPostano: 0:42 ned, 4. 2. 2018    Naslov: Citirajte i odgovorite
[code:1]drvored=raw_input("Drvored: ")
duljina=len(drvored)
pomdrvored=[0]*duljina

b=0
h=0
j=0

splitano=[drvored[i:i+1] for i in xrange(duljina)]

for i in range (duljina):
if splitano[i]=='B':
b=b+1
elif splitano[i]=='H':
h=h+1
elif splitano[i]=='J':
j=j+1

min=duljina*2

#slucaj BHJ

i=0
br=0
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj BJH

i=0
br=0
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj HBJ

i=0
br=0
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj HJB

i=0
br=0
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj JBH

i=0
br=0
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

#slucaj JHB

i=0
br=0
for k in range (j):
pomdrvored[i]='J'
i=i+1
for k in range (h):
pomdrvored[i]='H'
i=i+1
for k in range (b):
pomdrvored[i]='B'
i=i+1

for i in range (duljina):
if splitano[i]!=pomdrvored[i]:
br=br+1

if br<min:
min=br

print min*2
[/code:1]

Program bi trebao raditi i za sve ostale primjere. Javite ako uočite pogrešku.
Kod:
drvored=raw_input("Drvored: ")
duljina=len(drvored)
pomdrvored=[0]*duljina

b=0
h=0
j=0

splitano=[drvored[i:i+1] for i in xrange(duljina)]

for i in range (duljina):
    if splitano[i]=='B':
        b=b+1
    elif splitano[i]=='H':
        h=h+1
    elif splitano[i]=='J':
        j=j+1

min=duljina*2

#slucaj BHJ

i=0
br=0
for k in range (b):
    pomdrvored[i]='B'
    i=i+1
for k in range (h):
    pomdrvored[i]='H'
    i=i+1
for k in range (j):
    pomdrvored[i]='J'
    i=i+1

for i in range (duljina):
    if splitano[i]!=pomdrvored[i]:
        br=br+1

if br<min:
    min=br

#slucaj BJH

i=0
br=0
for k in range (b):
    pomdrvored[i]='B'
    i=i+1
for k in range (j):
    pomdrvored[i]='J'
    i=i+1
for k in range (h):
    pomdrvored[i]='H'
    i=i+1

for i in range (duljina):
    if splitano[i]!=pomdrvored[i]:
        br=br+1

if br<min:
    min=br

#slucaj HBJ

i=0
br=0
for k in range (h):
    pomdrvored[i]='H'
    i=i+1
for k in range (b):
    pomdrvored[i]='B'
    i=i+1
for k in range (j):
    pomdrvored[i]='J'
    i=i+1

for i in range (duljina):
    if splitano[i]!=pomdrvored[i]:
        br=br+1

if br<min:
    min=br

#slucaj HJB

i=0
br=0
for k in range (h):
    pomdrvored[i]='H'
    i=i+1
for k in range (j):
    pomdrvored[i]='J'
    i=i+1
for k in range (b):
    pomdrvored[i]='B'
    i=i+1

for i in range (duljina):
    if splitano[i]!=pomdrvored[i]:
        br=br+1

if br<min:
    min=br

#slucaj JBH

i=0
br=0
for k in range (j):
    pomdrvored[i]='J'
    i=i+1
for k in range (b):
    pomdrvored[i]='B'
    i=i+1
for k in range (h):
    pomdrvored[i]='H'
    i=i+1

for i in range (duljina):
    if splitano[i]!=pomdrvored[i]:
        br=br+1

if br<min:
    min=br

#slucaj JHB

i=0
br=0
for k in range (j):
    pomdrvored[i]='J'
    i=i+1
for k in range (h):
    pomdrvored[i]='H'
    i=i+1
for k in range (b):
    pomdrvored[i]='B'
    i=i+1

for i in range (duljina):
    if splitano[i]!=pomdrvored[i]:
        br=br+1

if br<min:
    min=br

print min*2


Program bi trebao raditi i za sve ostale primjere. Javite ako uočite pogrešku.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
krcko
Forumaš nagrađen za životno djelo
Forumaš nagrađen za životno djelo


Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
Sarma = la pohva - posuda
655 = 759 - 104
PostPostano: 22:53 sri, 7. 2. 2018    Naslov: Citirajte i odgovorite
Čestiam, rješenje je točno! Bilo bi elegantnije da ste dijelove koji se ponavljaju definirali kao funkcije, ali to službeno nismo radili na nastavi.

Dakle, ideja je prebrojati koliko puta se ponavljaju slova B, J, H i definirati šest nizova: BJH, BHJ, JBH, JHB, HBJ, HJB (slova se ponavljaju onoliko puta kao i u ulaznom nizu). Zatim se računa Hammingova udaljenost ulaznog niza od tih šest nizova i minimum se množi s 2. Hammingova udaljenost je jednostavno broj koordinata na kojima se nizovi razlikuju.
Čestiam, rješenje je točno! Bilo bi elegantnije da ste dijelove koji se ponavljaju definirali kao funkcije, ali to službeno nismo radili na nastavi.

Dakle, ideja je prebrojati koliko puta se ponavljaju slova B, J, H i definirati šest nizova: BJH, BHJ, JBH, JHB, HBJ, HJB (slova se ponavljaju onoliko puta kao i u ulaznom nizu). Zatim se računa Hammingova udaljenost ulaznog niza od tih šest nizova i minimum se množi s 2. Hammingova udaljenost je jednostavno broj koordinata na kojima se nizovi razlikuju.



_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Osnove algoritama Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Možete otvarati nove teme.
Možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan