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 = 0for o inrange(0, 11):
for b inrange(0, 7):
if3 * o + 5 * b == 30:
print(o, "olovaka i", b, "bilježnica")
nacina += 1print(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 = 0for i inrange(len(a)):
for j inrange(i + 1, len(a)):
if a[i] + a[j] == k:
print(a[i], a[j])
parova += 1print(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.
Petlje
N = 100
N = 1000
N = 100 000
jedna petlja do N
100
1000
100 000
svi parovi
oko 5000
oko 500 000
oko 5 milijardi
sve trojke
oko 160 000
oko 170 milijuna
previš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?
100 · 99 / 2 = 4950.
Pitanje
Kada je gruba sila (isprobaj sve) dovoljno brza?
Procijeni broj mogućnosti iz ograničenja.
Pitanje
Zašto je gruba sila dobra na natjecanju i kad je spora?
Djelomični bodovi i provjera.
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.