Przykładowe zadania maturalne

Zadanie 1. Pary

W pliku pary.txt znajduje się 100 wierszy. Każdy wiersz zawiera parę danych składającą się z liczby całkowitej z przedziału od 3 do 100 i słowa (ciągi znaków) złożone z małych liter alfabetu angielskiego o długości od 1 do 50 znaków. Liczba i słowo są oddzielone znakiem spacji.

Napisz program lub programy, będące odpowiedziami na podane zadania. Uzyskane odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając każdą z nich numerem odpowiedniego zadania.

Uwaga: plik przyklad.txt zawiera przykładowe dane spełniające warunki zadania. Odpowiedzi dla danych z pliku przyklad.txt są podane pod treściami zadań oraz w pliku odp_przyklad.txt.

Zadanie 1.1.

Mocna hipoteza Goldbacha mówi, że każda parzysta liczba całkowita większa od 4 jest sumą dwóch nieparzystych liczb pierwszychliczba pierwszaliczb pierwszych, np. liczba 20 jest równa sumie 3 + 17 lub sumie 7 + 13.

Każdą liczbę parzystą z pliku pary.txt przedstaw w postaci sumy dwóch liczb pierwszych. Wypisz tę liczbę oraz dwa składniki sumy w kolejności niemalejącej. Jeżeli istnieje więcej rozwiązań (tak jak dla liczby 20), należy wypisać składniki sumy o największej różnicy.

Wyniki podaj w oddzielnych wierszach, w kolejności zgodnej z kolejnością danych w pliku pary.txt. Liczby w każdym wierszu rozdziel znakiem spacji, np. dla liczby 20 należy wypisać 20 3 17.

Dla danych z pliku przyklad.txt prawidłową odpowiedzią jest:

24 5 19
6 3 3
6 3 3

Przykładowe rozwiązanie

Nasze rozwiązanie będzie opierać się na algorytmie sita Eratostenesa. Podczas omawiania rozwiązania skupimy się wyłącznie na części związanej z liczbami pierwszymi.

Rozwiązanie zadania rozpoczniemy od wczytania liczb z pliku. Zapisujemy je w tablicy liczby.

liczby = wczytaj liczby z pliku

Następnie tworzymy tablicę wartości logicznych o nazwie sito, która posłuży do wskazywania liczb pierwszych. Z treści zadania wynika, że największą zapisaną w pliku liczbą jest 100 – nasza tablica będzie o 1 większa od największej możliwej liczby (tę wartość zapisujemy do zmiennej n). Każdej komórce w tablicy przypisujemy wartość prawda – początkowo zakładamy, że każda liczba jest pierwsza.

liczby = wczytaj liczby z pliku
n = 101

sito[n] //tablica wartości logicznych

dla i = 0, 1, ... n wykonuj:
    sito[i] = True

Kolejnym krokiem jest napisanie algorytmu sita Eratostenesa. Komórkom, których indeksy są liczbami złożonymi, przypiszemy wartość fałsz. Proces zmiany wartości nazywamy „wykreślaniem”. Po wykonaniu tej części kodu w tablicy sito, indeksy w których komórkach pozostała wartość prawda, są liczbami pierwszymi.

liczby = wczytaj liczby z pliku
n = 101

sito[n] //tablica wartości logicznych

dla i = 0, 1, ... n wykonuj:
    sito[i] = True

i = 2
dopóki i*i <= n wykonuj :
    jeżeli sito[i] == prawda wykonaj:
        j = i * i
        dopóki j < n wykonuj:
            sito[j] = fałsz
            j = j + i
	i = i + 1

W następnym kroku tworzymy dwie zmienne. Pierwsza z nich: liczbaLiczbPierwszych posłuży nam do zliczenia, ile liczb pierwszych udało nam się odszukać w badanym przedziale. Druga: liczbyPierwsze będzie tablicą liczb całkowitych – zapiszemy w niej znalezione liczby pierwsze.

liczby = wczytaj liczby z pliku
n = 101

sito[n] //tablica wartości logicznych

dla i = 0, 1, ... n wykonuj:
    sito[i] = True

i = 2
dopóki i*i <= n wykonuj :
    jeżeli sito[i] == prawda wykonaj:
        j = i * i
        dopóki j < n wykonuj:
            sito[j] = fałsz
            j = j + i
	i = i + 1

liczbaLiczbPierwszych = 0
liczbyPierwsze = pustaTablica // pusta tablica liczb całkowitych

dla i = 2, 3, ... n wykonuj:
    jeżeli sito[i] == prawda wykonaj:
        liczbaLiczbPierwszych = liczbaLiczbPierwszych + 1
        dodaj do tablicy liczbyPierwsze wartość i

Zakończyliśmy fazę przygotowania potrzebnych nam struktur danych. Nadszedł czas na przetworzenie liczb, które udało się pobrać z pliku. Piszemy pętlę dla, która będzie wskazywać kolejne liczby z tablicy liczby. Zgodnie z treścią polecenia, naszym zadaniem jest przedstawienie każdej liczby parzystej z pliku, przy pomocy sumy dwóch liczb pierwszych. Dopiszmy więc warunek badający parzystość przetwarzanej liczby. W warunku tym wykorzystamy operator mod, który służy do wyznaczania reszty z dzielenia (modulo). Dana liczba jest parzysta, jeżeli reszta z dzielenia tej liczby przez 2 wynosi 0.

liczby = wczytaj liczby z pliku
n = 101

sito[n] //tablica wartości logicznych

dla i = 0, 1, ... n wykonuj:
    sito[i] = True

i = 2
dopóki i*i <= n wykonuj :
    jeżeli sito[i] == prawda wykonaj:
        j = i * i
        dopóki j < n wykonuj:
            sito[j] = fałsz
            j = j + i
	i = i + 1

liczbaLiczbPierwszych = 0
liczbyPierwsze = pustaTablica // pusta tablica liczb całkowitych

dla i = 2, 3, ... n wykonuj:
    jeżeli sito[i] == prawda wykonaj:
        liczbaLiczbPierwszych = liczbaLiczbPierwszych + 1
        dodaj do tablicy liczbyPierwsze wartość i

dla i = 0, 1, ... n wykonuj:
    jeżeli liczby[i] mod 2 == 0 wykonaj:

Wewnątrz instrukcji warunkowej tworzymy dwie zmienne pomocnicze: lewa i prawa. Będą one indeksami odwołującymi się do tablicy liczbyPierwsze. Zmienna lewa zostanie indeksem liczby wskazującej lewy składnik dodawania. Z kolei prawa będzie wskazywać prawy składnik. Autorzy zadania oczekują, że w przypadku, gdy liczbę można wyrazić przy pomocy więcej niż jednej sumy, wskażemy tę z największą różnicą. Dlatego zmiennej lewa przypisujemy wartość 0 (pierwszą – najmniejszą liczbę pierwszą z tablicy liczbyPierwsze). Z kolei zmiennej prawa – wartość liczbaLiczbPierwszych - 1 (czyli największą znalezioną liczbę pierwszą).

liczby = wczytaj liczby z pliku
n = 101

sito[n] //tablica wartości logicznych

dla i = 0, 1, ... n wykonuj:
    sito[i] = True

i = 2
dopóki i*i <= n wykonuj :
    jeżeli sito[i] == prawda wykonaj:
        j = i * i
        dopóki j < n wykonuj:
            sito[j] = fałsz
            j = j + i

liczbaLiczbPierwszych = 0
liczbyPierwsze = pustaTablica // pusta tablica liczb całkowitych

dla i = 2, 3, ... n wykonuj:
    jeżeli sito[i] == prawda wykonaj:
        liczbaLiczbPierwszych = liczbaLiczbPierwszych + 1
        dodaj do tablicy liczbyPierwsze wartość i

dla i = 0, 1, ... n wykonuj:
    jeżeli liczby[i] mod 2 == 0 wykonaj:
        lewa = 0
        prawa = liczbaLiczbPierwszych - 1

W pętli dopóki przeszukujemy znalezione liczby pierwsze – szukamy takich, które spełniają równanie liczbyPierwsze[lewa] + liczbyPierwsze[prawa] == liczby[i]. Jeżeli wartość sumy jest mniejsza od liczby[i], zwiększamy wartość zmiennej lewa. Z kolei jeżeli wartość sumy jest większa od liczby[i], zmniejszamy wartość zmiennej prawa. Ostatnią operacją, którą chcemy wykonać, jest wypisanie wartości tworzących równianie.

liczby = wczytaj liczby z pliku
n = 101

sito[n] //tablica wartości logicznych

dla i = 0, 1, ... n wykonuj:
    sito[i] = True

i = 2
dopóki i*i <= n wykonuj :
    jeżeli sito[i] == prawda wykonaj:
        j = i * i
        dopóki j < n wykonuj:
            sito[j] = fałsz
            j = j + i
	i = i + 1

liczbaLiczbPierwszych = 0
liczbyPierwsze = pustaTablica // pusta tablica liczb całkowitych

dla i = 2, 3, ... n wykonuj:
    jeżeli sito[i] == prawda wykonaj:
        liczbaLiczbPierwszych = liczbaLiczbPierwszych + 1
        dodaj do tablicy liczbyPierwsze wartość i

dla i = 0, 1, ... n wykonuj:
    jeżeli liczby[i] mod 2 == 0 wykonaj:
        lewa = 0
        prawa = liczbaLiczbPierwszych - 1
        dopóki lewa <= prawa wykonuj:
            jeżeli liczbyPierwsze[lewa] + liczbyPierwsze[prawa] == liczby[i]:
                przerwij pętlę
            w przeciwnym przypadku jeżeli liczbyPierwsze[lewa] + liczbyPierwsze[prawa] < liczby[i]:
                lewa = lewa + 1
            w przeciwnym przypadku:
                prawa = prawa - 1
        wypisz liczby[i], liczbyPierwsze[lewa], liczbyPierwsze[prawa]

Odpowiedź:

Schemat oceniania:

Zasady oceniania:

• 3 pkt – za poprawną odpowiedź;

• 2 pkt – za odpowiedź, w której jest podany dowolny poprawny rozkład na dwie liczby pierwsze dla każdej liczby parzystej ALBO gdy zdający nie uwzględni warunku, że liczba, której rozkładu szukamy, musi być parzysta i szuka także rozkładów liczb nieparzystych (ale rozkłady dla liczb parzystych otrzymuje poprawnie);

• 1 pkt – za odpowiedź zawierającą rozkłady, w których dla każdej liczby parzystej występuje przynajmniej jedna liczba pierwsza większa od 3;

• 0 pkt – za odpowiedź niepoprawną albo za brak odpowiedzi.

Słownik