Matura Informatyka Maj 2024: Zadanie 3 - Nieparzysty skrót. Rozwiązanie i omówienie (Python, C++, Java)

Zadanie 3 z arkusza maturalnego z informatyki (maj 2024) to klasyczny przykład problemu algorytmicznego, który sprawdza umiejętność operowania na cyfrach liczby bez konieczności zamiany jej na napis (string). Tematem przewodnim jest tzw. nieparzysty skrót.

Treść zadania z arkusza CKE

Co to jest "Nieparzysty skrót"?

Zgodnie z definicją z arkusza, nieparzystym skrótem dodatniej liczby całkowitej n nazywamy liczbę m, która powstaje przez usunięcie wszystkich cyfr parzystych z zapisu dziesiętnego liczby n. Jeśli liczba składa się tylko z cyfr parzystych, jej nieparzysty skrót nie istnieje.

• Dla liczby 294762 skrótem jest 97 (usuwamy 2, 4, 6, 2).
• Dla liczby 39101 skrótem jest 3911 (usuwamy tylko 0).
• Dla liczby 224 skrót nie istnieje (wszystkie cyfry są parzyste).

Zadanie 3.1 – Algorytm (0-3 pkt)

Pierwszym krokiem jest napisanie funkcji, która dla podanej liczby n wyznaczy jej nieparzysty skrót m. Jest tu jednak ważny haczyk: algorytm może operować wyłącznie na liczbach całkowitych. Zabronione jest używanie konwersji na napisy czy tablice znaków.

Dozwolone operacje: dodawanie, odejmowanie, mnożenie, dzielenie całkowite (`div`), reszta z dzielenia (`mod`), porównywanie liczb oraz instrukcje sterujące.

Analiza algorytmu

Algorytm jest prosty, jeśli pamiętamy o szkolnej metodzie "wyciągania" cyfr z liczby od końca:

1. Używamy operacji `n mod 10`, aby pobrać ostatnią cyfrę.
2. Sprawdzamy, czy cyfra jest nieparzysta (`cyfra mod 2 == 1`). Jeśli tak, dodajemy ją do wyniku.
3. Aby zachować kolejność cyfr, musimy budować nową liczbę, mnożąc cyfrę przez odpowiednią potęgę 10 (`potega`, która zaczyna od 1, a potem rośnie: 1, 10, 100...).
4. Zmniejszamy liczbę n dziesięciokrotnie (`n div 10`).

Ważne: aktualizację potęgi (`potega = potega * 10`) wykonujemy tylko wtedy, gdy napotkamy cyfrę nieparzystą. Dzięki temu pomijamy cyfry parzyste, "sklejając" pozostałe ze sobą.

Implementacja Zadanie 3.1

Oto przykładowe implementacje w trzech językach:

def skrotLiczba(liczba):
    potega = 1
    wynik = 0
    while liczba > 0:
        cyfra = liczba % 10
        if cyfra % 2 == 1:
            wynik = potega * cyfra + wynik
            potega = potega * 10
        liczba = liczba // 10
    return wynik

int skrotLiczba(int liczba) {
    int potega = 1;
    int wynik = 0;
    while (liczba > 0) {
        int cyfra = liczba % 10;
        if (cyfra % 2 == 1) {
            wynik = potega * cyfra + wynik;
            potega = potega * 10;
        }
        liczba = liczba / 10;
    }
    return wynik;
}

public static int skrotLiczba(int liczba) {
    int potega = 1;
    int wynik = 0;
    while (liczba > 0) {
        int cyfra = liczba % 10;
        if (cyfra % 2 == 1) {
            wynik = potega * cyfra + wynik;
            potega = potega * 10;
        }
        liczba = liczba / 10;
    }
    return wynik;
}

Zadanie 3.2 – Przetwarzanie pliku (0-3 pkt)

W tym podpunkcie pracujemy z plikiem `skrot.txt`, który zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000. Każda liczba jest zapisana w osobnym wierszu. Naszym celem jest znalezienie:

• Liczby wszystkich liczb, dla których nie istnieje nieparzysty skrót.
• Największej z takich liczb.

Odpowiedź należy zapisać w pliku `wyniki3_2.txt`.

Wskazówka: Korzystając z naszej funkcji z zadania 3.1: jeśli funkcja zwróci `0`, oznacza to, że w liczbie nie było żadnych cyfr nieparzystych (czyli skrót nie istnieje).

Dane przykładowe: Dla pliku `skrot_przyklad.txt` (20 liczb) prawidłowa odpowiedź to: 2 liczby bez skrótu, największa z nich to 2428.

Rozwiązanie i odpowiedź 3.2

Po uruchomieniu programu na danych z pliku `skrot.txt`, otrzymujemy następujące wyniki:

• Liczba takich liczb: 18
• Największa z nich: 28422

Pełny kod rozwiązania 3.2

def skrotLiczba(liczba):
    potega = 1
    wynik = 0
    while liczba > 0:
        cyfra = liczba % 10
        if cyfra % 2 == 1:
            wynik = potega * cyfra + wynik
            potega = potega * 10
        liczba = liczba // 10
    return wynik

# Wczytanie danych z pliku
with open('skrot.txt', 'r') as plik:
    linie = [int(linia.strip()) for linia in plik]

# Znajdź liczby bez skrótu
bezSkrotu = []
for liczba in linie:
    if skrotLiczba(liczba) == 0:
        bezSkrotu.append(liczba)

# Zapisz wynik
with open('wyniki3_2.txt', 'w') as plik:
    plik.write(f"{len(bezSkrotu)}\n")
    plik.write(f"{max(bezSkrotu)}\n")

print(f"Liczba: {len(bezSkrotu)}, Największa: {max(bezSkrotu)}")

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int skrotLiczba(int liczba) {
    int potega = 1;
    int wynik = 0;
    while (liczba > 0) {
        int cyfra = liczba % 10;
        if (cyfra % 2 == 1) {
            wynik = potega * cyfra + wynik;
            potega = potega * 10;
        }
        liczba = liczba / 10;
    }
    return wynik;
}

int main() {
    ifstream plik("skrot.txt");
    ofstream wynik("wyniki3_2.txt");
    
    vector<int> bezSkrotu;
    int liczba;
    
    while (plik >> liczba) {
        if (skrotLiczba(liczba) == 0) {
            bezSkrotu.push_back(liczba);
        }
    }
    
    int maksymalna = *max_element(bezSkrotu.begin(), bezSkrotu.end());
    
    wynik << bezSkrotu.size() << endl;
    wynik << maksymalna << endl;
    
    cout << "Liczba: " << bezSkrotu.size() << ", Największa: " << maksymalna << endl;
    return 0;
}

Zadanie 3.3 – NWD i skrót (0-4 pkt)

Ostatnia część zadania korzysta z pliku `skrot2.txt`, który zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000. Dla każdej z tych liczb istnieje nieparzysty skrót.

Musimy wypisać te liczby, dla których największy wspólny dzielnik (NWD) liczby i jej nieparzystego skrótu wynosi 7. Odpowiedź zapisujemy w pliku `wyniki3_3.txt`, po jednej liczbie w wierszu.

Dane przykładowe: Dla pliku `skrot2_przyklad.txt` prawidłowa odpowiedź to: 4872 i 23527.

Wymaga to użycia algorytmu Euklidesa (lub wbudowanej funkcji `gcd`).

Rozwiązanie i odpowiedź 3.3

Prawidłowe liczby spełniające warunek (NWD = 7) to:

• 784 (skrót: 7, NWD(784, 7) = 7)
• 14196 (skrót: 119, NWD(14196, 119) = 7)
• 2247 (skrót: 7, NWD(2247, 7) = 7)
• 24087 (skrót: 7, NWD(24087, 7) = 7)
• 3871 (skrót: 371, NWD(3871, 371) = 7)
• 10192 (skrót: 119, NWD(10192, 119) = 7)

Pełny kod rozwiązania 3.3

from math import gcd

def skrotLiczba(liczba):
    potega = 1
    wynik = 0
    while liczba > 0:
        cyfra = liczba % 10
        if cyfra % 2 == 1:
            wynik = potega * cyfra + wynik
            potega = potega * 10
        liczba = liczba // 10
    return wynik

# Wczytanie danych z pliku
with open('skrot2.txt', 'r') as plik:
    linie = [int(linia.strip()) for linia in plik]

# Znajdź liczby z NWD = 7
with open('wyniki3_3.txt', 'w') as wynik:
    for liczba in linie:
        skrot = skrotLiczba(liczba)
        if gcd(liczba, skrot) == 7:
            wynik.write(f"{liczba}\n")
            print(liczba)

#include <iostream>
#include <fstream>
using namespace std;

int skrotLiczba(int liczba) {
    int potega = 1;
    int wynik = 0;
    while (liczba > 0) {
        int cyfra = liczba % 10;
        if (cyfra % 2 == 1) {
            wynik = potega * cyfra + wynik;
            potega = potega * 10;
        }
        liczba = liczba / 10;
    }
    return wynik;
}

// Algorytm Euklidesa dla NWD
int nwd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    ifstream plik("skrot2.txt");
    ofstream wynik("wyniki3_3.txt");
    
    int liczba;
    while (plik >> liczba) {
        int skrot = skrotLiczba(liczba);
        if (nwd(liczba, skrot) == 7) {
            wynik << liczba << endl;
            cout << liczba << endl;
        }
    }
    return 0;
}

Uwaga: W C++ funkcję NWD (`gcd`) można też użyć z biblioteki `` (od C++17): `#include ` i `std::gcd(a, b)`.

Najczęstsze błędy i na co uważać

• Konwersja na string – zabroniona w zadaniu 3.1! Musisz operować wyłącznie na operacjach arytmetycznych.
• Zła kolejność cyfr – pamiętaj, że wyciągasz cyfry od końca (od jednostek), więc musisz budować wynik mnożąc przez potęgę 10.
• Aktualizacja potęgi – potęgę zwiększamy TYLKO gdy dodajemy cyfrę nieparzystą do wyniku!
• Dzielenie całkowite – w Pythonie używaj `//`, nie `/` (które daje float).
• Przypadek braku skrótu – jeśli funkcja zwraca 0, to znaczy że skrót nie istnieje (wszystkie cyfry były parzyste).

Podsumowanie i punktacja

Łącznie: 10 punktów za całe zadanie 3.

Zadanie 3 z maja 2024 to świetny test na rozumienie operacji modulo i dzielenia całkowitego. Kluczem do sukcesu było poprawne zaimplementowanie funkcji `skrotLiczba` zgodnie z surowymi wytycznymi (brak konwersji na string), co następnie pozwoliło łatwo rozwiązać podpunkty 3.2 i 3.3. Pamiętaj, że na maturze liczy się nie tylko poprawność wyniku, ale też zgodność z wymaganiami!