Algorytmy na maturę z informatyki - NWD, liczby pierwsze, Fibonacci, Cezar

1.Specyfikacja problemu

Dokładny opis zadania przed napisaniem algorytmu. Składa się z dwóch części: dane (co algorytm dostaje i jakie warunki spełniają, np. n - liczba naturalna, n > 1) oraz wynik (co algorytm zwraca i jak wynik zależy od danych).

2.Sprawdzanie poprawności algorytmu dla przykładowych danych

Wykonujemy algorytm krok po kroku na kilku danych i zapisujemy w tabeli wartości zmiennych po każdym obiegu pętli. Oprócz typowych danych sprawdzamy przypadki brzegowe, np. 0, 1, liczbę jednocyfrową, pusty napis albo dwie równe liczby.

3.Ostatnia cyfra liczby i jej usunięcie

Ostatnią cyfrę liczby naturalnej n daje reszta z dzielenia przez 10: n % 10. Część całkowita z dzielenia przez 10, czyli n // 10, usuwa ostatnią cyfrę. Dla n = 4071: n % 10 = 1, a n // 10 = 407.

4.Wyodrębnianie wszystkich cyfr liczby (np. suma cyfr)

Pętla działa, dopóki n > 0: bierze ostatnią cyfrę n % 10, a potem skraca liczbę przez n = n // 10. Cyfry pojawiają się od końca. Suma cyfr w Pythonie: s = 0, potem while n > 0: s += n % 10; n //= 10.

5.Odwracanie liczby (zapis cyfr w odwrotnej kolejności)

Zaczynamy od w = 0 i dopóki n > 0, dopisujemy ostatnią cyfrę n na koniec w: w = w * 10 + n % 10, a potem n = n // 10. Zera z końca liczby znikają, np. 1230 daje 321. Liczba jest palindromem, gdy jej odwrócenie jest jej równe.

6.NWD dwóch liczb

Największy wspólny dzielnik liczb naturalnych a i b, czyli największa liczba, przez którą dzielą się bez reszty obie liczby. Gdy NWD(a, b) = 1, liczby są względnie pierwsze.

7.Algorytm Euklidesa w wersji z odejmowaniem

Dla a, b > 0: dopóki liczby są różne, od większej odejmujemy mniejszą. Gdy się zrównają, każda z nich jest równa NWD. W Pythonie: pętla while a != b, a w niej: jeśli a > b, to a -= b, w przeciwnym razie b -= a. Np. (48, 18) → (30, 18) → (12, 18) → (12, 6) → (6, 6), więc NWD = 6.

8.Algorytm Euklidesa w wersji z resztą z dzielenia

Dopóki b jest różne od 0, zastępujemy parę (a, b) parą (b, a % b). Gdy b = 0, wynikiem jest a. W Pythonie: while b != 0: a, b = b, a % b.

9.Która wersja algorytmu Euklidesa jest szybsza i dlaczego?

Wersja z resztą. Jedno dzielenie z resztą zastępuje wiele odejmowań tej samej liczby. Dla pary (1000, 1) wersja z odejmowaniem wykona 999 odejmowań, a wersja z resztą tylko jeden obieg pętli.

10.NWW(a, b)

Najmniejsza wspólna wielokrotność, czyli najmniejsza dodatnia liczba podzielna przez a i przez b. Liczymy ją przez NWD: NWW(a, b) = a * b // NWD(a, b), np. NWW(12, 18) = 216 // 6 = 36.

11.Skracanie ułamka do postaci nieskracalnej

Licznik i mianownik dzielimy przez ich NWD. Np. dla 84/126: NWD(84, 126) = 42, więc ułamek to 2/3. Ułamek jest nieskracalny, gdy NWD licznika i mianownika wynosi 1.

12.Dodawanie ułamków z użyciem NWW

Wspólny mianownik to NWW mianowników. Każdy licznik mnożymy przez to, ile razy NWW jest większa od jego mianownika, dodajemy liczniki i skracamy wynik przez NWD. Np. 1/6 + 3/8: NWW(6, 8) = 24, więc 4/24 + 9/24 = 13/24.

13.Liczba pierwsza

Liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 i samą siebie. Liczba 1 nie jest ani pierwsza, ani złożona, a 2 to jedyna parzysta liczba pierwsza.

14.Badanie pierwszości liczby n (dzielniki do pierwiastka z n)

Gdy n < 2, liczba nie jest pierwsza. W przeciwnym razie sprawdzamy dzielniki d = 2, 3, 4, …, dopóki d * d <= n. Jeśli dla któregoś d zachodzi n % d == 0, to n jest złożona. Jeśli żadne d nie dzieli n, to n jest pierwsza.

15.Dlaczego przy badaniu pierwszości wystarczy sprawdzić dzielniki do pierwiastka z n?

Jeśli $n = a \cdot b$ i $a \le b$, to $a \cdot a \le n$, czyli mniejszy dzielnik nie przekracza pierwiastka z n. Gdy więc żadna liczba z przedziału od 2 do pierwiastka z n nie dzieli n, nie ma też większych dzielników (poza samym n).

16.Sito Eratostenesa

Algorytm wyznaczania WSZYSTKICH liczb pierwszych nie większych od n. Wypisujemy liczby od 2 do n, bierzemy najmniejszą niewykreśloną liczbę p (jest pierwsza) i wykreślamy jej wielokrotności. Powtarzamy, dopóki p * p <= n. Liczby niewykreślone są pierwsze.

17.Rozkład liczby na czynniki pierwsze

Zaczynamy od d = 2. Dopóki n > 1: jeśli n % d == 0, zapisujemy czynnik d i dzielimy n = n // d, w przeciwnym razie zwiększamy d o 1. Np. 360 = 2 * 2 * 2 * 3 * 3 * 5. Każdy znaleziony dzielnik jest pierwszy, bo mniejsze czynniki zostały już wydzielone.

18.Zamiana liczby dziesiętnej na system o podstawie p

Dzielimy liczbę z resztą przez p, potem iloraz znów przez p, aż iloraz wyniesie 0. Reszty czytamy od ostatniej do pierwszej. W Pythonie: w = '', potem while n > 0: w = str(n % p) + w; n //= p. Np. 13 = 1101 w systemie dwójkowym.

19.Zamiana liczby z systemu o podstawie p na dziesiętny

Każdą cyfrę mnożymy przez wagę jej pozycji (p do potęgi numeru pozycji, licząc od 0 od prawej) i dodajemy wyniki. W pętli od lewej: w = w * p + cyfra. Np. 10111 w systemie dwójkowym to 16 + 4 + 2 + 1 = 23. W Pythonie: int('10111', 2).

20.Ciąg Fibonacciego

Ciąg, w którym dwa pierwsze wyrazy są równe 1, a każdy następny jest sumą dwóch poprzednich: F(n) = F(n - 1) + F(n - 2). Początek: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

21.Ciąg Fibonacciego obliczany iteracyjnie

Pamiętamy tylko dwa ostatnie wyrazy i w pętli przesuwamy je o jeden: a, b = 1, 1, potem for i in range(n - 2): a, b = b, a + b. Wynikiem jest b. Pętla wykonuje około n obiegów, więc metoda jest szybka nawet dla dużych n.

22.Wada rekurencyjnego obliczania ciągu Fibonacciego

Funkcja fib(n) = fib(n - 1) + fib(n - 2) wiele razy oblicza od nowa te same wyrazy, np. fib(5) wywołuje fib(3) dwa razy. Liczba wywołań rośnie wykładniczo: przy warunku fib(1) = fib(2) = 1 dla n = 5 jest ich 9, a dla n = 10 już 109, więc dla dużych n program działa bardzo wolno.

23.Szybkie potęgowanie

Metoda obliczania $a^n$ przez połowienie wykładnika: dla parzystego $n$ korzystamy z $a^n = (a^{n/2})^2$, a dla nieparzystego z $a^n = a \cdot a^{n-1}$. Liczba mnożeń rośnie jak $\log_2 n$, a nie jak $n - 1$ mnożeń w zwykłym sposobie.

24.Szyfr Cezara

Szyfr podstawieniowy: każdą literę zastępujemy literą przesuniętą o k pozycji w alfabecie (klasycznie k = 3), a po Z wracamy do A. Dla wielkich liter alfabetu łacińskiego (26 liter): chr((ord(c) - ord('A') + k) % 26 + ord('A')).

25.Odszyfrowanie szyfru Cezara i jego słabość

Odszyfrowujemy przesunięciem o -k, czyli o 26 - k pozycji. Szyfr jest słaby, bo ma tylko 25 sensownych kluczy: wystarczy sprawdzić wszystkie przesunięcia albo porównać częstość liter w szyfrogramie z częstością liter w języku.

26.Palindrom

Napis, który czytany od początku i od końca jest taki sam, np. kajak, potop. Sprawdzamy, czy s[i] == s[len(s) - 1 - i] dla i od 0 do połowy długości napisu. W Pythonie wystarczy warunek s == s[::-1].

27.Porównywanie tekstów (porządek leksykograficzny)

Napisy porównujemy znak po znaku od lewej według kodów znaków; pierwsza różnica rozstrzyga. Gdy jeden napis jest początkiem drugiego, krótszy jest mniejszy, np. ala < alan. W kodzie ASCII wielkie litery (A = 65) są przed małymi (a = 97), więc Zebra < ala.

28.Wyszukiwanie wzorca w tekście metodą naiwną

Wzorzec w o długości m przykładamy kolejno do każdej pozycji i tekstu t o długości n, od 0 do n - m, i porównujemy znak po znaku. W Pythonie pętla for i in range(len(t) - len(w) + 1) sprawdza warunek t[i:i + len(w)] == w. Wystąpienia mogą na siebie zachodzić.

29.Złożoność obliczeniowa algorytmu

Liczba operacji, jaką algorytm wykonuje, w zależności od rozmiaru danych n. Mówi, jak szybko rośnie czas działania, gdy dane rosną, a nie ile sekund trwa program na konkretnym komputerze.

30.Złożoność logarytmiczna, liniowa i kwadratowa

Logarytmiczna: w każdym kroku problem maleje o połowę (szybkie potęgowanie, wyszukiwanie binarne). Liniowa: jedna pętla przez wszystkie dane (suma, szyfr Cezara, Fibonacci iteracyjnie). Kwadratowa: pętla w pętli przez dane (sortowanie bąbelkowe i przez wstawianie).