Algorytmy i złożoność
Specyfikacja i pseudokod, algorytmy na liczbach (NWD, sito, Horner), złożoność obliczeniowa.
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 , . Wynik: .
Algorytmy na liczbach
Algorytm Euklidesa (NWD)
dopóki b ≠ 0:
(a, b) ← (b, a mod b)
wynik: a
Złożoność logarytmiczna: .
Sito Eratostenesa
Wypisz liczby ; dla kolejnej niewykreślonej wykreśl jej wielokrotności . Złożoność .
Schemat Hornera
Wartość liczymy jako — mnożeń zamiast . Tak samo zamieniamy zapis w systemie o podstawie na liczbę.
Szybkie potęgowanie
dla parzystego , dla nieparzystego — mnożeń.
Cyfry liczby bez tablic i napisów
Cyfra jedności: ; usunięcie ostatniej cyfry: (dzielenie całkowite). Przykład — liczba przeniesień przy dodawaniu pisemnym (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 : < < < < < . Zagnieżdżone pętle po elementach ⇒ ; jedna pętla ⇒ ; dzielenie problemu na pół ⇒ .
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, ).
Średnie zadania
Dron. Tor lotu drona składa się z prostych odcinków; lot zaczyna się w , a kończy w . Plik dron.txt zawiera 100 wierszy: para liczb całkowitych — 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 oblicz (przyjmujemy ). Podaj liczbę par, dla których NWD jest większy od 1. Dla dron_przyklad.txt wynik to 6.
Plansza. Dana jest plansza złożona z wierszy i kolumn; pole jest białe () albo czarne (). Lewe górne i prawe dolne pole są zawsze białe. Rozważmy algorytm z tablicą pomocniczą (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) : 111 / 010 / 111
b) : 111 / 001 / 111 / 100 / 111
c) : 10000 / 11001 / 01001 / 01110 / 01011
Dla którego podpunktu wynikiem działania algorytmu jest PRAWDA? Oceń prawdziwość zdań.
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.
Dana jest kwadratowa plansza o wierszach i 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.
Nieparzysty skrót. Nieparzystym skrótem dodatniej liczby całkowitej nazwiemy liczbę powstałą przez usunięcie cyfr parzystych z zapisu dziesiętnego (skrót nie istnieje, gdy 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 , dla której istnieje nieparzysty skrót, wyznaczy .
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.
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ą.
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.
Liczby. Plik liczby.txt składa się z dwóch wierszy: w pierwszym jest 3000 liczb pierwszych z przedziału , w drugim 20 liczb całkowitych z przedziału (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.
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
Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danych dwóch liczb całkowitych dodatnich i , o tej samej liczbie cyfr w zapisie dziesiętnym, obliczy liczbę przeniesień otrzymanych w trakcie ich dodawania pisemnego. Przykład: dla i wynik to .
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: , — dodatnie liczby całkowite o tej samej liczbie cyfr. Wynik: — liczba przeniesień.
Rozważmy wszystkie punkty, w których dron znajdował się po wykonaniu kolejnych ruchów (dla przykładu z arkusza: , , , , , ).
a) Podaj, ile z tych punktów leży wewnątrz kwadratu o wierzchołkach , , , (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) , , .
Wpisz: liczba x1 y1 x2 y2 x3 y3 (trójka od lewej do prawej).
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.