Zadanie 3
Matura z informatyki, maj 2024, poziom rozszerzony
Wymaganie: I.2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. I.3) objaśnia dobrany algorytm, uzasadnia poprawność rozwiązania na wybranych przykładach danych i ocenia jego efektywność. I.5) przedstawia sposoby reprezentowania w komputerze znaków, liczb […]. I+II.1) zapisuje za pomocą listy kroków, schematu blokowego lub pseudokodu i implementuje w wybranym języku programowania algorytmy poznane na wcześniejszych etapach […]. P.I.2) […] a) na liczbach: […] zamiany reprezentacji liczb między pozycyjnymi systemami liczbowymi […]. P.II.1) projektuje i programuje rozwiązania problemów z różnych dziedzin […]. II.1) projektuje i tworzy rozbudowane programy w procesie rozwiązywania problemów, wykorzystuje w programach dobrane do algorytmów struktury danych […]. II.2) stosuje zasady programowania strukturalnego i obiektowego w rozwiązywaniu problemów. II.3) sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów.
Treść zadania
Zadanie 3. Nieparzysty skrót
Nieparzystym skrótem dodatniej liczby całkowitej n nazwiemy dodatnią liczbę całkowitą m, która powstaje przez usunięcie cyfr parzystych z zapisu dziesiętnego liczby n.
Nieparzysty skrót liczby całkowitej n nie istnieje, gdy jej zapis dziesiętny składa się tylko z cyfr parzystych.
Przykład:
- Nieparzystym skrótem liczby 294762 jest liczba 97.
- Nieparzystym skrótem liczby 39101 jest liczba 3911.
- Nieparzysty skrót liczby 224 nie istnieje.
Specyfikacja: Dane: n — dodatnia liczba całkowita, taka że istnieje dla niej nieparzysty skrót. Wynik: m — nieparzysty skrót liczby n.
Zadanie 3.1. (0–3) W postaci pseudokodu lub w wybranym języku programowania napisz funkcję, która dla dodatniej liczby całkowitej n, takiej że istnieje dla niej nieparzysty skrót, wyznacza liczbę m — nieparzysty skrót liczby n.
Uwaga: Twój algorytm może używać wyłącznie zmiennych przechowujących liczby całkowite oraz może operować wyłącznie na liczbach całkowitych. W zapisie możesz wykorzystać tylko operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, resztę z dzielenia oraz porównywanie liczb, instrukcje sterujące, przypisania do zmiennych lub samodzielnie napisane funkcje, wykorzystujące wyżej wymienione operacje. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione.
Zadanie 3.2. (0–3) Plik skrot.txt zawiera 200 dodatnich liczb całkowitych, mniejszych od 30 000. Każda liczba jest zapisana w osobnym wierszu. Dla co najmniej jednej z tych liczb nie istnieje nieparzysty skrót. Napisz program, który wyznaczy liczbę wszystkich tych liczb z pliku skrot.txt, dla których nie istnieje nieparzysty skrót, oraz poda największą z nich. Odpowiedź zapisz w pliku wyniki3_2.txt. (Dla pliku skrot_przyklad.txt prawidłową odpowiedzią jest: 2 oraz 2428 – w pliku są dwie liczby bez nieparzystego skrótu: 266 i 2428.)
Zadanie 3.3. (0–4) Plik skrot2.txt zawiera 200 dodatnich liczb całkowitych, mniejszych od 30 000. Każda liczba jest zapisana w osobnym wierszu. Dla każdej z tych liczb istnieje nieparzysty skrót. Napisz program, który wypisze liczby z pliku skrot2.txt, dla których największy wspólny dzielnik liczby i jej nieparzystego skrótu jest równy 7. Odpowiedź zapisz w pliku wyniki3_3.txt. Twój program powinien wypisać w każdym wierszu wyniku po jednej liczbie z pliku skrot2.txt, dla której jest spełniony powyższy warunek. (Dla pliku skrot2_przyklad.txt prawidłową odpowiedzią jest: 4872 i 23527.)
Źródło: arkusz CKE MINP-R0-100-2405. Otwórz oryginalny PDF
Rozwiązanie
Zadanie 3.1. Funkcja w pseudokodzie, używająca tylko mod/div i porównań:
funkcja nieparzystyskrot(n):
m ← 0
b ← 1
dopóki n > 0 wykonuj:
a ← n mod 10
n ← n div 10
jeżeli (a mod 2 = 1):
m ← m + a * b
b ← b * 10
zwróć m
Idea: przechodzimy cyfry n od najmłodszej, każdą nieparzystą cyfrę dopisujemy z lewej strony m (z mnożnikiem b = 1, 10, 100, …). Cyfry parzyste pomijamy bez zwiększania b.
Zadanie 3.2. Program w Pythonie:
def nieparzysty_skrot(n):
m, b = 0, 1
while n > 0:
a = n % 10
n //= 10
if a % 2 == 1:
m += a * b
b *= 10
return m # 0 oznacza brak skrótu
brak = 0
najw = 0
with open("skrot.txt") as f:
for line in f:
n = int(line.strip())
if nieparzysty_skrot(n) == 0:
brak += 1
if n > najw:
najw = n
with open("wyniki3_2.txt", "w") as g:
g.write(f"{brak}\n{najw}\n")
Zadanie 3.3. Program wypisujący liczby z skrot2.txt, dla których NWD(j, nieparzysty_skrót(j)) = 7:
from math import gcd
def nieparzysty_skrot(n):
m, b = 0, 1
while n > 0:
a = n % 10
n //= 10
if a % 2 == 1:
m += a * b
b *= 10
return m
with open("skrot2.txt") as f, open("wyniki3_3.txt", "w") as g:
for line in f:
j = int(line.strip())
m = nieparzysty_skrot(j)
if m > 0 and gcd(j, m) == 7:
g.write(f"{j}\n")
Wynik dla skrot2_przyklad.txt: 4872, 23527.
Odpowiedzi z zasad oceniania CKE: 3.2 — 18 liczb bez nieparzystego skrótu, największa z nich 28422; 3.3 — 784, 14196, 2247, 24087, 3871, 10192.
Uwaga: (1) w 3.1 mnożnik b zwiększamy tylko po dopisaniu cyfry nieparzystej — gdyby rósł także przy cyfrach parzystych, w wyniku pojawiłyby się zera w miejscu usuniętych cyfr; (2) zamiana n na napis jest sprzeczna z ograniczeniami zadania (tylko liczby całkowite); (3) w 3.2 liczba bez nieparzystego skrótu to taka, dla której funkcja zwraca 0 (same cyfry parzyste); (4) w 3.3 warunek to NWD(n, m) równe 7 — nie wystarczy, że NWD jest podzielne przez 7 (np. NWD = 14 nie spełnia warunku).
Strona arkusza CKE z treścią zadania
Rozwiązanie
Trzy podzadania opierają się na tym samym pomyśle: filtrowanie cyfr nieparzystych z zapisu dziesiętnego liczby i sklejanie ich z powrotem w liczbę.
Kluczowy trick (3.1): kiedy iterujemy n od najmłodszej cyfry, każdą zachowaną nieparzystą cyfrę dopisujemy z lewej strony skrótu m (na kolejnej, wyższej pozycji), ale tylko wtedy zwiększamy mnożnik pozycji b. Cyfry parzyste są pomijane — nie zwiększają b, więc nie zostawiają w m “dziury”.
Weryfikacja na przykładach z treści:
- 294762: cyfry od końca 2,6,7,4,9,2 → nieparzyste: 7, 9 → m = 97 ✓
- 39101: cyfry od końca 1,0,1,9,3 → nieparzyste: 1,1,9,3 → m = 3911 ✓
- 224: cyfry 4,2,2 → brak nieparzystych → m = 0 (skrót nie istnieje) ✓
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 „programowanie, nieparzysty skrót, cyfry parzyste/nieparzyste, plik tekstowy” zrobisz samodzielnie.
Otwórz matury-online.pl