Python stazaCjelina 4 · Prvi algoritmiLekcija 23

Isprobaj sve mogućnosti

Koliko je kokoši, a koliko zečeva na farmi? Ne treba nam jednadžba. Računalo je dovoljno brzo da isproba svaku mogućnost i nađe onu pravu.

Pythonoko 45 minuta4 zadatka za evaluator

1Ideja: provjeri svaku mogućnost

Na farmi su kokoši i zečevi. Ukupno imaju 10 glava i 32 noge. Koliko je kokoši, a koliko zečeva? Mogli bismo postaviti jednadžbe. Ali računalo može i jednostavnije: isprobati sve mogućnosti. Kokoši može biti 0, 1, 2, … 10, a zečeva je onda ostatak do 10 glava. Za svaku mogućnost provjerimo broj nogu.

k–
z–
ispis–
Klikni „Sljedeći korak“ i prati što se događa.
Ključna ideja

Ovaj pristup zovemo gruba sila (engl. brute force). Nije elegantan, ali je jednostavan i siguran: ako je mogućnosti malo, računalo ih provjeri u trenu.

2Dvije nepoznanice: petlja u petlji

Olovka košta 3 eura, a bilježnica 5 eura. Na koliko načina možemo potrošiti točno 30 eura? Sada isprobavamo svaki broj olovaka i, za svaki od njih, svaki broj bilježnica.

Program
nacina = 0
for o in range(0, 11):
    for b in range(0, 7):
        if 3 * o + 5 * b == 30:
            print(o, "olovaka i", b, "bilježnica")
            nacina += 1
print(nacina)
Ispis
0 olovaka i 6 bilježnica 5 olovaka i 3 bilježnica 10 olovaka i 0 bilježnica 3
Stani i razmisli

Zašto olovaka ima najviše 10, a bilježnica najviše 6?

Pogledaj odgovor

Za 30 eura stane najviše 30 / 3 = 10 olovaka i 30 / 5 = 6 bilježnica. Veće brojeve nema smisla provjeravati.

Ključna ideja

Jednu petlju često možemo uštedjeti: kad znamo broj olovaka o, ostatak novca je 30 − 3 · o. Bilježnica je onda (30 − 3 · o) / 5, ako je to cijeli broj, to jest ako je (30 − 3 · o) % 5 == 0.

3Svi parovi iz liste

Česta gruba sila: provjeri svaki par elemenata liste. Koliko parova brojeva ima zbroj točno K?

Program
a = [3, 7, 1, 9, 5]
k = 10
parova = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] + a[j] == k:
            print(a[i], a[j])
            parova += 1
print(parova)
Ispis
3 7 1 9 2
Ključna ideja

Unutarnja petlja kreće od i + 1. Tako svaki par provjerimo točno jednom i nikad ne sparimo element sa samim sobom.

Pazi

Da unutarnja petlja kreće od 0, par (3, 7) bismo brojali dvaput, kao (3, 7) i (7, 3), a 5 + 5 bi se pogrešno brojalo kao par.

4Koliko je to mogućnosti?

Gruba sila radi samo kad mogućnosti nije previše. Prije pisanja procijeni koliko puta će se izvršiti unutarnji dio petlje.

PetljeN = 100N = 1000N = 100 000
jedna petlja do N1001000100 000
svi parovioko 5000oko 500 000oko 5 milijardi
sve trojkeoko 160 000oko 170 milijunapreviše
Ključna ideja

Python u sekundi napravi otprilike nekoliko milijuna jednostavnih koraka. Što je više od toga, neće stići u vremenskom ograničenju. Više o tome u lekciji 25.

Na natjecanju

Gruba sila je odličan prvi pokušaj: donosi bodove za male ulaze, a kasnije pomaže provjeriti brže rješenje na istim primjerima.

5Provjeri se

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

Pitanje

Koliko parova (i, j) s i < j ima među 100 elemenata?

Pitanje

Kada je gruba sila (isprobaj sve) dovoljno brza?

Pitanje

Zašto je gruba sila dobra na natjecanju i kad je spora?

6Zadaci

Kokoši i zečevi

★☆☆ lagano

Na farmi su kokoši i zečevi. Znamo ukupan broj glava i nogu. Koliko je kokoši, a koliko zečeva?

Ulaz
Jedan redak s brojem glava G i brojem nogu N.
Izlaz
Broj kokoši i broj zečeva, odvojeni razmakom. Ako takav raspored ne postoji, ispiši NEMA.
Ograničenja
1 ≤ G ≤ 1000, 1 ≤ N ≤ 4000
Ulaz
10 32
Izlaz
4 6
Ulaz
3 7
Izlaz
NEMA
Riješi u evaluatoru

Kupovina

★★☆ srednje

Olovka košta A eura, a bilježnica B eura. Na koliko načina možemo potrošiti točno M eura? Smijemo kupiti i nula olovaka ili nula bilježnica.

Ulaz
Jedan redak s brojevima A, B i M.
Izlaz
Broj načina.
Ograničenja
1 ≤ A, B ≤ 100, 1 ≤ M ≤ 10 000
Ulaz
3 5 30
Izlaz
3
Treba ti pomoć?

Petlja po broju olovaka. Za svaki broj olovaka provjeri može li se ostatak novca točno potrošiti na bilježnice.

Riješi u evaluatoru

Parovi

★★☆ srednje

Koliko parova brojeva iz liste ima zbroj točno K? Par čine dva različita elementa liste (po mjestu).

Ulaz
U prvom retku N i K. U drugom retku N cijelih brojeva.
Izlaz
Broj parova.
Ograničenja
2 ≤ N ≤ 1000, brojevi i K su od −1000 do 1000
Ulaz
5 10 3 7 1 9 5
Izlaz
2
Ulaz
4 4 2 2 2 1
Izlaz
3
Riješi u evaluatoru

Tri karte

★★★ teže

Na stolu je N karata s brojevima. Izaberi tri karte tako da im je zbroj što veći, ali ne veći od M. Koliki je taj zbroj?

Ulaz
U prvom retku N i M. U drugom retku N brojeva na kartama.
Izlaz
Najveći mogući zbroj tri karte koji nije veći od M. Takve tri karte sigurno postoje.
Ograničenja
3 ≤ N ≤ 100, 1 ≤ M ≤ 300 000, brojevi su od 1 do 100 000
Ulaz
5 21 5 6 7 8 9
Izlaz
21
Ulaz
4 20 9 3 12 7
Izlaz
19
Treba ti pomoć?

Isprobaj sve trojke: tri petlje, svaka kreće od jedan više od prethodne. Za N = 100 to je oko 160 000 trojki, što je brzo.

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

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

  1. Kocka Infokup 2021 · školsko · 7. r. OŠ
  2. Strah Infokup 2019 · županijsko · 7. r. OŠ
  3. Čarape Infokup 2021 · županijsko · 8. r. OŠ

7Što smo naučili

  • Gruba sila (brute force): isprobaj sve mogućnosti i provjeri svaku.
  • Dvije nepoznanice: petlja u petlji; jednu petlju često zamijeni račun.
  • Svi parovi: unutarnja petlja od i + 1.
  • Prije pisanja procijeni broj mogućnosti: nekoliko milijuna je u redu, milijarde nisu.
Najčešće greške

Granice petlje koje preskoče neku mogućnost · par brojan dvaput · gruba sila s previše mogućnosti