|
Jučer je održano natjecanje iz informatike (školska razina). Za 7. razred OŠ postavljen je ovaj zanimljivi zadatak.
[quote][b]Zadatak: Bomboni[/b] (90 bodova)
U dječjem vrtiću "Tulipan" odgajateljica je djeci podijelila bombone. Ali, jao! Neka djeca dobila su manje bombona od drugih.
Reći ćemo da je neko dijete [b]uplakano[/b] ako svako drugo dijete ima strogo više bombona od njega. Odgajateljica je slaba na suze pa se i sama rasplače kad vidi uplakano dijete. Ona tada posegne za golemom vrećom bombona i uplakanom djetetu [b]udvostruči[/b] broj bombona. Na primjer, ako uplakano dijete ima 3 bombona, dobit će još 3 bombona pa će imati 6 bombona.
Ako se tada opet pojavi neko uplakano dijete, odgajateljica će učiniti isto, i taj će se postupak ponavljati dok god postoji bilo koje uplakano dijete. Ako u nekom trenutku [b]nijedno[/b] dijete više nije uplakano, što znači da nijedno dijete nema manje bombona od svakog drugog djeteta, postupak se zaustavlja. Moguće je i da se postupak ponavlja [b]beskonačno[/b], a u tom će slučaju odgajateljica naručivati nove bombone iz tvornice kad god joj ponestane bombona. (Još nije poznato kako će ih platiti.)
Napiši program koji, za dane početne količine bombona svakog djeteta, ispisuje njihove konačne količine bombona ako se postupak zaustavi, ili riječ "INFINITY" ako će postupak trajati beskonačno.
[b]ULAZNI PODACI[/b]
U prvom retku nalazi se prirodan broj [i]N[/i] (2≤[i]N[/i]≤10), broj djece. U sljedećih [i]N[/i] redaka nalaze se prirodni brojevi, manji od 100. To su količine bombona koje su dobila djeca od prvog do [i]N[/i]-tog.
[b]IZLAZNI PODACI[/b]
Ako se postupak u nekom trenutku zaustavlja, u jedini redak ispiši završni niz količina bombona, odvojene razmakom. Ako postupak traje beskonačno, ispiši samo riječ "INFINITY".
[b]PRIMJERI TEST PODATAKA[/b]
[b]ulaz[/b]
2
5
6
[b]izlaz[/b]
INFINITY
[b]ulaz[/b]
5
14
6
8
10
12
[b]izlaz[/b]
14 12 16 20 12
[/quote]
Kao što vidite sastavljači zadataka su se zbilja potrudili, čak i oko humora. (Odgajateljice, ne brini! Lokalni izbori se bliže i gradonačelnik će sigurno platiti beskonačnu narudžbu bombona.) Osim ovog zadatka sedmašima su zadali još dva lakša zadatka, a ovaj je zanimljiv jer ima dvije razine. Prvo treba razumjeti algoritam po kojem odgajateljica postupa dok ima uplakane djece - nazovimo ga [b]algoritam za odplakivanje[/b]. Recimo da su početne količine bombona spremljene u niz [i]a[/i].
[code:1]1. Pronađi minimalni element niza a.
2. Ako je jedinstven, pomnoži minimalni element s 2 i vrati se na korak 1; inače ispiši niz.
[/code:1]
Problem je što za neke nizove algoritam ne završava za konačno mnogo koraka. To treba prepoznati i ispisati poruku "INFINITY". Zadatak bi se mogao riješiti "inžinjerskim pristupom" (pokrenemo algoritam za odplakivanje i zaustavimo ga ako ne završi u nekom vremenu), ali nismo FER-ovci nego matematičari i nećemo se time zadovoljiti. Dakle, tražimo karakterizaciju nizova za koje odplakivanje traje beskonačno, i to takvu koja se može provjeriti u konačno mnogo koraka! Neka je [i]h[/i]([i]a[/i])=1 ako algoritam odplakivanja za niz [i]a[/i] završava u konačno mnogo koraka, a [i]h[/i]([i]a[/i])=0 inače. Kad smislimo konačan algoritam za izračunavanje funkcije [i]h[/i], ovako izgleda rješenje zadatka.
[code:1]1. Učitaj niz a.
2. Izračunaj h(a). Ako je h(a)=0 ispiši "INFINITY", a inače izvedi algoritam za odplakivanje.
[/code:1]
Tko se prvi dosjeti algoritma za [i]h[/i]([i]a[/i]) i opiše ga ovdje na forumu, dobiva peticu iz zalaganja i celebrity status na usmenom :D (Molim sve koji nisu upisali Osnove algoritama 2016./17. da [b]ne[/b] pišu rješenje!) Inače, ovo je specijalni slučaj takozvanog [url=https://en.wikipedia.org/wiki/Halting_problem]halting problema[/url]. Treba algoritamski provjeriti završava li zadani algoritam sa zadanim ulazom u konačno mnogo koraka, ili se izvodi beskonačno. U specijalnom slučaju algoritma za odplakivanje to je moguće napraviti, ali općenito je taj problem [b]neodlučiv[/b]. To znači da [b]ne postoji[/b] algoritam za izračunavanje generalizirane funkcije [i]h[/i]. Svih mogućih programa i svih ulaznih podata ima prebrojivo beskonačno, tj. možemo ih indeksirati prirodnim brojevima. Funkcija [i]h[/i] definirana je ovako: [i]h[/i]([i]m[/i],[i]n[/i])=1 ako [i]m[/i]-ti program s [i]n[/i]-tim ulaznim podacima završava u konačno koraka, a [i]h[/i]([i]m[/i],[i]n[/i])=0 inače.
Alan Turing je 1936. dokazao da ne postoji algoritam za tako generaliziranu funkciju [i]h[/i]. Dokaz podsjeća na paradoks o brici: "Brico brije sve ljude u selu koji ne briju sami sebe. Tko brije bricu?". Ako brico brije sam sebe, onda se ne brije. Ako se ne brije, onda se brije. Dakle, takav brico ne postoji. Slično, pretpostavimo da možemo napisati program koji izračunava [i]h[/i]([i]m[/i],[i]n[/i]). Promotrimo ovaj program:
[code:1]1. Učitaj m.
2. Izračunaj h(m,m). Ako je h(m,m)=1, onda uđi u beskonačnu petlju, a inače stani.
[/code:1]
Neka je to [i]m[/i]-ti program. Što je [i]h[/i]([i]m[/i],[i]m[/i])? Ako je 1, program će ući u beskonačnu petlju i trebalo bi biti 0, a ako je 0 stat će i trebalo bi biti 1. Dakle, takav program ne postoji, tj. funkcija [i]h[/i] nije izračunljiva.
U zadatku s natjecanja treba smisliti algoritam za restrikciju funkcije [i]h[/i] kad se za prvu varijablu uvrsti broj koji odgovara algoritmu za odplakivanje.
Jučer je održano natjecanje iz informatike (školska razina). Za 7. razred OŠ postavljen je ovaj zanimljivi zadatak.
| Citat: | Zadatak: Bomboni (90 bodova)
U dječjem vrtiću "Tulipan" odgajateljica je djeci podijelila bombone. Ali, jao! Neka djeca dobila su manje bombona od drugih.
Reći ćemo da je neko dijete uplakano ako svako drugo dijete ima strogo više bombona od njega. Odgajateljica je slaba na suze pa se i sama rasplače kad vidi uplakano dijete. Ona tada posegne za golemom vrećom bombona i uplakanom djetetu udvostruči broj bombona. Na primjer, ako uplakano dijete ima 3 bombona, dobit će još 3 bombona pa će imati 6 bombona.
Ako se tada opet pojavi neko uplakano dijete, odgajateljica će učiniti isto, i taj će se postupak ponavljati dok god postoji bilo koje uplakano dijete. Ako u nekom trenutku nijedno dijete više nije uplakano, što znači da nijedno dijete nema manje bombona od svakog drugog djeteta, postupak se zaustavlja. Moguće je i da se postupak ponavlja beskonačno, a u tom će slučaju odgajateljica naručivati nove bombone iz tvornice kad god joj ponestane bombona. (Još nije poznato kako će ih platiti.)
Napiši program koji, za dane početne količine bombona svakog djeteta, ispisuje njihove konačne količine bombona ako se postupak zaustavi, ili riječ "INFINITY" ako će postupak trajati beskonačno.
ULAZNI PODACI
U prvom retku nalazi se prirodan broj N (2≤N≤10), broj djece. U sljedećih N redaka nalaze se prirodni brojevi, manji od 100. To su količine bombona koje su dobila djeca od prvog do N-tog.
IZLAZNI PODACI
Ako se postupak u nekom trenutku zaustavlja, u jedini redak ispiši završni niz količina bombona, odvojene razmakom. Ako postupak traje beskonačno, ispiši samo riječ "INFINITY".
PRIMJERI TEST PODATAKA
ulaz
2
5
6
izlaz
INFINITY
ulaz
5
14
6
8
10
12
izlaz
14 12 16 20 12
|
Kao što vidite sastavljači zadataka su se zbilja potrudili, čak i oko humora. (Odgajateljice, ne brini! Lokalni izbori se bliže i gradonačelnik će sigurno platiti beskonačnu narudžbu bombona.) Osim ovog zadatka sedmašima su zadali još dva lakša zadatka, a ovaj je zanimljiv jer ima dvije razine. Prvo treba razumjeti algoritam po kojem odgajateljica postupa dok ima uplakane djece - nazovimo ga algoritam za odplakivanje. Recimo da su početne količine bombona spremljene u niz a.
| Kod: | 1. Pronađi minimalni element niza a.
2. Ako je jedinstven, pomnoži minimalni element s 2 i vrati se na korak 1; inače ispiši niz.
|
Problem je što za neke nizove algoritam ne završava za konačno mnogo koraka. To treba prepoznati i ispisati poruku "INFINITY". Zadatak bi se mogao riješiti "inžinjerskim pristupom" (pokrenemo algoritam za odplakivanje i zaustavimo ga ako ne završi u nekom vremenu), ali nismo FER-ovci nego matematičari i nećemo se time zadovoljiti. Dakle, tražimo karakterizaciju nizova za koje odplakivanje traje beskonačno, i to takvu koja se može provjeriti u konačno mnogo koraka! Neka je h(a)=1 ako algoritam odplakivanja za niz a završava u konačno mnogo koraka, a h(a)=0 inače. Kad smislimo konačan algoritam za izračunavanje funkcije h, ovako izgleda rješenje zadatka.
| Kod: | 1. Učitaj niz a.
2. Izračunaj h(a). Ako je h(a)=0 ispiši "INFINITY", a inače izvedi algoritam za odplakivanje.
|
Tko se prvi dosjeti algoritma za h(a) i opiše ga ovdje na forumu, dobiva peticu iz zalaganja i celebrity status na usmenom  (Molim sve koji nisu upisali Osnove algoritama 2016./17. da ne pišu rješenje!) Inače, ovo je specijalni slučaj takozvanog halting problema. Treba algoritamski provjeriti završava li zadani algoritam sa zadanim ulazom u konačno mnogo koraka, ili se izvodi beskonačno. U specijalnom slučaju algoritma za odplakivanje to je moguće napraviti, ali općenito je taj problem neodlučiv. To znači da ne postoji algoritam za izračunavanje generalizirane funkcije h. Svih mogućih programa i svih ulaznih podata ima prebrojivo beskonačno, tj. možemo ih indeksirati prirodnim brojevima. Funkcija h definirana je ovako: h(m,n)=1 ako m-ti program s n-tim ulaznim podacima završava u konačno koraka, a h(m,n)=0 inače.
Alan Turing je 1936. dokazao da ne postoji algoritam za tako generaliziranu funkciju h. Dokaz podsjeća na paradoks o brici: "Brico brije sve ljude u selu koji ne briju sami sebe. Tko brije bricu?". Ako brico brije sam sebe, onda se ne brije. Ako se ne brije, onda se brije. Dakle, takav brico ne postoji. Slično, pretpostavimo da možemo napisati program koji izračunava h(m,n). Promotrimo ovaj program:
| Kod: | 1. Učitaj m.
2. Izračunaj h(m,m). Ako je h(m,m)=1, onda uđi u beskonačnu petlju, a inače stani.
|
Neka je to m-ti program. Što je h(m,m)? Ako je 1, program će ući u beskonačnu petlju i trebalo bi biti 0, a ako je 0 stat će i trebalo bi biti 1. Dakle, takav program ne postoji, tj. funkcija h nije izračunljiva.
U zadatku s natjecanja treba smisliti algoritam za restrikciju funkcije h kad se za prvu varijablu uvrsti broj koji odgovara algoritmu za odplakivanje.
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
