Nauka / Algorytmy i złożoność

Algorytmy i złożoność

Specyfikacja i pseudokod, algorytmy na liczbach (NWD, sito, Horner), złożoność obliczeniowa.

Rozszerzony

Teoria, wzory i przykłady

Co to jest algorytm

Algorytm to skończony ciąg jednoznacznych kroków prowadzący od danych do wyniku. Na maturze opisujesz go w specyfikacji (dane, wynik), a rozwiązanie zapisujesz w pseudokodzie lub w wybranym języku (Python, C++, Java).

Specyfikacja przykładowa: Dane: liczby całkowite dodatnie aa, bb. Wynik: NWD(a,b)\text{NWD}(a,b).

Algorytmy na liczbach

Algorytm Euklidesa (NWD)

dopóki b ≠ 0:
    (a, b) ← (b, a mod b)
wynik: a

Złożoność logarytmiczna: O(log⁡min⁡(a,b))O(\log \min(a,b)).

Sito Eratostenesa

Wypisz liczby 2..n2..n; dla kolejnej niewykreślonej pp wykreśl jej wielokrotności p2,p2+p,…p^2, p^2+p,\dots. Złożoność O(nlog⁡log⁡n)O(n\log\log n).

Schemat Hornera

Wartość w(x)=anxn+⋯+a1x+a0w(x)=a_nx^n+\dots+a_1x+a_0 liczymy jako (…(anx+an−1)x+… )x+a0(\dots(a_nx+a_{n-1})x+\dots)x+a_0 — nn mnożeń zamiast O(n2)O(n^2). Tak samo zamieniamy zapis w systemie o podstawie pp na liczbę.

Szybkie potęgowanie

an=(an/2)2a^n=(a^{n/2})^2 dla parzystego nn, an=a⋅an−1a^n=a\cdot a^{n-1} dla nieparzystego — O(log⁡n)O(\log n) mnożeń.

Cyfry liczby bez tablic i napisów

Cyfra jedności: n mod 10n \bmod 10; usunięcie ostatniej cyfry: n÷10n \div 10 (dzielenie całkowite). Przykład — liczba przeniesień przy dodawaniu pisemnym a+ba+b (liczby o tej samej liczbie cyfr):

p ← 0; c ← 0            # c = bieżące przeniesienie
dopóki a > 0 lub b > 0:
    s ← (a mod 10) + (b mod 10) + c
    jeśli s ≥ 10: c ← 1; p ← p + 1
    w przeciwnym razie: c ← 0
    a ← a div 10; b ← b div 10
wynik: p

Dla 27732 + 72619 wynik to 4.

Złożoność obliczeniowa

Zliczamy operacje w zależności od rozmiaru danych nn: O(1)O(1) < O(log⁡n)O(\log n) < O(n)O(n) < O(nlog⁡n)O(n\log n) < O(n2)O(n^2) < O(2n)O(2^n). Zagnieżdżone pętle po nn elementach ⇒ O(n2)O(n^2); jedna pętla ⇒ O(n)O(n); dzielenie problemu na pół ⇒ O(log⁡n)O(\log n).

Typowe błędy

  • Naruszanie ograniczeń zadania (np. użycie tablic, gdy zabroniono).
  • Zła inicjalizacja zmiennych (przeniesienie, licznik).
  • Brak obsługi przypadków brzegowych (jedna cyfra, n=0n=0).

Łatwe zadania

Średnie zadania

Średnie2 pkt

Dron. Tor lotu drona składa się z prostych odcinków; lot zaczyna się w (0,0)(0,0), a kończy w (20000,0)(20000,0). Plik dron.txt zawiera 100 wierszy: para liczb całkowitych A BA\ B — przemieszczenie w poziomie (zawsze dodatnie) i w pionie (dodatnie: w górę, ujemne: w dół, 0: bez zmiany) od ostatniej pozycji. Pliki z danymi (Dane-NF-2505.zip) pobierzesz na stronie arkusza.

Dla każdego przesunięcia [A,B][A,B] oblicz NWD(∣A∣,∣B∣)\text{NWD}(|A|,|B|) (przyjmujemy NWD(A,0)=A\text{NWD}(A,0)=A). Podaj liczbę par, dla których NWD jest większy od 1. Dla dron_przyklad.txt wynik to 6.

Średnie2 pkt

Plansza. Dana jest plansza złożona z nn wierszy i mm kolumn; pole jest białe (A[i][j]=1A[i][j]=1) albo czarne (A[i][j]=0A[i][j]=0). Lewe górne i prawe dolne pole są zawsze białe. Rozważmy algorytm z tablicą pomocniczą PP (wartości logiczne):

P[1][1] ← PRAWDA
dla i = 1, 2, ..., n wykonuj
    dla j = 1, 2, ..., m wykonuj
        jeżeli A[i][j] = 0
            P[i][j] ← FAŁSZ
        w przeciwnym przypadku
            jeżeli i = 1 oraz j ≠ 1
                P[i][j] ← P[i][j-1]
            jeżeli i ≠ 1 oraz j = 1
                P[i][j] ← P[i-1][j]
            jeżeli i ≠ 1 oraz j ≠ 1
                P[i][j] ← P[i][j-1] lub P[i-1][j]
podaj wynik P[n][m]

Plansze do podpunktów (wiersz po wierszu, 1 = białe, 0 = czarne):

a) n=3, m=3n=3,\ m=3: 111 / 010 / 111

b) n=5, m=3n=5,\ m=3: 111 / 001 / 111 / 100 / 111

c) n=5, m=5n=5,\ m=5: 10000 / 11001 / 01001 / 01110 / 01011

Dla którego podpunktu wynikiem działania algorytmu jest PRAWDA? Oceń prawdziwość zdań.

Średnie2 pkt

Przy założeniu, że lewy górny i prawy dolny róg planszy są białe, podaj przykład planszy (wiersz po wierszu; 1 — pole białe, 0 — pole czarne):

a) o 5 wierszach i 5 kolumnach, na której co najwyżej 2 pola są czarne, a wynikiem algorytmu z zadania 1.1 jest FAŁSZ;

b) o 4 wierszach i 4 kolumnach, na której co najmniej 9 pól jest czarnych, a wynikiem algorytmu jest PRAWDA.

Średnie1 pkt

Dana jest kwadratowa plansza o nn wierszach i nn kolumnach (lewy górny i prawy dolny róg są białe). Podaj, jaka jest największa możliwa liczba czarnych pól na tej planszy, dla której wynikiem algorytmu z zadania 1.1 jest PRAWDA.

Średnie3 pkt

Nieparzysty skrót. Nieparzystym skrótem dodatniej liczby całkowitej nn nazwiemy liczbę mm powstałą przez usunięcie cyfr parzystych z zapisu dziesiętnego nn (skrót nie istnieje, gdy nn składa się wyłącznie z cyfr parzystych). Przykłady: skrótem 294762 jest 97; skrótem 39101 jest 3911; dla 224 skrót nie istnieje.

W pseudokodzie lub w wybranym języku programowania napisz funkcję, która dla dodatniej liczby całkowitej nn, dla której istnieje nieparzysty skrót, wyznaczy mm.

Uwaga: algorytm może używać wyłącznie zmiennych całkowitych i operacji: dodawanie, odejmowanie, mnożenie, dzielenie całkowite, reszta z dzielenia, porównania, instrukcje sterujące i własne funkcje; zabronione są funkcje wbudowane.

Średnie3 pkt

Plik skrot.txt zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000 (każda w osobnym wierszu); dla co najmniej jednej nie istnieje nieparzysty skrót. Pliki z danymi (Dane-NF-2405.zip) pobierzesz na stronie arkusza.

Podaj, ile liczb z pliku skrot.txt nie ma nieparzystego skrótu, oraz największą z nich. Dla skrot_przyklad.txt odpowiedź to 2 i 2428 (liczby 266 i 2428).

Wpisz dwie liczby oddzielone spacją.

Średnie4 pkt

Plik skrot2.txt zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000, z których każda ma nieparzysty skrót. Wypisz te liczby z pliku skrot2.txt, dla których największy wspólny dzielnik liczby i jej nieparzystego skrótu jest równy 7. Dla skrot2_przyklad.txt odpowiedź to 4872 i 23527.

Wpisz liczby w kolejności z pliku, oddzielone spacjami.

Średnie2 pkt

Liczby. Plik liczby.txt składa się z dwóch wierszy: w pierwszym jest 3000 liczb pierwszych z przedziału [2,2000][2, 2000], w drugim 20 liczb całkowitych z przedziału [2,109][2, 10^9] (liczby rozdzielone spacjami). Pliki z danymi (Dane-NF-2405.zip) pobierzesz na stronie arkusza. Do dyspozycji jest też liczby_przyklad.txt (200 liczb w 1. wierszu).

Podaj, ile liczb z pierwszego wiersza jest dzielnikiem jakiejkolwiek liczby z drugiego wiersza. Dla pliku przykładowego odpowiedź to 199.

Średnie3 pkt

Znajdź w ciągu liczb z pierwszego wiersza liczby.txt spójny fragment zawierający co najmniej 50 elementów, którego średnia arytmetyczna jest największa (przy remisie — pierwszy w pliku). Podaj: najwyższą średnią, liczbę elementów tego fragmentu oraz liczbę będącą jego pierwszym elementem. Dla pliku przykładowego: 5,52 50 5.

Trudne zadania

Trudne4 pkt

Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danych dwóch liczb całkowitych dodatnich aa i bb, o tej samej liczbie cyfr w zapisie dziesiętnym, obliczy liczbę przeniesień otrzymanych w trakcie ich dodawania pisemnego. Przykład: dla 2773227732 i 7261972619 wynik to 44.

Uwaga: algorytm może operować wyłącznie na liczbach całkowitych i używać tylko zmiennych przechowujących pojedyncze liczby całkowite. Możesz korzystać tylko z operatorów arytmetycznych (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), logicznych, porównań, instrukcji sterujących i przypisania oraz własnych funkcji z tych operacji. Zabronione są funkcje wbudowane, tablice/listy i konwersje napis↔liczba.

Specyfikacja. Dane: aa, bb — dodatnie liczby całkowite o tej samej liczbie cyfr. Wynik: pp — liczba przeniesień.

Trudne4 pkt

Rozważmy wszystkie punkty, w których dron znajdował się po wykonaniu kolejnych ruchów (dla przykładu z arkusza: (3000,2000)(3000,2000), (5000,11000)(5000,11000), (10000,4000)(10000,4000), (15000,8000)(15000,8000), (18000,14000)(18000,14000), (20000,0)(20000,0)).

a) Podaj, ile z tych punktów leży wewnątrz kwadratu o wierzchołkach (0,0)(0,0), (0,5000)(0,5000), (5000,5000)(5000,5000), (5000,0)(5000,0) (bez punktów na krawędziach).

b) Znajdź trzy różne punkty takie, że jeden z nich jest środkiem odcinka o końcach w pozostałych dwóch (jest tylko jedna taka trójka; nie muszą to być kolejne punkty).

Dla dron_przyklad.txt: a) 2, b) (14000,3014)(14000,3014), (16000,2010)(16000,2010), (18000,1006)(18000,1006).

Wpisz: liczba x1 y1 x2 y2 x3 y3 (trójka od lewej do prawej).

Trudne3 pkt

Dla każdej liczby z drugiego wiersza liczby.txt rozstrzygnij, czy da się ją przedstawić jako iloczyn jedynie liczb z pierwszego wiersza, przy czym liczba wystąpień danego czynnika w iloczynie nie może być większa niż liczba jego wystąpień w pierwszym wierszu. Wypisz wszystkie takie liczby. Dla pliku przykładowego: 10 12 14 15 18 20 21 25 27 28 (np. 16 = 2·2·2·2 odpada, bo liczba 2 występuje w pierwszym wierszu tylko dwa razy).

Wpisz liczby w kolejności z pliku, oddzielone spacjami.

Gotowy na sprawdzian z działu?
Wygeneruj krótki test z tego działu w generatorze.
Test działowy