BITEDU.PL

Specjalne elementy w tablicy: największy, najmniejszy element listy, lider.

(największy – element o najwyższej wartości, najmniejszy – element o najniższej wartości, lider – element o największej liczbie wystąpień, który występuje częściej niż połowa długości tablicy).

1) Co to jest tablica w Pythonie

W Pythonie używamy list (np. liczby = [5, 7, 9]).
Lista:

  • ma kolejność i indeksy zaczynające się od 0,
  • jest modyfikowalna (można dodawać/usuwać),
  • zwykle trzymamy w niej jednorodne dane (np. same liczby), żeby łatwiej liczyć.

Minimalny start:

liczby = [5, 7, 9]
print(liczby[0])      # 5
print(len(liczby))    # 3
liczby.append(12)     # [5, 7, 9, 12]
liczby.remove(7)      # [5, 9, 12]

2) Iteracja po liście

Gdy chcesz „zajrzeć” do każdego elementu:

for x in liczby:
    print(x)

Gdy chcesz też indeks:

for i, x in enumerate(liczby):
    print(i, x)

3) Największy element — rozumienie od środka

Idea: „trzymam najlepszy dotąd wynik i porównuję z kolejnymi”.

def znajdz_max(L):
    if not L:            # ochrona przed pustą listą
        return None
    maks = L[0]          # 1) start: pierwszy element
    for x in L:          # 2) idź po elementach
        if x > maks:     # 3) lepszy? podmień
            maks = x
    return maks          # 4) gotowe po jednym przejściu

To działa w czasie O(n), czyli jedno pełne przejście listy. (Wbudowane max(L) robi logicznie to samo — też O(n).) bitedu.pl

4) Najmniejszy element — analogicznie

def znajdz_min(L):
    if not L:
        return None
    mini = L[0]
    for x in L:
        if x < mini:
            mini = x
    return mini

Analogicznie, O(n). bitedu.pl

Dodatkowo: indeks(y) maksimum/minimum

Pierwszy indeks maksimum:

def indeks_max(L):
    if not L: return None
    m = L[0]
    idx = 0
    for i, x in enumerate(L):
        if x > m:
            m, idx = x, i
    return idx

Wszystkie indeksy maksimum:

def indeksy_max(L):
    if not L: return []
    m = znajdz_max(L)
    return [i for i, x in enumerate(L) if x == m]

5) „Lider” — o co chodzi

Lider to element, który występuje więcej niż połowę długości listy. Np. w [2, 2, 1, 2, 3, 2, 2] liderem jest 2 (5 na 7 pozycji). Nie każda lista ma lidera.

5a) Proste (edukacyjne) znalezienie lidera

Najpierw wersja „naiwna” — bardzo czytelna dla ucznia:

def znajdz_lidera_naiwny(L):
    n = len(L)
    for kandydat in L:                 # sprawdzamy kolejnych kandydatów
        if L.count(kandydat) > n // 2: # uwaga: // to dzielenie całkowite
            return kandydat
    return None

To jest czytelne, ale wolniejsze: w najgorszym razie O(n²), bo count też chodzi po liście. bitedu.pl

5b) Szybsza wersja (Boyer–Moore + weryfikacja)

Dla rozszerzenia warto pokazać „sprytny” pomysł: parujemy różne elementy i „kasujemy” je, więc kandydatem zostaje to, czego „zostaje najwięcej”. Potem trzeba potwierdzić liczeniem.

def znajdz_lidera_boyer_moore(L):
    # Faza 1: znajdź kandydata
    kandydat, licznik = None, 0
    for x in L:
        if licznik == 0:
            kandydat, licznik = x, 1
        elif x == kandydat:
            licznik += 1
        else:
            licznik -= 1
    # Faza 2: potwierdź kandydata
    if kandydat is None:
        return None
    return kandydat if L.count(kandydat) > len(L)//2 else None

To działa w O(n) i jest świetnym przykładem „myślenia algorytmicznego” (ale nie wymagane dla podstaw).

6) Przydatne na lekcji: testy i skrajne przypadki

  • Pusta lista → zwracamy None / komunikat dla użytkownika.
  • Wiele takich samych wartości → max i min działają normalnie; indeksy mogą być liczne.
  • Brak lidera to też wynik.
  • Zadbaj o konwersję wejścia:
L = [int(x) for x in input("Podaj liczby: ").split()]

Zadania dla ucznia + przykładowe rozwiązania

Zadanie 1

Wczytaj z klawiatury listę liczb (jedna linia, spacje). Wypisz największy i najmniejszy element bez użycia max/min.

Rozwiązanie (przykład):

def znajdz_max(L):
    if not L: return None
    m = L[0]
    for x in L:
        if x > m: m = x
    return m

def znajdz_min(L):
    if not L: return None
    m = L[0]
    for x in L:
        if x < m: m = x
    return m

L = [int(x) for x in input().split()]
print("max =", znajdz_max(L))
print("min =", znajdz_min(L))

Zadanie 2

Podaj indeks pierwszego maksimum i indeks pierwszego minimum (jeśli lista pusta, wypisz „brak danych”).

Rozwiązanie (przykład):

def indeks_pierwszego_maks(L):
    if not L: return None
    m, idx = L[0], 0
    for i, x in enumerate(L):
        if x > m:
            m, idx = x, i
    return idx

def indeks_pierwszego_min(L):
    if not L: return None
    m, idx = L[0], 0
    for i, x in enumerate(L):
        if x < m:
            m, idx = x, i
    return idx

L = [int(x) for x in input().split()]
imx = indeks_pierwszego_maks(L)
imn = indeks_pierwszego_min(L)
print("i(max) =", imx if imx is not None else "brak danych")
print("i(min) =", imn if imn is not None else "brak danych")

Zadanie 3

Wypisz wszystkie indeksy, pod którymi występuje maksimum (np. dla [3, 7, 7, 2, 7] → 1, 2, 4).

Rozwiązanie (przykład):

def indeksy_max(L):
    if not L: return []
    m = L[0]
    for x in L:
        if x > m:
            m = x
    return [i for i, x in enumerate(L) if x == m]

L = [int(x) for x in input().split()]
print(indeksy_max(L))

Zadanie 4

Napisz funkcję znajdz_lidera_naiwny(L) i przetestuj ją na:

  • L1 = [2, 2, 1, 2, 3, 2, 2]
  • L2 = [1, 2, 3, 2, 1]
    Wypisz wynik oraz krótkie uzasadnienie (ile razy wystąpił kandydat).

Rozwiązanie (przykład):

def znajdz_lidera_naiwny(L):
    n = len(L)
    for k in L:
        if L.count(k) > n//2:
            return k
    return None

for L in ([2,2,1,2,3,2,2], [1,2,3,2,1]):
    lid = znajdz_lidera_naiwny(L)
    if lid is None:
        print(L, "-> brak lidera")
    else:
        print(L, "-> lider =", lid, "(wystąpienia:", L.count(lid), ")")

(Definicja i przykład zgodne z Twoim artykułem — tam też pokazujesz proste liczenie i próg > n/2.) bitedu.pl

Zadanie 5 (dla chętnych)

Zaimplementuj Boyer–Moore i potwierdzenie kandydata. Porównaj czas działania z wersją naiwną na dużej liście (np. 100 000 losowych liczb z domieszką lidera).

Rozwiązanie (szkielet):

def lider_boyer_moore(L):
    k, c = None, 0
    for x in L:
        if c == 0:
            k, c = x, 1
        elif x == k:
            c += 1
        else:
            c -= 1
    return k if k is not None and L.count(k) > len(L)//2 else None

Zadanie 6

Napisz program, który:

  1. wczytuje listę,
  2. wypisuje: max, min, indeksy max, indeksy min,
  3. sprawdza lidera (najpierw naiwnie, potem Boyer–Moore) i wyświetla wynik w postaci:
max=..., min=...
i(max)=..., i(min)=...
lider(naiwny)=..., lider(BM)=...

Rozwiązanie (szkic):

def znajdz_max(L): ...
def znajdz_min(L): ...
def indeksy_max(L): ...
def indeksy_min(L):
    m = znajdz_min(L)
    return [i for i, x in enumerate(L) if x == m]
def znajdz_lidera_naiwny(L): ...
def lider_boyer_moore(L): ...

L = [int(x) for x in input().split()]
print("max=", znajdz_max(L), "min=", znajdz_min(L))
print("i(max)=", indeksy_max(L), "i(min)=", indeksy_min(L))
print("lider(naiwny)=", znajdz_lidera_naiwny(L))
print("lider(BM)=", lider_boyer_moore(L))