Python stazaCjelina 4 · Prvi algoritmiLekcija 22

Simulacija

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).

DioPitanjeU programu
stanjeŠto se mijenja?varijable (položaj, bodovi, lista lampica…)
pravilaKako se mijenja u jednom koraku?if i računanje
ponavljanjeKoliko 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 = 0
while n != 1:
    if n % 2 == 0:
        n = n // 2
    else:
        n = 3 * n + 1
    koraka += 1
print(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 in range(n + 1):
    upaljena.append(False)
for k in range(1, n + 1):
    for i in range(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 in range(n + 1):
    upaljena.append(False)
for k in range(1, n + 1):
    for i in range(k, n + 1, k):
        upaljena[i] = not upaljena[i]
for i in range(1, n + 1):
    if upaljena[i]:
        print(i, end=" ")

5Savjeti za simulaciju

6Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

Što je simulacija?

Pitanje

Kada simulacija nije dobra ideja?

Pitanje

Robot dobije naredbu U (gore). Što se mijenja?

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?

Ulaz
Jedan redak s naredbama, bez razmaka.
Izlaz
Dva broja x i y, odvojena razmakom.
Ograničenja
Naredbi ima od 1 do 1000.
Ulaz
RRUL
Izlaz
1 1
Ulaz
DDDL
Izlaz
-1 -3
Riješi u evaluatoru

Do jedinice

★★☆ srednje

Ako je broj paran, podijeli ga s 2, a ako je neparan, pomnoži ga s 3 i dodaj 1. Koliko koraka treba da se od N dođe do 1?

Ulaz
Jedan prirodni broj N.
Izlaz
Broj koraka.
Ograničenja
1 ≤ N ≤ 1 000 000
Ulaz
6
Izlaz
8
Riješi u evaluatoru

Dizalo

★★☆ srednje

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.

Riješi u evaluatoru

Lampice

★★★ teže

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.

Riješi u evaluatoru
Vježbaj dalje: zadaci s natjecanja

Ovi zadaci s Infokupa traže upravo ovo gradivo. Kreni od prvoga.

  1. Sto Infokup 2017 · županijsko · 5. r. OŠ
  2. Robot Infokup 2018 · županijsko · 7. r. OŠ
  3. Zmija Infokup 2023 · županijsko · 7. i 8. r. OŠ
  4. Ruka Infokup 2019 · županijsko · 8. r. OŠ

8Što smo naučili

  • Simulacija: stanje (varijable), pravila (if, računanje) i ponavljanje (for, while).
  • Prvo odsimuliraj primjer na papiru.
  • Stanje može biti i lista; indeks 0 smijemo preskočiti da brojevi odgovaraju indeksima.
  • Procijeni broj koraka prije nego napišeš simulaciju.
Najčešće greške

Krivo shvaćeno pravilo · krivo početno stanje · simulacija s previše koraka · zamijenjeni x i y