Czego się nauczysz
Lider ciągu to wartość, która zajmuje więcej niż połowę miejsc. Takie pytania pojawiają się w zadaniach o głosowaniach, ankietach i pomiarach: czy któraś odpowiedź ma bezwzględną większość? Nauczysz się trzech sposobów szukania lidera, w tym algorytmu, który robi to w jednym przejściu i pamięta tylko dwie liczby.
Po co ci to na maturze
Zadania o głosowaniach, ankietach i pomiarach pytają, czy któraś odpowiedź ma ponad połowę głosów. Przy dużym pliku warto umieć odpowiedzieć na to jednym przejściem przez dane.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Kto jest lideremWięcej niż połowa, a nie najwięcej. Nie każdy ciąg ma lidera.
- 1.2Zliczanie słownikiemPolicz każdą wartość i sprawdź, czy któraś ma ponad połowę.
- 1.3Skreślanie parPary różnych wartości odpadają, a lider zostaje. Wystarczą do tego dwie zmienne: kandydat i licznik.
- 1.4Lider stoi na środkuPo posortowaniu lider, jeśli istnieje, zajmuje środkowe miejsce.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.