Python stazaCjelina 4 · Prvi algoritmiLekcija 24

Rječnici, skupovi i n-torke

Tko je pobijedio na izborima? Koliko je različitih brojeva u listi? Kako složiti rang listu? Uz liste, Python ima još tri spremnika koja to čine lakim.

Pythonoko 45 minuta6 zadataka za evaluator

1Rječnik: ključ i vrijednost

Na izborima za predsjednika razreda svaki učenik napiše jedno ime. Kako prebrojati glasove za svakog kandidata? Za to služi rječnik (engl. dictionary, u Pythonu dict). Rječnik pamti parove: ključ i njegovu vrijednost, kao imenik u kojem uz svako ime piše broj.

Program
glasovi = {"Ana": 3, "Ivo": 5}
print(glasovi["Ana"])
glasovi["Ana"] += 1
glasovi["Marko"] = 1
print(glasovi)
print(len(glasovi))
Ispis
3 {'Ana': 4, 'Ivo': 5, 'Marko': 1} 3
ZapisŠto radi
{}prazan rječnik
d["Ana"]vrijednost uz ključ "Ana"
d["Marko"] = 1dodaje novi par ili mijenja postojeću vrijednost
"Ana" in dpostoji li ključ "Ana"
len(d)broj parova
d.values()sve vrijednosti (npr. max(d.values()) je najveća vrijednost)
Pazi

Čitanje ključa koji ne postoji javlja grešku KeyError. Prije čitanja provjeri s in.

2Brojanje pojava

Najčešća upotreba rječnika: koliko puta se svaka vrijednost pojavila. Za svaku novu vrijednost provjerimo je li već u rječniku. Ako jest, povećamo brojač; ako nije, dodamo je s brojem 1.

ime–
glasovi–
Klikni „Sljedeći korak“ i prati što se događa.

Kroz rječnik prolazimo petljom po ključevima. sorted(d) daje ključeve poredane po abecedi.

Program
glasovi = {"Ivo": 2, "Ana": 3, "Marko": 1}
for ime in sorted(glasovi):
    print(ime, glasovi[ime])
Ispis
Ana 3 Ivo 2 Marko 1

3Skup: samo različite vrijednosti

Skup (engl. set) pamti vrijednosti bez ponavljanja i bez redoslijeda. Ako dodamo nešto što već postoji, skup se ne mijenja.

Program
s = set()
s.add(5)
s.add(3)
s.add(5)
print(len(s))
print(3 in s)
print(len(set([4, 1, 4, 4, 2, 1])))
Ispis
2 True 3
Ključna ideja

len(set(lista)) je broj različitih elemenata liste. U lekciji 19 smo to radili sortiranjem; ovo je kraće.

4Zašto su rječnik i skup brzi

x in lista provjerava element po element, kao kad tražiš ime u neporedanom popisu. Za listu od 100 000 elemenata to je 100 000 usporedbi. x in skup i x in rjecnik odgovore gotovo odmah, bez obzira na veličinu.

ProvjeraLista od 100 000Skup od 100 000
x in ...do 100 000 korakaotprilike 1 korak
100 000 takvih provjerado 10 milijardi koraka: presporooko 100 000 koraka: brzo

Zato zadatak „Prvi ponovljeni“ iz lekcije 17 za velike ulaze rješavamo skupom umjesto liste:

vidjeni = set()
for x in map(int, input().split()):
    if x in vidjeni:
        print(x)
        break
    vidjeni.add(x)
Ulaz
4 7 2 7 4 1
Ispis
7
Ključna ideja

Ovdje nam treba samo prvi ponovljeni broj, pa nakon njega break iz lekcije 8 prekida petlju.

5N-torka: vrijednosti koje idu zajedno

Ponekad nekoliko vrijednosti uvijek ide zajedno: koordinate (x, y), bodovi i ime, sat i minuta. Za to služi uređena n-torka (engl. tuple): nekoliko vrijednosti u okruglim zagradama. Dvije vrijednosti čine par, tri trojku.

Program
tocka = (3, 5)
print(tocka[0])
print(tocka[1])
x, y = tocka
print(x + y)
Ispis
3 5 8
Pazi

N-torka se ne može mijenjati, kao ni string: tocka[0] = 7 javlja grešku. Ako trebaš drugu vrijednost, napraviš novu n-torku.

Raspakiravanje x, y = tocka već znaš iz recepta a, b = map(...). Isti trik zamijeni dvije varijable u jednom retku, bez treće varijable iz lekcije 2:

Program
a = 5
b = 9
a, b = b, a
print(a, b)
Ispis
9 5

6N-torke u skupu i rječniku

Lista ne može biti ključ rječnika ni element skupa, ali n-torka može. Tako lako pamtimo polja na ploči. Robot iz lekcije 22: na koliko je različitih polja stao, uključujući početno?

x = 0
y = 0
posjeceno = set()
posjeceno.add((x, y))
for n in input():
    if n == "R":
        x += 1
    elif n == "L":
        x -= 1
    elif n == "U":
        y += 1
    else:
        y -= 1
    posjeceno.add((x, y))
print(len(posjeceno))
Ulaz
RULD
Ispis
4
Ključna ideja

Robot je bio na (0, 0), (1, 0), (1, 1), (0, 1) i opet (0, 0). Skup pamti svako polje samo jednom, pa je odgovor 4.

7Sortiranje n-torki

Lista n-torki sortira se po prvom elementu, a kad su prvi jednaki, po drugom, i tako dalje. To je točno ono što treba za rang listu.

Program
rezultati = [(85, "Marko"), (92, "Ivo"), (85, "Ana")]
rezultati.sort()
print(rezultati)
Ispis
[(85, 'Ana'), (85, 'Marko'), (92, 'Ivo')]

Na rang listi želimo više bodova prvo, a kod jednakih bodova ime po abecedi. Trik: spremimo negativne bodove. Tada sortiranje od manjeg prema većem stavlja najviše bodova na početak, a imena ostaju po abecedi.

Program
rezultati = [(-85, "Marko"), (-92, "Ivo"), (-85, "Ana")]
rezultati.sort()
for bodovi, ime in rezultati:
    print(ime, -bodovi)
Ispis
Ivo 92 Ana 85 Marko 85
Ključna ideja

Petlja for bodovi, ime in rezultati: raspakira svaku n-torku u dvije varijable.

8Provjeri se

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

Pitanje

Brojimo pojave u rječniku d. Što napraviti s riječju w koje još nema u d?

Pitanje

Koliko je len(set([1, 2, 2, 3, 3, 3]))?

Pitanje

Zašto je x in skup brže nego x in lista?

9Zadaci

Različiti

★☆☆ lagano

Koliko je različitih brojeva u listi?

Ulaz
U prvom retku N. U drugom retku N cijelih brojeva.
Izlaz
Broj različitih brojeva.
Ograničenja
1 ≤ N ≤ 100 000
Ulaz
6 5 3 5 1 3 5
Izlaz
3
Riješi u evaluatoru

Izbori

★★☆ srednje

Svaki učenik napisao je ime jednog kandidata. Tko je pobijedio i s koliko glasova? Ako više kandidata ima najviše glasova, pobjeđuje onaj koji je prvi po abecedi.

Ulaz
U prvom retku N. U svakom od sljedećih N redaka jedno ime.
Izlaz
Ime pobjednika i broj njegovih glasova, odvojeni razmakom.
Ograničenja
1 ≤ N ≤ 1000, imena su od slova engleske abecede
Ulaz
5 Ana Ivo Ana Ivo Marko
Izlaz
Ana 2
Treba ti pomoć?

Prebroji glasove rječnikom. Zatim prođi ključevima poredanim po abecedi i traži najveći broj. Uvjet mora biti >, a ne >=, da kod jednakih ostane onaj koji je prvi po abecedi.

Riješi u evaluatoru

Prvi ponovljeni

★★☆ srednje

Brojevi stižu jedan po jedan. Koji je prvi broj koji se pojavio drugi put? Ako se nijedan ne ponavlja, ispiši 0.

Ulaz
U prvom retku N. U drugom retku N prirodnih brojeva.
Izlaz
Prvi broj koji se pojavi po drugi put, ili 0.
Ograničenja
1 ≤ N ≤ 100 000, brojevi su od 1 do 1 000 000 000
Ulaz
6 4 7 2 7 4 1
Izlaz
7
Ulaz
3 1 2 3
Izlaz
0
Treba ti pomoć?

Isti zadatak kao u lekciji 17, ali sada N može biti 100 000. S listom bi rješenje bilo presporo; upotrijebi skup.

Riješi u evaluatoru

Posjećena polja

★★☆ srednje

Robot kreće s polja (0, 0) i izvrši niz naredbi R, L, U i D. Na koliko je različitih polja stao, uključujući početno?

Ulaz
Jedan redak s naredbama, bez razmaka.
Izlaz
Broj različitih polja.
Ograničenja
Naredbi ima od 1 do 100 000.
Ulaz
RULD
Izlaz
4
Ulaz
RRLL
Izlaz
3
Riješi u evaluatoru

Rang lista

★★★ teže

Ispiši rang listu natjecanja: više bodova prvo, a kod jednakog broja bodova imena po abecedi.

Ulaz
U prvom retku N. U svakom od sljedećih N redaka ime i broj bodova, odvojeni razmakom.
Izlaz
N redaka: ime i bodovi, redom po rang listi.
Ograničenja
1 ≤ N ≤ 1000, imena su od slova engleske abecede, bodovi od 0 do 100
Ulaz
4 Marko 85 Ivo 92 Ana 85 Zara 70
Izlaz
Ivo 92 Ana 85 Marko 85 Zara 70
Treba ti pomoć?

Spremi svakog natjecatelja kao par (−bodovi, ime) i sortiraj listu parova, kao u dijelu 7.

Riješi u evaluatoru

Par sa zbrojem

★★★ teže

Postoje li u listi dva broja (na različitim mjestima) čiji je zbroj točno K?

Ulaz
U prvom retku N i K. U drugom retku N cijelih brojeva.
Izlaz
DA ili NE.
Ograničenja
2 ≤ N ≤ 100 000, brojevi su od −1 000 000 000 do 1 000 000 000, K je od −2 000 000 000 do 2 000 000 000
Ulaz
5 10 3 8 1 7 4
Izlaz
DA
Ulaz
3 10 5 1 2
Izlaz
NE
Treba ti pomoć?

Svi parovi iz lekcije 23 su presporo za 100 000 brojeva. Za svaki broj x zapitaj se: jesam li već vidio broj K − x? Brojeve koje si vidio pamti u skupu.

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

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

  1. Brazil Infokup 2014 · državno · 7. r. OŠ
  2. Imendan Infokup 2013 · županijsko · 8. r. OŠ
  3. Kripto Infokup 2017 · županijsko · 8. r. OŠ

10Što smo naučili

  • Rječnik (dictionary) pamti parove ključ → vrijednost: d[kljuc] = vrijednost.
  • Brojanje pojava: ako je ključ u rječniku, povećaj, inače dodaj s 1.
  • Skup (set) pamti samo različite vrijednosti: s.add(x), len(s).
  • in je u skupu i rječniku gotovo trenutan, a u listi spor.
  • N-torka (tuple) (85, "Ana") drži vrijednosti koje idu zajedno; ne mijenja se, može biti ključ i element skupa.
  • Lista n-torki sortira se po prvom, pa po drugom elementu.
Najčešće greške

Čitanje ključa koji ne postoji (KeyError) · lista umjesto skupa za velike ulaze · zaboravljen uvjet za izjednačene rezultate