Srednjoškolski zadaci

[Bahati [SiD]]

Samo mi objasni kako si došao do ove formule: y:= ((brrob mod 5) * 2) mod 5 ?
Mislim, ok je ona, očigledno, nego kako si odnos između ostatka i broj grupa po 3 uspeo da pretočiš u ovu formulu? Ima li neka logika, koju ja ne vidim, ili ti se prosto javilo

cist vudu! lupio sam nekoliko primera u excelu, malo gledao i bum!

evo jos veci vudu: 9*((brrob div 5)-(brrob mod 5) mod 3)+5*(((brrob mod 5)*2) mod 5) = novi_roboti

*razlika je sto se i "petice" traze na svoj vudu nacin, tj. ne koriste se "trojke"

probao sam da je sredim u matlabu al' ne pravi nista korisno. ako vec nije bilo jasno, nisam neki maher za algebru, pa bi mozda neko drugi mogao jos da sredi...

Skroz mi je interesantno ovo kako je ''timski rad'' i unapređivanje predstavljenih rešenja dovelo do toga da od koda koji se izvršava 10ak sekundi, dođemo do ultra-jednostavnog i efikasnog koda.

bas i ja o tome razmisljam! a thing of beauty!

 

[Switch]

Svaka čast za ovaj vudu, mislim da kraći način za rešavanje tog problema ne postoji. Ali me intresuje matematičko objašnjenje te formule, i na koji si način došao do nje?

 

[Bahati [SiD]]

matematicko objasnjenje sigurno postoji, s tim sto ja formulu ne bi ni umeo da zapisem matematicki.

problem je bio napraviti funkciju koja za ulazni skup:
0 1 2 3 4 <- ostaci deljenja sa 5
proizvodi:
0 2 4 1 3 <- odgovarajuci broj grupa po 3 (primecen patern)

odmah se vidi da se prva tri broja dobijaju mnozenjem dvojkom, tj.
0 1 2 3 4 x 2 =
0 2 4 6 8

a onda je problem pretvoriti 6 i 8 u 1 i 3, a to se dobija kad se uradi mod 5.
on ne utice na prva tri zato sto su <5 tj. sami predstavljaju ostatak

0 2 4 6 8 mod 5 =
0 2 4 1 3 <- bingo!

ps. cela formula u drugacijem obliku:

n = 5 * x + 3 * y
x = ((n div 5)-(n mod 5) mod 3)
y = (((n mod 5)*2) mod 5)

je posebno interesantna zato sto radi za svako n=N0 i garantuje da je x najvece moguce! samo to treba dokazati...

 

[Speeder]

Auuu... opasan vudu

Ladno nisam jedini koji je za rešavanje ovog problema koristio Excel i Matlab :d

 

[Bahati [SiD]]

^^

i jos uvek tvrdim da profa ocekuje resenje slicno onom brute force sa pocetka! excel, matlab, paterni i vudu ne bi trebalo da budu neophodni za resavanje srednjoskolskih zadataka. :d

 

[marko_n]

Bio sam nešto zauzet, pa sam tek sad svratio ovde.

@all
cheers

@Switch
Kači zadatke slobodno. :smash:

 

[WebWolf]

Ja sam oduševljen odzivom i tolikom zalaganju da se dođe jednostavnog i efikasnog koda, zaista za svaku pohvalu. Kada sam postavljao temu očekivao sam komentare tipa 'Aj mali malo se potrudi, ne možeš dobiti sve na gotovo' , a zaista je lepo što postoje ljudi koji toliko truda i vremena potroše da pomognu u rešavanja jednog ovakvog zadatka. Zato sam i pre nekoliko postova napisao da ću postavljati slične zadatke ako ste zaintresovani, a to mi je i bila početna ideja i zato je naslov thread-a takav.
Da, i mene intresuje kako se došlo do te formule.

Ma uzivaj. Zadatak ti uopste nije naivan, kao sto vidis, a i imas ovde ljude koji su zeljni sto podsecanja sto novih izazova :d .

@Speeder && Bahati
Vi ste mi idoli, majke mi :bottle:

 

[marko_n]

n = 5 * x + 3 * y
x = ((n div 5)-(n mod 5) mod 3)
y = (((n mod 5)*2) mod 5)

Kad sam se malo udubio u formule, uopšte nije vudu, skroz je jasno.

Prva formula (x) se bazira na Speeder-ovom algoritmu (određuje koliko grupa od 5 će se rasformirati u zavisnosti od ostatka deljenja), dok se druga formula bazira na paternu koji sam učio, s tim da si izbacio niz tako što si pronašao funkciju koja mapira ostatak deljenja direktno na vrednost u onom nizu. arty:

 

[Switch]

Zadatak 2. Kasirka ispred sebe ima n klijenata. Ako se u ciklusu očitavaju njihove visine odrediti koliko klijenata ona može da vidi, ako se ne vide oni ispred kojih ima viših osoba.

 

[Bahati [SiD]]

uopšte nije vudu, skroz je jasno.

naravno da je jasno, ne verujem da je ikome palo napamet da sam izmislio novu matematiku. :d "vudu" je samo nacin na koji sam do nje dosao.

@switch: to je vec stvarno srednjoskolski.

priprema:
input h (visina prvog)
max = h
cnt = 1 (broj vidljivih)

algo:
loop begin
input h
if h>max -> max = h; cnt = cnt+1
loop end

kraj:
output cnt

moze i if h>=max -> max = h; cnt = cnt+1
ako se vidi i ako su iste visine...

i moze da se stavi provera na pocetak dal uopste ima musterija, pa ako nema cnt = 0. sve zavisi dal se ocekuje da prvo uneses sve visine ili si u petlji koja vrti dok se nesto ne desi (unese se specijalan znak i sl.) kao sto je algo napisan.

 

[drfedja]

Zadatak 2. Kasirka ispred sebe ima n klijenata. Ako se u ciklusu očitavaju njihove visine odrediti koliko klijenata ona može da vidi, ako se ne vide oni ispred kojih ima viših osoba.

Ovo je izuzetno prost zadatak. Svodi se na jednu brojacku promenjivu i na odredjivanje maksimuma u nizu. Algoritam se prekida kada je prvi sledeci element manji od prethodnog.

 

[Switch]

Ok, onda cemo naci nesto zanimljivije.

 

[WebWolf]

Ovo je izuzetno prost zadatak. Svodi se na jednu brojacku promenjivu i na odredjivanje maksimuma u nizu. Algoritam se prekida kada je prvi sledeci element manji od prethodnog.

Nigde nije receno da se prekida tada. Moze da ide 182, 192, 180, 188, 190, 170, 156, 200, 199. Vide se prva dva i predzadnji.

 

[ivan90BG]

^Nije zadnji već predzadnji.

 

[WebWolf]

^Nije zadnji već predzadnji.

Predzadnji, pardon . Dodao sam jos jednog na kraju, a nisam stavio pred* .

 

[drfedja]

Nigde nije receno da se prekida tada. Moze da ide 182, 192, 180, 188, 190, 170, 156, 200, 199. Vide se prva dva i predzadnji.

To se prakticno svodi na isto, s' tim sto u ovom slucaju program prolazi n koraka, slozenost je uvek O.
Ako hoce da cepidlaci, moze da trazi da se koristi Talesova teorema, ali pri tom mora da bude data i visina "kasirke".
Tako bi mogli da izracunamo koliko koji zaklanja sledeceg. :d
Pri tom mozes da napravis optimalan ili manje optimalan algoritam. Za racunanje trigonometrijskih funckija najbolje je koristiti tabelu, jer je racunanje trig. funkcija skupo. :d

 

[Bahati [SiD]]

algo je dat, samo zbunjujete momka.

 

[Switch]

Ma ne zbunjuju me, bar što se tiče matematičkog dela (talesova teorema). Evo postaviću još jedan zadatak.
Zadatak 3. U sudu se nalazi v litara p% rastvora soli. Iz suda se odlije a litara mešavine i dolije a litara čiste vode, poste čega se rastvor meša. Ako se N puta vrši odlivanje i dolivanje napisati program kojim se ispisuje tabela koncetracije soli u sudu posle svakod odlivanja i dolivanja.

 

[ivan90BG]

Mislim da je ovo zadovoljvajuće:

[B]program[/B] RastvorSoli;

[B]uses[/B] sysutils;

[B]var[/B]
v, p, a:[B]float[/B];
DaNe:[B]char[/B];
podaci:[B]string[/B];
n:[B]integer[/B];

[B]begin[/B]

podaci:='Zasicenosi rastvora po izmenama:#13#10';

write('Upisite zapreminu rastvora u litrima: ');
readln(v);

write('Upisite količinu soli u rastvoru u procentima: ');
readln(p);

n:=1;
[B]while[/B] DaNe = 'd' [B]or[/B] DaNe = 'D' [B]do[/B]
[B]begin[/B]
write('Koliko litara se menja vodom: ');
read(a);

p:=(p*v-p*a)/v;

podaci:=podaci+IntToStr(n)+': '+FloatToStr(p)+'#13#10';

n:=n+1;

write(' nastavljate? (d/n): ')
readln(DaNe);

[B]end;[/B]

write(podaci);
readln;

[B]end.[/B]

 

[Bahati [SiD]]

ovo je zgodna stvarcica za racunanje kolika je prevara homeopatija:

V = 100 (npr 100ml "otrova")
a = 99 ("C" homeopatski rastvor, u svakom razblazivanju ostaje 1 stoti deo od prethodne kolicine)
p = 1 (pocinje se se full "otrovom", 100%, mada sta to uopste znaci...)
n = 30 (najcesce se prepisuje 30C rastvor, tj. 30 razblazivanja)

izadje da je p na kraju 10^-60. sto se poklapa sa tabelom ovde.

btw, ovo je nerekurzivna formula pn = (V-a)^n * p0 / V^n koju sam ja koristio, mada ti i ne treba posto svakako moras da ulazis u nekakvu petlju za ispis. mene je samo zanimao kraj...

 

[ivan90BG]

Sad treba Switch da nam kaže da li program treba da primi broj razblaživanja u napred i da se za svako zamenjuje ista količina vode ili da se za svako razblaživenje unosi količina rastvora koja se menja čistom vodom.

U prvom slučaju ne treba string jer bi petlja direktno na ekranu ispisivala rezultat svakog razblaživanja i ne bi tražila unos od strane korisnika pa je program znatno prostiji.

[B]program[/B] RastvorSoli;

[B]var[/B]
v, p, a:[B]float[/B];
n, i:[B]integer[/B];

[B]begin[/B]

write('Upisite zapreminu rastvora u litrima: ');
readln(v);

write('Upisite količinu soli u rastvoru u procentima: ');
readln(p);

write('Koliko litara se menja vodom: ');
readln(a);

write('Koliko puta: ');
readln(n);

writeln('Zasićenosti rastvora po izmenama:');
[B]for[/B] i:=1 [B]to[/B] n [B]do[/B]
begin

p:=(p*v-p*a)/v;

writeln(i,': ',p,'%');

[B]end;[/B]

readln;

[B]end.[/B]

 

[yooyo]

Ako se dobro secam, evo jednog zadatka koji je svojevremeno bio u casopisu Racunari:

Kapetan broda je imao posadu od 200 clanova. Dugo su plovili pa su na kraju pristali u malu luku i svi mornari su pojurili u provod. Medjutim, mesto u kome su pristali je malo.. imalo je samo jednu ulicu koja se zavrsavala u luci. Ulica je imala 10 bandera. Svi mornari su odmah po izlasku pitali gde ima najbliza kafana. Stanovnici su im rekli da je najbliza kafana kod 7. bandere... i svi su pojurili tamo.

Kada su usli u kafanu poceli su da piju.. Oko ponoci, gazda kafane objavio fajront i mornari su morali da izadju. Medjutim neko im je rekao da postoji jos jedna kafana kod 10. bandere koja radi celu noc. Polupijani i pijani mornari izlaze iz prve kafane i udaraju u banderu.. da ne bi pali, zadrze se za banderu ali se okrenu nekoliko puta oko nje i nastave da hodaju ili u pravcu luke ili u suprotnom pravcu (ka kafani kod 10. bandere). Kad opet naidje na sledecu banderu opet je udari i opet se okrene par puta i nastavi u jednom ili drugom smeru (ka luci ili ka kafani kod 10. bandere).
- Ako dodje do kafane kod 10. bandere uci ce unutra, jos vise ce se napiti i potuci ce se i na kraju ce serif da ga uhapsi i smesti u zatvor. Kazna za izazivanje tuce je $200.
- Ako dodje do luke, pasce u vodu, i istreznice se momentalno, popece se na brod i nastaviti da spava
- Ako 10 puta udari u banderu zaspace na ulici. Serif ce ga pokupiti i strpati u zatvor. Kazna za spavanje na ulici u alkoholisanom stanju je $30.

Pitanje glasi.. koliko ce novca kapetan morati da isplati da bi izvadio sve mornare iz zatvora?

 

[WebWolf]

Pa ovo je cist random. Mislim, moguce je napraviti program. . Recimo da bih uzeo mornara i 10 puta uradio nasumicno pomeranje levo ili desno od broja 7 i racunao koja je bandera u pitanju. Ako usled nasumicnog pomeranja dosao do bandere 0, onda nista (na brodu je), ako dodje do bandere 10, odmah bih racunao $200, a ako 10 puta uradi taj random bez toga da je dosao do vode ili bandere 10, onda bih racunao $30. I tako za svih 200 mornara. Teoretski to moze da bude bilo koji broj izmedju 0 i $4000000 (jadan kapetan). E sad ovo je za slucaj da izlaze mornar po mornar. Ako izlaze vise njih, ili svi odjednom to otvara mnogo veci broj pitanja koja nisu odgovorena u tekstu, tako da sumnjam da je tako zamisljeno.

 

[Matori]

Bozanstven zadatak! A ja ne smem ni pomisliti da se udubim, dok ne predam zavrsni racun za 2009. :rupa:
Nadam se da niko nece objaviti nista znacajno do pocetka marta...

@yooyo
Nemoj nikome da pomazes! Na potpitanja odgovaraj kao Pitija :-devil-: ,)

@WebWolf
Pa nije bas random, verujem da uz pomoc Markovljevih lanaca moze prilicno egzaktno da se uradi. Ali i bez njih, moze sasvim lepo da se procenjuje - ako njih 200 udari u banderu, racunaj da ce 100 da podje prema kafani, a 100 prema luci...

 

[Bahati [SiD]]

1) graf, nodovi 0-10, susedni medjusobno povezani u oba smera (<->), sem 1->0 i 9->10. izbrojis sve puteve koji pocinju iz noda 7, da zadovoljavaju uslove po duzini i nodovima kroz koje prolaze (zavrsavaju se) i sracunas verovatnoce...

2) nekakav monte karlo... (ja bi sve u zivotu tako :d)

3) neko moje quick & dirty resenje koje kaze ~7053,5$

jel blizu?

naravno, sve je to pitanje verovatnoce, u smislu resenje je ono sto je najverovatnije.

ps. ima raznih detalja koje sam podrazumevao: cim izadje iz prve kafane udara u banderu i to mu se racuna. ako mu je 10-i udarac u 10-u banderu spava, ne ulazi u kafanu.

 

[WebWolf]

Najbolje da mi to prakticno isprobamo :d . Skupimo se nas 201, izponapijamo kao stoka pa zapnemo niz i uz ulicu.

P.S
Onaj 1 nam treba da broji .

 

[marko_n]

Pitanje glasi.. koliko ce novca kapetan morati da isplati da bi izvadio sve mornare iz zatvora?

Približno $11970? :bottle:

 

[WebWolf]

Ja sam dobijam $17670 ovim mojim algoritmom... Random bas i nije random . Dobijam isti broj onih sto su se izvukli, zaspali na ulici i uhapsenih... Naivno od mene. Jos nisam slusao verovatnocu (u ovom semestru pocinjem), tako da bih trebao da se javim za 6 meseci .

Hocete mi samo objasniti kako ste dobili brojeve koji imaju za cifru jedinice razlicit broj od 0, kada racunanje ide u koracima od 30 i 200?

 

[marko_n]

Moje je average vrednost velikog broja slučajeva.

A 17670 je šta?

 

[yooyo]

Zadatak je bio postavljen u casopisu Racunari br 27. Sigurno ga nisam preneo identicno tako da postoje odredjene nelogicnosti. Uglavnom...
- mornari izlaze jedan po jedan
- ako deseti udarac u banderu bude bas na desetoj banderi zaspace na ulici.