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.

Rwtq0oLbKAQfI

Plik txt z przykładowymi danymi.

Plik przyklad.txt do zadania nr 1
Plik TXT o rozmiarze 1 012.00 B w języku polskim
R1W3g5pkIoMWm

Plik txt z odpowiedzią do zadania nr 1.

Plik odp_przyklad.txt do zadania nr 1
Plik TXT o rozmiarze 865.00 B w języku polskim
R1buZs1TGzKOO

Plik txt z wartościami liczbowymi połączonymi w prazy z ciągami znaków.

Plik pary.txt do zadania nr 1
Plik TXT o rozmiarze 1.71 KB w języku polskim

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.

Zadanie zostało przygotowane przez Centralną Komisję Egzaminacyjną i pojawiło się na egzaminie maturalnym z informatyki w czerwcu 2020 roku (cz. 2.). Cały arkusz można znaleźć na stronie internetowej CKE.

Ponieważ na egzaminie maturalnym uczniowie mają swobodę wyboru języka programowania, nie będziemy przedstawiać rozwiązania zadania w konkretnym języku, lecz posłużymy się pseudokodem.

Dokonaj implementacji proponowanego pseudokodu w języku, w którym programujesz.

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

Linia 1. 24 5 19. Linia 2. 6 3 3. Linia 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.

Linia 1. liczby znak równości 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.

Linia 1. liczby znak równości wczytaj liczby z pliku. Linia 2. n znak równości 101. Linia 4. sito otwórz nawias kwadratowy n zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica wartości logicznych. Linia 6. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 7. sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 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.

Linia 1. liczby znak równości wczytaj liczby z pliku. Linia 2. n znak równości 101. Linia 4. sito otwórz nawias kwadratowy n zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica wartości logicznych. Linia 6. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 7. sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości True. Linia 9. i znak równości 2. Linia 10. dopóki i asterysk i otwórz nawias ostrokątny znak równości n wykonuj dwukropek. Linia 11. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 12. j znak równości i asterysk i. Linia 13. dopóki j otwórz nawias ostrokątny n wykonuj dwukropek. Linia 14. sito otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości fałsz. Linia 15. j znak równości j plus i. Linia 16. i znak równości i plus 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.

Linia 1. liczby znak równości wczytaj liczby z pliku. Linia 2. n znak równości 101. Linia 4. sito otwórz nawias kwadratowy n zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica wartości logicznych. Linia 6. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 7. sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości True. Linia 9. i znak równości 2. Linia 10. dopóki i asterysk i otwórz nawias ostrokątny znak równości n wykonuj dwukropek. Linia 11. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 12. j znak równości i asterysk i. Linia 13. dopóki j otwórz nawias ostrokątny n wykonuj dwukropek. Linia 14. sito otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości fałsz. Linia 15. j znak równości j plus i. Linia 16. i znak równości i plus 1. Linia 18. liczbaLiczbPierwszych znak równości 0. Linia 19. liczbyPierwsze znak równości pustaTablica prawy ukośnik prawy ukośnik pusta tablica liczb całkowitych. Linia 21. dla i znak równości 2 przecinek 3 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 22. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 23. liczbaLiczbPierwszych znak równości liczbaLiczbPierwszych plus 1. Linia 24. 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.

Linia 1. liczby znak równości wczytaj liczby z pliku. Linia 2. n znak równości 101. Linia 4. sito otwórz nawias kwadratowy n zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica wartości logicznych. Linia 6. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 7. sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości True. Linia 9. i znak równości 2. Linia 10. dopóki i asterysk i otwórz nawias ostrokątny znak równości n wykonuj dwukropek. Linia 11. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 12. j znak równości i asterysk i. Linia 13. dopóki j otwórz nawias ostrokątny n wykonuj dwukropek. Linia 14. sito otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości fałsz. Linia 15. j znak równości j plus i. Linia 16. i znak równości i plus 1. Linia 18. liczbaLiczbPierwszych znak równości 0. Linia 19. liczbyPierwsze znak równości pustaTablica prawy ukośnik prawy ukośnik pusta tablica liczb całkowitych. Linia 21. dla i znak równości 2 przecinek 3 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 22. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 23. liczbaLiczbPierwszych znak równości liczbaLiczbPierwszych plus 1. Linia 24. dodaj do tablicy liczbyPierwsze wartość i. Linia 26. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 27. jeżeli liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy mod 2 znak równości znak równości 0 wykonaj dwukropek.

Wewnątrz instrukcji warunkowej tworzymy dwie zmienne pomocnicze: lewaprawa. 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ą).

Linia 1. liczby znak równości wczytaj liczby z pliku. Linia 2. n znak równości 101. Linia 4. sito otwórz nawias kwadratowy n zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica wartości logicznych. Linia 6. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 7. sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości True. Linia 9. i znak równości 2. Linia 10. dopóki i asterysk i otwórz nawias ostrokątny znak równości n wykonuj dwukropek. Linia 11. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 12. j znak równości i asterysk i. Linia 13. dopóki j otwórz nawias ostrokątny n wykonuj dwukropek. Linia 14. sito otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości fałsz. Linia 15. j znak równości j plus i. Linia 17. liczbaLiczbPierwszych znak równości 0. Linia 18. liczbyPierwsze znak równości pustaTablica prawy ukośnik prawy ukośnik pusta tablica liczb całkowitych. Linia 20. dla i znak równości 2 przecinek 3 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 21. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 22. liczbaLiczbPierwszych znak równości liczbaLiczbPierwszych plus 1. Linia 23. dodaj do tablicy liczbyPierwsze wartość i. Linia 25. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 26. jeżeli liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy mod 2 znak równości znak równości 0 wykonaj dwukropek. Linia 27. lewa znak równości 0. Linia 28. prawa znak równości liczbaLiczbPierwszych minus 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.

Linia 1. liczby znak równości wczytaj liczby z pliku. Linia 2. n znak równości 101. Linia 4. sito otwórz nawias kwadratowy n zamknij nawias kwadratowy prawy ukośnik prawy ukośnik tablica wartości logicznych. Linia 6. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 7. sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości True. Linia 9. i znak równości 2. Linia 10. dopóki i asterysk i otwórz nawias ostrokątny znak równości n wykonuj dwukropek. Linia 11. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 12. j znak równości i asterysk i. Linia 13. dopóki j otwórz nawias ostrokątny n wykonuj dwukropek. Linia 14. sito otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości fałsz. Linia 15. j znak równości j plus i. Linia 16. i znak równości i plus 1. Linia 18. liczbaLiczbPierwszych znak równości 0. Linia 19. liczbyPierwsze znak równości pustaTablica prawy ukośnik prawy ukośnik pusta tablica liczb całkowitych. Linia 21. dla i znak równości 2 przecinek 3 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 22. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 23. liczbaLiczbPierwszych znak równości liczbaLiczbPierwszych plus 1. Linia 24. dodaj do tablicy liczbyPierwsze wartość i. Linia 26. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka n wykonuj dwukropek. Linia 27. jeżeli liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy mod 2 znak równości znak równości 0 wykonaj dwukropek. Linia 28. lewa znak równości 0. Linia 29. prawa znak równości liczbaLiczbPierwszych minus 1. Linia 30. dopóki lewa otwórz nawias ostrokątny znak równości prawa wykonuj dwukropek. Linia 31. jeżeli liczbyPierwsze otwórz nawias kwadratowy lewa zamknij nawias kwadratowy plus liczbyPierwsze otwórz nawias kwadratowy prawa zamknij nawias kwadratowy znak równości znak równości liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 32. przerwij pętlę. Linia 33. w przeciwnym przypadku jeżeli liczbyPierwsze otwórz nawias kwadratowy lewa zamknij nawias kwadratowy plus liczbyPierwsze otwórz nawias kwadratowy prawa zamknij nawias kwadratowy otwórz nawias ostrokątny liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 34. lewa znak równości lewa plus 1. Linia 35. w przeciwnym przypadku dwukropek. Linia 36. prawa znak równości prawa minus 1. Linia 37. wypisz liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek liczbyPierwsze otwórz nawias kwadratowy lewa zamknij nawias kwadratowy przecinek liczbyPierwsze otwórz nawias kwadratowy prawa zamknij nawias kwadratowy.

Odpowiedź:

R1DBFIdWzhIUD

Plik txt zawierający wynik do zadania nr 1

Plik "wynik.txt" do zadania nr 1
Plik TXT o rozmiarze 247.00 B w języku polskim

Schemat oceniania:

Wymagania ogólne

Wymagania szczegółowe

Rozwiązywanie problemów i podejmowanie decyzji z wykorzystaniem komputera, stosowanie podejścia algorytmicznego.

Zdający analizuje, modeluje i rozwiązuje sytuacje problemowe z różnych dziedzin.

Zdający stosuje podejście algorytmiczne do rozwiązywania problemu.

Zdający formułuje przykłady sytuacji problemowych, których rozwiązanie wymaga podejścia algorytmicznego i użycia komputera.

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.

Schemat oceniania pochodzi z arkusza odpowiedzi egzaminu maturalnego z informatyki z 2020 roku. Cały arkusz można znaleźć na stronie internetowej Centralnej Komisji Egzaminacyjnej.

Słownik

kryptografia
kryptografia

dziedzina kryptologii, zajmująca się zabezpieczaniem informacji przed niepowołanym dostępem

liczba pierwsza
liczba pierwsza

liczba naturalna większa od 1, która dzieli się tylko przez jeden i przez samą siebie

sito Eratostenesa
sito Eratostenesa

algorytm, który przesiewa liczby z określonego przedziału w taki sposób, że zostają w nim tylko liczby pierwsze; służy on do znajdywania wszystkich liczb pierwszych w podanym przedziale