Zadanie 3
Matura z informatyki, maj 2023, poziom rozszerzony
Wymaganie: I.2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. II.3) sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów. P.I.2) stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy poznane w szkole podstawowej oraz algorytmy: a) na liczbach […]. P.II.1) projektuje i programuje rozwiązania problemów z różnych dziedzin […]. I+II.2) wykorzystuje znane sobie algorytmy przy rozwiązywaniu i programowaniu rozwiązań następujących problemów: c) znajdowania w ciągu podciągów o różnorodnych własnościach […].
Treść zadania
Zadanie 3. Liczba Pi
Pewien matematyk jest zafascynowany liczbą π ≈ 3,14159265... do tego stopnia, że zapisał jej rozwinięcie dziesiętne z dokładnością do 10 000 cyfr po przecinku. Wszystkie cyfry po przecinku zapisał w pliku tekstowym pi.txt.
Plik pi.txt zawiera 10 000 wierszy, każdy wiersz zawiera jedną cyfrę. W pierwszych 10 wierszach pliku zapisano zatem cyfry: 1, 4, 1, 5, 9, 2, 6, 5, 3, 5.
Matematyk zastanawia się, jakiego rodzaju regularności można zaobserwować w zebranych danych. Napisz program(y), który(-e) da(-dzą) odpowiedzi do poniższych zadań. Odpowiedzi do zadań zapisz w pliku wyniki3.txt, a każdą z nich poprzedź numerem odpowiedniego zadania. Plik pi_przyklad.txt zawiera 100 pierwszych wierszy pliku pi.txt. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań.
Zadanie 3.1. (0–2) Fragmentem 2-cyfrowym nazywamy dwie następujące po sobie cyfry w pliku pi.txt. Wszystkich fragmentów 2-cyfrowych zapisanych w tym pliku jest 9999. Ostatni rozpoczyna się w wierszu nr 9999. Przykładowe fragmenty: od pozycji 1 – 14, od 2 – 41, od 3 – 15, od 9 – 35.
Znajdź liczbę wszystkich fragmentów 2-cyfrowych, które są zapisami dziesiętnymi liczb o wartościach większych od 90. Dla danych zapisanych w pliku pi_przyklad.txt poprawna odpowiedź to 13.
Zadanie 3.2. (0–3) Wszystkich możliwych różnych fragmentów 2-cyfrowych jest dokładnie 100. Są nimi fragmenty 00, 01, 02, …, 99. Można sprawdzić, że np. 2-cyfrowy fragment równy 27 występuje w pliku pi.txt dokładnie 101 razy.
Znajdź fragmenty 2-cyfrowe, których liczba wystąpień w pliku pi.txt jest najmniejsza, oraz fragmenty 2-cyfrowe, których liczba wystąpień w pliku pi.txt jest największa. W wyniku podaj znalezione fragmenty 2-cyfrowe oraz liczby ich wystąpień. W przypadku, gdy więcej niż jeden fragment występuje tyle samo razy, wypisz ten o mniejszej wartości liczbowej.
Dla danych z pliku pi_przyklad.txt poprawna odpowiedź to: 00 0 / 62 4 (minimalna liczba wystąpień: fragment 00, liczba wystąpień 0; maksymalna liczba wystąpień: fragment 62, liczba wystąpień 4).
Informacja do zadań 3.3. i 3.4. Skończony co najmniej 4-elementowy ciąg liczb (a₁, a₂, …, aₙ) jest rosnąco-malejący, jeśli można podzielić go na dwa ciągi, z których pierwszy jest rosnący, a drugi – malejący, tzn. jeśli istnieje takie k ∈ {2, 3, …, n – 2}, że a₁ < a₂ < … < aₖ oraz aₖ₊₁ > aₖ₊₂ > … > aₙ.
Przykład: Ciąg (2, 5, 7, 9, 8, 3, 1) jest rosnąco-malejący, bo można go podzielić na dwa ciągi: rosnący (2, 5, 7) i malejący (9, 8, 3, 1) lub – odpowiednio – (2, 5, 7, 9) i (8, 3, 1). Ciąg (5, 9, 9, 4, 1) także jest rosnąco-malejący. Przykłady ciągów, które nie są rosnąco-malejące, to: (2, 5, 8, 4, 3, 4, 5), (1, 2, 3, 4), (5, 5, 3, 2, 1).
Zadanie 3.3. (0–3) Podaj, ile jest wszystkich rosnąco-malejących ciągów złożonych z dokładnie sześciu kolejnych cyfr zapisanych w pliku pi.txt. Dla pliku pi_przyklad.txt poprawna odpowiedź to 3 (są to ciągi 028841, 089986, 899862).
Zadanie 3.4. (0–2) Znajdź najdłuższy ciąg kolejnych cyfr z pliku pi.txt, który jest rosnąco-malejący, oraz pozycję, na której on się rozpoczyna. W pliku pi.txt jest tylko jeden taki ciąg o największej długości.
Wynik zapisz w dwóch wierszach: w pierwszym wierszu zapisz pozycję, od której zaczyna się znaleziony ciąg, a w drugim wypisz znaleziony ciąg. Cyfry ciągu zapisz jedną po drugiej, bez znaku odstępu.
Dla danych zapisanych w pliku pi_przyklad.txt poprawna odpowiedź to: 77 / 0899862 (najdłuższy ciąg rosnąco-malejący w pliku pi_przyklad.txt to ciąg 0899862 o długości 7 rozpoczynający się w 77 wierszu pliku).
Źródło: arkusz CKE MINP-R0-100-2305. Otwórz oryginalny PDF
Rozwiązanie
Odpowiedzi z zasad oceniania CKE (sprawdzone programami poniżej na 10 000 cyfrach rozwinięcia π):
- 3.1. 902
- 3.2. 88 80 (najrzadszy fragment i liczba wystąpień), 65 124 (najczęstszy)
- 3.3. 214
- 3.4. pozycja 2781, ciąg 014576540
3.1.
c = [int(l) for l in open("pi.txt")]
print(sum(1 for i in range(len(c) - 1) if c[i] * 10 + c[i + 1] > 90))
3.2. Zliczamy wszystkie 100 fragmentów (także te, które nie wystąpiły ani razu); przy remisie wybieramy mniejszą wartość — także dla maksimum:
ile = [0] * 100
for i in range(len(c) - 1):
ile[c[i] * 10 + c[i + 1]] += 1
mn = min(range(100), key=lambda v: (ile[v], v))
mx = min(range(100), key=lambda v: (-ile[v], v))
print(f"{mn:02d} {ile[mn]}")
print(f"{mx:02d} {ile[mx]}")
3.3. Funkcja sprawdzająca definicję wprost (istnieje podział po k elementach, k od 2 do n − 2) i zliczanie okien długości 6:
def rm(s):
n = len(s)
for k in range(2, n - 1):
if all(s[i] < s[i + 1] for i in range(k - 1)) and \
all(s[i] > s[i + 1] for i in range(k, n - 1)):
return True
return False
print(sum(1 for i in range(len(c) - 5) if rm(c[i:i + 6])))
3.4. Dla każdego miejsca podziału liczymy długość ściśle rosnącego ciągu kończącego się przed podziałem (up) i ściśle malejącego zaczynającego się za nim (down); oba muszą mieć co najmniej 2 elementy. Między ostatnim elementem części rosnącej a pierwszym malejącej nie ma żadnego warunku:
n = len(c)
up = [1] * n
for i in range(1, n):
if c[i] > c[i - 1]:
up[i] = up[i - 1] + 1
down = [1] * n
for i in range(n - 2, -1, -1):
if c[i] > c[i + 1]:
down[i] = down[i + 1] + 1
best, start = 0, 0
for k in range(1, n): # część rosnąca kończy się na k-1, malejąca zaczyna na k
if up[k - 1] >= 2 and down[k] >= 2:
dl = up[k - 1] + down[k]
if dl > best:
best, start = dl, k - up[k - 1]
print(start + 1) # numer wiersza (od 1)
print("".join(map(str, c[start:start + best])))
Dla pliku przykładowego program daje 77 i 0899862.
Zad. 3.2 — przy remisie wybieramy fragment o mniejszej wartości liczbowej zarówno dla minimum, jak i dla maksimum. Trzeba też uwzględnić fragmenty, które nie wystąpiły ani razu (w pliku przykładowym 00 występuje 0 razy). Zad. 3.3 i 3.4 — definicja wymaga, by pierwsza część była ściśle rosnąca, a druga ściśle malejąca, ale między aₖ i aₖ₊₁ nie stawia żadnego warunku. Dlatego (5, 9, 9, 4, 1) jest rosnąco-malejący (podział na (5, 9) i (9, 4, 1)), a (5, 5, 3, 2, 1) nie jest. Podejście „szukam szczytu, na lewo rośnie, na prawo maleje” gubi takie przypadki — np. w pliku przykładowym nie znajduje ciągu 0899862. Zasady oceniania dają 2 pkt, gdy pominięto jeden przypadek (np. typu 123454). Zad. 3.4 — pozycję podajemy jako numer wiersza w pi.txt (od 1).
Strona arkusza CKE z treścią zadania
Rozwiązanie
3.1. Pary > 90
Składamy parę (c[i], c[i+1]) w liczbę 10·c[i] + c[i+1] i liczymy te, które są większe od 90 (dla pliku przykładowego wynik to 13).
3.2. Min / max wystąpienie pary
Zliczamy wszystkie 9999 par, uzupełniamy zerami brakujące spośród 00–99, sortujemy z odpowiednim kluczem (przy remisie wartość mniejsza).
3.3. Liczba podciągów rosnąco-malejących
Definicja: ciąg długości ≥ 4 z jednym wyraźnym szczytem (ściśle rosnący do, ściśle malejący po).
3.4. Najdłuższy ciąg rosnąco-malejący
Programowanie dynamiczne O(n): up[i] = długość ciągu rosnącego kończącego się na pozycji i; down[i] = długość malejącego od i. Dla każdego potencjalnego szczytu i: długość = up[i] + down[i] - 1.
Rozumiesz, jak to rozwiązać?
Przećwicz podobne typy zadań w aplikacji
matury-online.pl ma tysiące zadań pogrupowanych po dziedzinach. Sprawdź, czy temat „liczba Pi, analiza tekstu, fragmenty cyfr, ciągi rosnąco-malejące” zrobisz samodzielnie.
Otwórz matury-online.pl