{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "k00",
   "metadata": {},
   "source": [
    "# Algorytmy: zapis, wyszukiwanie i rekurencja\n",
    "\n",
    "*Wersja notatnika: 2026-10-16 · przygotowanie: dr inż. Szczepan Górtowski*\n",
    "\n",
    "Pierwsze zajęcia modułu **Algorytmy**. Zapiszesz ten sam algorytm na cztery sposoby, porównasz wyszukiwanie liniowe\n",
    "z binarnym, a potem poznasz **rekurencję**: funkcję, która wywołuje samą siebie. Na koniec zobaczysz, jak jedna linijka\n",
    "`@lru_cache` przyspiesza obliczenia setki razy.\n",
    "\n",
    "### Jak korzystać\n",
    "1. Uruchamiaj komórki po kolei: `Ctrl + Enter` albo `Shift + Enter`.\n",
    "2. Przy ramkach **Przewidź, zanim uruchomisz** najpierw zgadnij, potem uruchom, na końcu rozwiń odpowiedź.\n",
    "3. W zadaniach zamień `pass` i `TODO` na swój kod i uruchom komórkę **Sprawdź**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k01",
   "metadata": {},
   "source": [
    "## Spis treści\n",
    "1. Algorytm i cztery sposoby jego zapisu\n",
    "2. Wyszukiwanie liniowe\n",
    "3. Wyszukiwanie binarne — i błąd, który przetrwał dekady\n",
    "4. Rekurencja: przypadek bazowy i krok\n",
    "5. Stos wywołań i limit rekurencji\n",
    "6. Fibonacci: rekurencja, która się powtarza — i `@lru_cache`\n",
    "7. Zadania 8.0–8.3 i zadanie 8.4 dla chętnych (wieże Hanoi)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k02",
   "metadata": {},
   "source": [
    "## 1) Algorytm i cztery sposoby jego zapisu\n",
    "\n",
    "**Algorytm** to skończony ciąg jednoznacznych kroków, który rozwiązuje problem (zajęcia 1). Ten sam algorytm —\n",
    "*znajdź największą liczbę na liście* — można zapisać na cztery sposoby:\n",
    "\n",
    "**Opis słowny:** zapamiętaj pierwszą liczbę jako największą. Przejdź po pozostałych; jeśli któraś jest większa od\n",
    "zapamiętanej, zapamiętaj ją. Na końcu podaj zapamiętaną liczbę.\n",
    "\n",
    "**Pseudokod:**\n",
    "```\n",
    "największa ← pierwszy element listy\n",
    "dla każdego elementu e listy:\n",
    "    jeśli e > największa:\n",
    "        największa ← e\n",
    "zwróć największa\n",
    "```\n",
    "\n",
    "**Schemat blokowy:** romb to decyzja, prostokąt — operacja, strzałki — kolejność (na slajdach).\n",
    "\n",
    "**Program w Pythonie:**"
   ]
  },
  {
   "cell_type": "code",
   "id": "k03",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def najwieksza(lista):\n",
    "    wynik = lista[0]\n",
    "    for e in lista[1:]:\n",
    "        if e > wynik:\n",
    "            wynik = e\n",
    "    return wynik\n",
    "\n",
    "print(najwieksza([4, 8, 1, 9, 3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k04",
   "metadata": {},
   "source": [
    "## 2) Wyszukiwanie liniowe\n",
    "\n",
    "Sprawdzasz elementy po kolei, aż trafisz albo skończy się lista. Działa na **każdej** liście, ale w najgorszym\n",
    "przypadku sprawdza wszystkie `n` elementów: **O(n)**."
   ]
  },
  {
   "cell_type": "code",
   "id": "k05",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def szukaj_liniowo_kroki(lista, x):\n",
    "    for kroki, element in enumerate(lista, start=1):\n",
    "        if element == x:\n",
    "            return kroki\n",
    "    return len(lista)\n",
    "\n",
    "N = 1_000_000\n",
    "posortowana = list(range(0, 2 * N, 2))      # milion liczb parzystych\n",
    "print(\"liniowo, pierwszy:\", szukaj_liniowo_kroki(posortowana, 0))\n",
    "print(\"liniowo, ostatni: \", szukaj_liniowo_kroki(posortowana, 2 * N - 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k06",
   "metadata": {},
   "source": [
    "## 3) Wyszukiwanie binarne — i błąd, który przetrwał dekady\n",
    "\n",
    "W **posortowanej** liście patrzysz na środek. Szukana liczba jest większa — odrzucasz lewą połowę, mniejsza — prawą.\n",
    "Każdy krok zostawia połowę, więc dla miliona elementów wystarczy ok. 20 kroków: **O(log n)**. Tak samo grasz\n",
    "w „zgadnij liczbę od 1 do 100” — wystarczy 7 pytań."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k07",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** ile kroków zrobi wyszukiwanie binarne w milionie liczb dla ostatniego elementu?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> 20 albo mniej: 2²⁰ = 1 048 576, więc po 20 połowieniach zostaje jeden element.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k08",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def szukaj_binarnie_kroki(lista, x):\n",
    "    lo, hi = 0, len(lista) - 1\n",
    "    kroki = 0\n",
    "    while lo <= hi:\n",
    "        kroki += 1\n",
    "        sr = (lo + hi) // 2\n",
    "        if lista[sr] == x:\n",
    "            return kroki\n",
    "        if lista[sr] < x:\n",
    "            lo = sr + 1\n",
    "        else:\n",
    "            hi = sr - 1\n",
    "    return kroki\n",
    "\n",
    "print(\"binarnie, ostatni:\", szukaj_binarnie_kroki(posortowana, 2 * N - 2))\n",
    "print(\"binarnie, brak:   \", szukaj_binarnie_kroki(posortowana, 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k09",
   "metadata": {},
   "source": [
    "### Błąd, który przetrwał dekady\n",
    "\n",
    "W 2006 r. Joshua Bloch opisał na blogu Google Research, że linijka `sr = (lo + hi) // 2` w Javie i C może się\n",
    "**przepełnić**: dla tablic powyżej ok. miliarda elementów suma `lo + hi` przekracza największą liczbę typu `int`\n",
    "i robi się ujemna. Błąd siedział w bibliotece Javy przez lata. Bezpieczny zapis to `lo + (hi - lo) // 2`.\n",
    "\n",
    "**W Pythonie tego problemu nie ma**: liczby całkowite nie mają górnej granicy. Ale gdy przepiszesz algorytm na inny\n",
    "język, pamiętaj o bezpiecznym zapisie."
   ]
  },
  {
   "cell_type": "code",
   "id": "k10",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "duza = 2**31 - 1          # największy 32-bitowy int w Javie i C\n",
    "print(\"lo + hi =\", duza + duza, \"| w Pythonie bez przepełnienia\")\n",
    "print(\"bezpiecznie:\", duza + (duza - duza) // 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k11",
   "metadata": {},
   "source": [
    "## 4) Rekurencja: przypadek bazowy i krok\n",
    "\n",
    "Funkcja **rekurencyjna** wywołuje samą siebie dla mniejszego problemu. Potrzebuje dwóch części:\n",
    "- **przypadek bazowy** — prosty przypadek, który zwraca wynik bez dalszych wywołań (`n <= 1` dla silni),\n",
    "- **krok rekurencyjny** — sprowadza problem do mniejszego (`n! = n · (n − 1)!`).\n",
    "\n",
    "Bez przypadku bazowego funkcja wywoływałaby się w nieskończoność."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k12",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** w jakiej kolejności pojawią się linie `→ …` przy liczeniu `silnia(4)`?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> Od najgłębszego: `→ 1`, `→ 2`, `→ 6`, `→ 24`. Wywołania schodzą w dół do przypadku bazowego, a wyniki wracają w odwrotnej kolejności — jak zdejmowanie ze stosu (zajęcia 4).\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k13",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def silnia(n, glebokosc=0):\n",
    "    wciecie = \"    \" * glebokosc\n",
    "    print(f\"{wciecie}silnia({n})\")\n",
    "    if n <= 1:                         # przypadek bazowy\n",
    "        print(f\"{wciecie}→ 1\")\n",
    "        return 1\n",
    "    wynik = n * silnia(n - 1, glebokosc + 1)   # krok rekurencyjny\n",
    "    print(f\"{wciecie}→ {wynik}\")\n",
    "    return wynik\n",
    "\n",
    "print(\"wynik:\", silnia(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k14",
   "metadata": {},
   "source": [
    "## 5) Stos wywołań i limit rekurencji\n",
    "\n",
    "Każde wywołanie czeka na wynik następnego — Python trzyma je na **stosie wywołań** (LIFO, zajęcia 4). Stos ma limit:\n",
    "domyślnie ok. 1000 poziomów. Głębsza rekurencja kończy się `RecursionError`. Wersja z pętlą nie ma tego problemu."
   ]
  },
  {
   "cell_type": "code",
   "id": "k15",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "def silnia_rek(n):\n",
    "    if n <= 1:\n",
    "        return 1\n",
    "    return n * silnia_rek(n - 1)\n",
    "\n",
    "def silnia_iter(n):\n",
    "    wynik = 1\n",
    "    for k in range(2, n + 1):\n",
    "        wynik *= k\n",
    "    return wynik\n",
    "\n",
    "print(\"limit rekurencji:\", sys.getrecursionlimit())\n",
    "try:\n",
    "    silnia_rek(5000)\n",
    "except RecursionError as e:\n",
    "    print(\"RecursionError:\", e)\n",
    "print(\"1000! ma\", len(str(silnia_iter(1000))), \"cyfr\")\n",
    "print(\"ta sama wartość:\", silnia_rek(500) == silnia_iter(500))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k16",
   "metadata": {},
   "source": [
    "## 6) Fibonacci: rekurencja, która się powtarza — i `@lru_cache`\n",
    "\n",
    "Ciąg Fibonacciego: `F(0) = 0`, `F(1) = 1`, `F(n) = F(n − 1) + F(n − 2)`. Zapis rekurencyjny jest wierny definicji,\n",
    "ale te same wartości liczy wiele razy: `fib(5)` liczy `fib(2)` trzy razy. Liczba wywołań rośnie wykładniczo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k17",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** ile wywołań funkcji potrzebuje naiwne `fib(20)`?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> 21 891. A `fib(30)` — ponad 2,6 miliona. Każdy poziom prawie podwaja liczbę wywołań.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k18",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "licznik = {\"wywołania\": 0}\n",
    "\n",
    "def fib(n):\n",
    "    licznik[\"wywołania\"] += 1\n",
    "    if n < 2:\n",
    "        return n\n",
    "    return fib(n - 1) + fib(n - 2)\n",
    "\n",
    "for n in [5, 10, 20, 25]:\n",
    "    licznik[\"wywołania\"] = 0\n",
    "    wynik = fib(n)\n",
    "    print(f\"fib({n:>2}) = {wynik:>6} | wywołań: {licznik['wywołania']:>7}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k19",
   "metadata": {},
   "source": [
    "**Zapamiętywanie** (*memoization*): zapisz raz policzony wynik i przy kolejnym pytaniu oddaj go od razu. Python ma to\n",
    "gotowe w dekoratorze `functools.lru_cache`. Zadanie 8.3 robi to samo ręcznie, na słowniku (zajęcia 3)."
   ]
  },
  {
   "cell_type": "code",
   "id": "k20",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import time\n",
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache(maxsize=None)\n",
    "def fib_cache(n):\n",
    "    if n < 2:\n",
    "        return n\n",
    "    return fib_cache(n - 1) + fib_cache(n - 2)\n",
    "\n",
    "start = time.perf_counter()\n",
    "fib(27)\n",
    "t_naiwnie = time.perf_counter() - start\n",
    "\n",
    "start = time.perf_counter()\n",
    "fib_cache(27)\n",
    "t_cache = time.perf_counter() - start\n",
    "\n",
    "print(f\"naiwnie:    {t_naiwnie * 1000:9.2f} ms\")\n",
    "print(f\"lru_cache:  {t_cache * 1000:9.3f} ms\")\n",
    "print(f\"fib_cache(90) = {fib_cache(90)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k21",
   "metadata": {},
   "source": [
    "## 7) Zadanie 8.0 — wyszukiwanie liniowe\n",
    "\n",
    "Napisz `szukaj_liniowo(lista, x)`: zwraca **indeks pierwszego** wystąpienia `x` albo `-1`, gdy go nie ma."
   ]
  },
  {
   "cell_type": "code",
   "id": "k22",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def szukaj_liniowo(lista: list, x) -> int:\n",
    "    \"\"\"Indeks pierwszego wystąpienia x albo -1.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k23",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert szukaj_liniowo([4, 8, 1, 8], 8) == 1\n",
    "    assert szukaj_liniowo([4, 8, 1], 7) == -1\n",
    "    assert szukaj_liniowo([], 1) == -1\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 8.0 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k24",
   "metadata": {},
   "source": [
    "## Zadanie 8.1 — wyszukiwanie binarne\n",
    "\n",
    "Napisz `szukaj_binarnie(lista, x)` dla **posortowanej** listy: indeks `x` albo `-1`. Użyj pętli `while lo <= hi`\n",
    "i środka `sr = (lo + hi) // 2`, jak w sekcji 3."
   ]
  },
  {
   "cell_type": "code",
   "id": "k25",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def szukaj_binarnie(lista: list, x) -> int:\n",
    "    \"\"\"Indeks x w posortowanej liście albo -1.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k26",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    dane = [1, 3, 5, 7, 9, 11, 13]\n",
    "    assert all(szukaj_binarnie(dane, v) == i for i, v in enumerate(dane))\n",
    "    assert szukaj_binarnie(dane, 4) == -1\n",
    "    assert szukaj_binarnie([], 4) == -1\n",
    "    duza = list(range(0, 2_000_000, 2))\n",
    "    assert szukaj_binarnie(duza, 1_999_998) == 999_999\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 8.1 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k27",
   "metadata": {},
   "source": [
    "## Zadanie 8.2 — suma cyfr rekurencyjnie\n",
    "\n",
    "Napisz rekurencyjną `suma_cyfr(n)`: `suma_cyfr(1234) == 10`. Przypadek bazowy: liczba jednocyfrowa. Krok: ostatnia\n",
    "cyfra `n % 10` plus suma cyfr liczby `n // 10`. Bez pętli i bez `str`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k28",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def suma_cyfr(n: int) -> int:\n",
    "    \"\"\"Suma cyfr liczby naturalnej, rekurencyjnie.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k29",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert suma_cyfr(1234) == 10\n",
    "    assert suma_cyfr(7) == 7\n",
    "    assert suma_cyfr(1000000) == 1\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 8.2 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k30",
   "metadata": {},
   "source": [
    "## Zadanie 8.3 — Fibonacci z pamięcią (słownik)\n",
    "\n",
    "Napisz `fib_memo(n)` bez `lru_cache`: wyniki zapisuj w słowniku `pamiec` przekazywanym w kolejnych wywołaniach.\n",
    "Pamiętaj o pułapce z zajęć 7 — **nie** pisz `pamiec={}` w nagłówku. `fib_memo(80)` ma się policzyć od razu."
   ]
  },
  {
   "cell_type": "code",
   "id": "k31",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def fib_memo(n: int, pamiec: dict | None = None) -> int:\n",
    "    \"\"\"n-ta liczba Fibonacciego z zapamiętywaniem wyników.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k32",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    assert [fib_memo(n) for n in range(8)] == [0, 1, 1, 2, 3, 5, 8, 13]\n",
    "    assert fib_memo(80) == 23416728348467685\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 8.3 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k33",
   "metadata": {},
   "source": [
    "## Zadanie 8.4 dla chętnych — wieże Hanoi\n",
    "\n",
    "Przenieś `n` krążków z pręta `A` na `C`, używając `B`. Wolno ruszać jednym krążkiem i nigdy nie kłaść większego na\n",
    "mniejszy. Rekurencja: przenieś `n − 1` krążków na pręt pomocniczy, największy na cel, potem `n − 1` na cel.\n",
    "Funkcja `hanoi(n)` zwraca listę ruchów `(skąd, dokąd)`. Ile ruchów potrzeba dla 10 krążków?"
   ]
  },
  {
   "cell_type": "code",
   "id": "k34",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "def hanoi(n: int, z=\"A\", na=\"C\", przez=\"B\") -> list:\n",
    "    \"\"\"Lista ruchów (skąd, dokąd) przenoszących n krążków z z na na.\"\"\"\n",
    "    pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k35",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    wieze = {'A': [3, 2, 1], 'B': [], 'C': []}\n",
    "    for skad, dokad in hanoi(3):\n",
    "        krazek = wieze[skad].pop()\n",
    "        assert not wieze[dokad] or wieze[dokad][-1] > krazek\n",
    "        wieze[dokad].append(krazek)\n",
    "    assert wieze['C'] == [3, 2, 1]\n",
    "    assert len(hanoi(10)) == 2**10 - 1\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 8.4 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k36",
   "metadata": {},
   "source": [
    "## Zapamiętaj\n",
    "\n",
    "- Algorytm zapiszesz słowami, pseudokodem, schematem blokowym albo programem — to ten sam ciąg kroków.\n",
    "- Wyszukiwanie liniowe: każda lista, O(n). Binarne: tylko posortowana, O(log n) — milion elementów w 20 krokach.\n",
    "- Rekurencja = przypadek bazowy + krok do mniejszego problemu. Głębokość ogranicza stos wywołań (ok. 1000).\n",
    "- Gdy rekurencja liczy to samo wiele razy, zapamiętuj wyniki: słownik albo `@lru_cache`.\n",
    "\n",
    "## Zadania dodatkowe\n",
    "\n",
    "1. Narysuj schemat blokowy wyszukiwania binarnego.\n",
    "2. Ile pytań „większa czy mniejsza?” wystarczy, by zgadnąć liczbę od 1 do 1 000 000?\n",
    "3. Przepisz `suma_cyfr` z pętlą `while`. Która wersja jest czytelniejsza?"
   ]
  }
 ],
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  }
 }
}