Robot se kreće po ploči, domar pali i gasi lampice, dizalo vozi s kata na kat. Kad zadatak opiše što se događa, program to samo treba vjerno ponoviti.
Pythonoko 45 minuta4 zadatka za evaluator
1Što je simulacija
U mnogim zadacima nema skrivenog trika. Zadatak opiše što se događa, korak po korak, a program to samo vjerno ponovi. Takav pristup zovemo simulacija (engl. simulation).
Dio
Pitanje
U programu
stanje
Što se mijenja?
varijable (položaj, bodovi, lista lampica…)
pravila
Kako se mijenja u jednom koraku?
if i računanje
ponavljanje
Koliko koraka, ili do kada?
for ili while
Ključna ideja
Prije programiranja odgovori na tri pitanja iz tablice. Kad znaš stanje, pravila i koliko puta ponavljaš, program se gotovo sam napiše.
2Robot na ploči
Robot kreće s polja (0, 0). Dobije niz naredbi: R desno, L lijevo, U gore, D dolje. Gdje će završiti? Stanje su koordinate x i y, pravilo je kako svaka naredba mijenja koordinate, a ponavljamo za svako slovo naredbe.
n–
x–
y–
Klikni „Sljedeći korak“ i prati što se događa.
3Simulacija do zaustavljanja
Ponekad ne znamo unaprijed koliko će koraka biti. Poznata igra s brojevima: ako je broj paran, podijeli ga s 2. Ako je neparan, pomnoži ga s 3 i dodaj 1. Ponavljaj dok ne dođeš do 1. Koliko koraka treba?
n = int(input())
koraka = 0while n != 1:
if n % 2 == 0:
n = n // 2else:
n = 3 * n + 1
koraka += 1print(koraka)
Ulaz
6
Ispis
8
Za 6 niz je: 6, 3, 10, 5, 16, 8, 4, 2, 1. To je 8 koraka.
Stani i razmisli
Je li sigurno da ova petlja uvijek stane?
Pogledaj odgovor
Matematičari to ne znaju dokazati! Za sve brojeve koje su ljudi ikad isprobali niz dođe do 1, ali dokaz još nitko nije našao. Za brojeve iz zadataka slobodno pretpostavi da stane.
4Simulacija s listom
Stanje može biti i cijela lista. U hodniku je N lampica, sve ugašene. Domar prolazi hodnikom N puta. U k-tom prolazu pritisne prekidač svake k-te lampice: upaljenu ugasi, a ugašenu upali. Koliko je lampica upaljeno na kraju?
n = int(input())
upaljena = []
for i inrange(n + 1):
upaljena.append(False)
for k inrange(1, n + 1):
for i inrange(k, n + 1, k):
upaljena[i] = not upaljena[i]
print(upaljena.count(True))
Ulaz
10
Ispis
3
Ključna ideja
Lista ima n + 1 elemenata, a element s indeksom 0 ne koristimo. Tako je lampica broj i baš na indeksu i, što smanjuje zabune. not okreće stanje lampice: True postaje False i obrnuto.
Probaj sam
Pokreni program za n = 100 i ispiši koje su lampice upaljene. Vidiš li pravilo?
Pogledaj rješenje
n = int(input())
upaljena = []
for i inrange(n + 1):
upaljena.append(False)
for k inrange(1, n + 1):
for i inrange(k, n + 1, k):
upaljena[i] = not upaljena[i]
for i inrange(1, n + 1):
if upaljena[i]:
print(i, end=" ")
5Savjeti za simulaciju
Pročitaj pravila dvaput. Najviše grešaka nastaje zbog krivo shvaćenog pravila, a ne zbog programiranja.
Odsimuliraj primjer na papiru. Ako ti na papiru ispadne drugačije nego u primjeru, krivo si shvatio pravilo.
Pazi na početno stanje: od čega kreće brojač, gdje je robot na početku, broji li se početni korak.
Procijeni broj koraka. Milijun koraka program napravi brzo. Milijardu koraka u Pythonu neće stići; tada treba pametnije rješenje.
6Provjeri se
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
Pitanje
Što je simulacija?
Program radi točno ono što zadatak opisuje, korak po korak.
Pitanje
Kada simulacija nije dobra ideja?
Tada treba pametnije rješenje.
Pitanje
Robot dobije naredbu U (gore). Što se mijenja?
Kao u lekciji: U znači y += 1, D znači y -= 1, R znači x += 1, L znači x -= 1.
7Zadaci
Robot
★☆☆ lagano
Robot kreće s polja (0, 0) i izvrši niz naredbi: R desno, L lijevo, U gore, D dolje. Na kojem polju završi?
Dizalo je na katu 0. Redom stižu pozivi s raznih katova, a dizalo ide na svaki od njih, jedan za drugim. Koliko je katova ukupno prešlo?
Ulaz
U prvom retku N. U drugom retku N katova, redom kojim stižu pozivi.
Izlaz
Ukupan broj prijeđenih katova.
Ograničenja
1 ≤ N ≤ 1000, katovi su od 0 do 100
Ulaz
4
5 2 8 8
Izlaz
14
Treba ti pomoć?
Stanje je kat na kojem je dizalo. Za svaki poziv dodaj razliku između katova, pazeći da razlika ne bude negativna. Pomoći može gotova funkcija abs: abs(-3) je 3.
U hodniku je N lampica, sve ugašene. Domar prolazi N puta: u k-tom prolazu pritisne prekidač svake k-te lampice. Koliko je lampica upaljeno nakon K prolaza?
Ulaz
Jedan redak s brojevima N i K.
Izlaz
Broj upaljenih lampica nakon K prolaza.
Ograničenja
1 ≤ K ≤ N ≤ 10 000
Ulaz
10 2
Izlaz
5
Ulaz
10 10
Izlaz
3
Treba ti pomoć?
Kao u dijelu 4, ali vanjska petlja ide samo do K. Odsimuliraj primjer s N = 10 i K = 2 na papiru.