{"id":"informator-maturalny-informatyka-2015/zad/21","paper_id":"informator-maturalny-informatyka-2015","number":"21","points":null,"ptype":"open","subject":"informatyka","category":"informator-maturalny","year":2015,"month":null,"level":null,"text":"Zadanie 21. Podzielność (0-10)\nW trzech plikach tekstowych liczby1.txt, liczby2.txt i liczby3.txt zapisano\npo 1000 dodatnich liczb binarnych. W każdym pliku liczby zapisano w kolejnych wierszach\npo jednej liczbie w wierszu. W pliku liczby1.txt długość zapisu każdej z liczb jest nie\nwiększa od 12. W pliku liczby2.txt długość zapisu każdej z liczb jest nie większa od 30,\nzaś w pliku liczby3.txt długość zapisu każdej liczby nie przekracza 200.\nDla każdego z plików z danymi wyznacz, ile zawiera on\n- liczb podzielnych przez 2,\n- liczb podzielnych przez 3,\n- liczb podzielnych przez 5.\nPrzykład:\nW pliku z 3 liczbami binarnymi:\n10101\n1100\n1110\nsą 2 liczby podzielne przez 2, 1 liczba podzielna przez 3 i 1 liczba podzielna przez 5.\nDo oceny oddajesz plik(i) o nazwie zawierający\ntu wpisz nazwę pliku/plików\nkomputerową realizację Twoich obliczeń oraz plik tekstowy podzielnosc.txt\nzawierający w dziewięciu kolejnych wierszach dziewięć liczb, po jednej w wierszu. Pierwsze\ntrzy wiersze powinny zawierać liczby liczb z pliku liczby1.txt podzielnych odpowiednio\nprzez 2, 3 i 5. Kolejne trzy wiersze powinny zawierać liczby liczb z pliku liczby2.txt\npodzielnych odpowiednio przez 2, 3 i 5, a ostatnie trzy wiersze liczby liczb z pliku\nliczby3.txt podzielnych odpowiednio przez 2, 3 i 5.\nWymagania ogólne\nIII. Rozwiązywanie problemów i podejmowanie\ndecyzji z wykorzystaniem komputera, z zastosowaniem\npodejścia algorytmicznego.\nWymagania szczegółowe\n5. Rozwiązywanie problemów i podejmowanie decyzji\nz wykorzystaniem komputera, stosowanie podejścia\nalgorytmicznego.\nZdający:\n1) analizuje, modeluje i rozwiązuje sytuacje\nproblemowe z różnych dziedzin,\n11) opisuje podstawowe algorytmy i stosuje algorytmy\nna liczbach całkowitych,\n12) projektuje rozwiązanie problemu (realizację\nalgorytmu) i dobiera odpowiednią strukturę danych,\n15) stosuje zasady programowania strukturalnego\ni modularnego do rozwiązywania problemu,\n23) stosuje podstawowe konstrukcje programistyczne\nw wybranym języku programowania, instrukcje\niteracyjne i warunkowe, rekurencję i procedury,\n72 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\ninstrukcje wejścia i wyjścia, poprawnie tworzy\nstrukturę programu,\n24) dobiera najlepszy algorytm, odpowiednie\nstruktury danych i oprogramowanie do rozwiązania\npostawionego problemu,\n26) ocenia poprawność komputerowego rozwiązania\nna podstawie jego testowania.\nSchemat punktowania\nCzynność\nLiczba\npunktów\nza zadanie\nZa poprawne wyniki dla pliku 1 - 2 punkty.\nZa poprawne wyniki dla pliku 2 - 3 punkty.\nZa poprawne wyniki dla pliku 3 - 4 punkty.\n9\nZadanie 21. Podzielność (0-10) - rozwiązanie\nPliki z danymi, plik programu źródłowego oraz plik podzielnosc.txt zawierający\nodpowiedzi znajdują się w folderze PODZIELNOSC.\nKomentarz\nJedna z metod rozwiązania tego zadania mogła by polegać na przytoczeniu i wykorzystaniu\nwłasności podzielności liczb binarnych. O ile własność podzielności przez 2 jest oczywista\ni powszechnie znana - najmniej znaczącą cyfrą takiej liczby musi być 0 - to już własności\npodzielności liczby binarnych przez inne liczby nie są tak naturalne i znane. Dla każdego\ndzielnika taka własność byłaby pewnie inna i prowadziłaby do algorytmu właściwego tylko\ndla tej własności. Przedstawimy algorytm, który jest jednakowy dla wszystkich dzielników\nz dokładnością do parametru, którym jest właśnie dzielnik.\nJest naturalne rozwiązanie, które pozwala stwierdzić, czy dana, dodatnia liczba binarna b,\njest podzielna całkowicie przez dodatnią (dziesiętną) liczbę całkowitą p. Wystarczy obliczyć\n(dziesiętną) wartość d liczby b i sprawdzić, czy p dzieli całkowicie d. W tym celu\nwykorzystujemy dostępny w większości języków programowania operator mod obliczania\nreszty z dzielenia liczb całkowitych i sprawdzamy, czy d mod p = 0. Do zamiany liczby\nbinarnej b na jej odpowiednik dziesiętny d można zastosować schemat Hornera. Prawda\njakie to proste? Jest tylko jeden mały problem. W kolejnych plikach z danymi są coraz\nwiększe liczby. W pliku liczby1.txt długość zapisu każdej z liczb jest nie większa niż 12\ni do zapisu każdej takiej liczby wystarczają dwa bajty, do zapisu jednej liczby z pliku\nliczby2.txt potrzeba już 4 bajtów, natomiast do zapisu liczby z pliku liczby3.txt\nmoże być potrzebnych 25 bajtów na każdą z nich. Jeśli język programowania użyty do\nrozwiązania pozwala reprezentować tak duże liczby i umożliwia wykonywanie na nich\npodstawowych arytmetycznych - dodawanie, mnożenie i branie modulo - to powyżej opisane\nrozwiązanie jest wystarczające. Często jednak języki programowania nie umożliwiają\nbezpośredniego operowania na bardzo dużych liczbach. Wówczas pozostaje albo\nzaprogramować własną arytmetykę dużych liczb, albo, jak w tym przypadku, skorzystać\nz pewnych własności używanych operacji arytmetycznych. Tutaj skorzystamy z własności\noperacji modulo brania reszty z dzielenia, które to własności pozwalają nam operować tylko\nna resztach z dzielenia przez dzielnik p, a nie na całych liczbach. Każda taka reszta jest nie\nwiększa od p. Dwie podstawowe, wykorzystywane przez nas własności są następujące:\nPrzykładowe zadania z rozwiązaniami 73\nDla dodatnich liczb całkowitych a, b i p mamy:\n(1) (a + b) mod p =( a mod p + b mod p) mod p\n(2) (a*b) mod p = ((a mod p) * (b mod p)) mod p\nTak więc do policzenia reszty z dzielenia przez p dodatniej liczby całkowitej d, której wartość\njest taka sama jak wartość liczby binarnej b, należy po prostu zastosować schemat Hornera\nobliczania wartości d z zapisu b pamiętając, żeby wszystkie obliczenia wykonywać modulo p.\nOto funkcja zapisana w języku programowania C++, która dla liczby binarnej b podanej\nw postaci zero-jedynkowego napisu i dodatniego, całkowitego podzielnika p, oblicza resztę\nz dzielenia wartości dziesiętnej liczby b przez p.\nint Reszta(string b, int p){\nconst char zero = '0';\nint dl = b.length(); //obliczenie długości zapisu liczby b\nint d = 0; // po zakończeniu obliczeń wartością d będzie\n// wartość dziesiętna liczby b modulo p\n// schemat Hornera modulo p\nfor (int j = 0; j < dl; j++){\nint cyfra = b[j] - zero;//odzyskanie kolejnej cyfry liczby b\n// poczynając od najbardziej znaczącej\nd = (d*2 + cyfra) % p; // % jest operatorem modulo w C++\n}\nreturn d;\n}\nNależy zwrócić jeszcze uwagę na drobiazg, jakim jest odzyskiwanie wartości liczbowych\nkolejnych cyfr zapisu liczby b. Liczba b jest zadana jako napis złożony ze znaków ‘0’ i ‘1’.\nKażdy ze znaków ‘0’ lub ‘1’ do obliczeń arytmetycznych należy zamienić odpowiednio na\nliczbę 0 lub 1. Do tego celu najprościej wykorzystać fakt, że cyfry ‘0’, ‘1’, …, ‘9’ są\nkodowane kolejnymi liczbami naturalnymi poczynając od kodu znaku ‘0’. Tak więc, gdy od\nkodu cyfry odejmiemy kod cyfry ‘0’, to otrzymamy liczbę odpowiadającą tej cyfrze.\nW przedstawionym powyżej rozwiązaniu wykorzystujemy ten fakt - wartość wyrażenia b[j]\n- zero jest obliczana z wykorzystaniem kodów cyfr b[j] i zero.\nPoniżej przedstawiamy program Podzielnosc zapisany w języku C++, który oblicza\nżądane wyniki dla jednego pliku. Dla przykładu, żeby uzyskać wyniki dla pliku\nliczby1.txt można program wykonywalny Podzielnosc uruchomić w katalogu\nzawierającym plik liczby1.txt następującą komendą z wiersza poleceń:\nPodzielnosc < liczby1.txt > wyniki1.txt\nWyniki znajdą się w pliku tekstowym wyniki1.txt w tym samym katalogu. Na koniec\ntrzeba pamiętać, żeby wyniki obliczeń dla wszystkich trzech plików umieścić w jednym pliku\ntekstowym podzielnosc.txt zgodnie z opisem w treści zadania.\n//Program Podzielnosc\n#include \nusing namespace std;\nint Reszta(string b, int p){\nconst char zero = '0';\n74 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nint dl = b.length(); //obliczenie długości zapisu liczby b\nint d = 0; //po zakończeniu obliczeń wartością d będzie\n// wartość dziesiętna liczby b modulo p\n// schemat Hornera modulo p\nfor (int j = 0; j < dl; j++){\nint cyfra = b[j] - zero; //odzyskanie kolejnej cyfry liczby\nb\n//poczynając od najbardziej znaczącej\nd = (d*2 + cyfra) % p; //% jest operatorem modulo w C++\n}\nreturn d;\n}\nint main(){\nstring liczba;\nconst int n = 1000; //rozmiar danych\nint podz_2 = 0, podz_3 = 0, podz_5 = 0; // podz_p - liczba\nliczb\n// podzielnych przez p\nfor (int i = 0; i < n; i++){\ncin >> liczba; //wczytanie kolejnej liczby;\nif (Reszta(liczba,2) == 0) podz_2++;\nif (Reszta(liczba,3) == 0) podz_3++;\nif (Reszta(liczba,5) == 0) podz_5++;\n}\ncout << \"podzielne przez \" << 2 << \" : \" << podz_2 << \"\\n\";\ncout << \"podzielne przez \" << 3 << \" : \" << podz_3 << \"\\n\";\ncout << \"podzielne przez \" << 5 << \" : \" << podz_5 << \"\\n\";\nreturn 0;\n}\nPrzykładowe zadania z rozwiązaniami 75","answer":null,"answer_text":null,"solution":null,"image":"img/informator-maturalny-informatyka-2015/zad-21.webp","solution_image":null,"topics":null,"page_from":71,"source":"ocr","answer_source":null,"answer_text_source":null,"solution_source":null,"text_source":"ocr","source_label":"Informatyka · Informator maturalny · 2015","subject_label":"Informatyka","category_label":"Informator maturalny","text_html":"

Zadanie 21. Podzielność (0-10)
W trzech plikach tekstowych liczby1.txt, liczby2.txt i liczby3.txt zapisano
po 1000 dodatnich liczb binarnych. W każdym pliku liczby zapisano w kolejnych wierszach
po jednej liczbie w wierszu. W pliku liczby1.txt długość zapisu każdej z liczb jest nie
większa od 12. W pliku liczby2.txt długość zapisu każdej z liczb jest nie większa od 30,
zaś w pliku liczby3.txt długość zapisu każdej liczby nie przekracza 200.
Dla każdego z plików z danymi wyznacz, ile zawiera on

\n\n

Przykład:
W pliku z 3 liczbami binarnymi:
10101
1100
1110
są 2 liczby podzielne przez 2, 1 liczba podzielna przez 3 i 1 liczba podzielna przez 5.
Do oceny oddajesz plik(i) o nazwie zawierający
tu wpisz nazwę pliku/plików
komputerową realizację Twoich obliczeń oraz plik tekstowy podzielnosc.txt
zawierający w dziewięciu kolejnych wierszach dziewięć liczb, po jednej w wierszu. Pierwsze
trzy wiersze powinny zawierać liczby liczb z pliku liczby1.txt podzielnych odpowiednio
przez 2, 3 i 5. Kolejne trzy wiersze powinny zawierać liczby liczb z pliku liczby2.txt
podzielnych odpowiednio przez 2, 3 i 5, a ostatnie trzy wiersze liczby liczb z pliku
liczby3.txt podzielnych odpowiednio przez 2, 3 i 5.
Wymagania ogólne
III. Rozwiązywanie problemów i podejmowanie
decyzji z wykorzystaniem komputera, z zastosowaniem
podejścia algorytmicznego.
Wymagania szczegółowe

\n
  1. Rozwiązywanie problemów i podejmowanie decyzji
\n

z wykorzystaniem komputera, stosowanie podejścia
algorytmicznego.
Zdający:

\n
  1. analizuje, modeluje i rozwiązuje sytuacje
\n

problemowe z różnych dziedzin,

\n
  1. opisuje podstawowe algorytmy i stosuje algorytmy
\n

na liczbach całkowitych,

\n
  1. projektuje rozwiązanie problemu (realizację
\n

algorytmu) i dobiera odpowiednią strukturę danych,

\n
  1. stosuje zasady programowania strukturalnego
\n

i modularnego do rozwiązywania problemu,

\n
  1. stosuje podstawowe konstrukcje programistyczne
\n

w wybranym języku programowania, instrukcje
iteracyjne i warunkowe, rekurencję i procedury,
72 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
instrukcje wejścia i wyjścia, poprawnie tworzy
strukturę programu,

\n
  1. dobiera najlepszy algorytm, odpowiednie
\n

struktury danych i oprogramowanie do rozwiązania
postawionego problemu,

\n
  1. ocenia poprawność komputerowego rozwiązania
\n

na podstawie jego testowania.
Schemat punktowania
Czynność
Liczba
punktów
za zadanie
Za poprawne wyniki dla pliku 1 - 2 punkty.
Za poprawne wyniki dla pliku 2 - 3 punkty.
Za poprawne wyniki dla pliku 3 - 4 punkty.
9
Zadanie 21. Podzielność (0-10) - rozwiązanie
Pliki z danymi, plik programu źródłowego oraz plik podzielnosc.txt zawierający
odpowiedzi znajdują się w folderze PODZIELNOSC.
Komentarz
Jedna z metod rozwiązania tego zadania mogła by polegać na przytoczeniu i wykorzystaniu
własności podzielności liczb binarnych. O ile własność podzielności przez 2 jest oczywista
i powszechnie znana - najmniej znaczącą cyfrą takiej liczby musi być 0 - to już własności
podzielności liczby binarnych przez inne liczby nie są tak naturalne i znane. Dla każdego
dzielnika taka własność byłaby pewnie inna i prowadziłaby do algorytmu właściwego tylko
dla tej własności. Przedstawimy algorytm, który jest jednakowy dla wszystkich dzielników
z dokładnością do parametru, którym jest właśnie dzielnik.
Jest naturalne rozwiązanie, które pozwala stwierdzić, czy dana, dodatnia liczba binarna b,
jest podzielna całkowicie przez dodatnią (dziesiętną) liczbę całkowitą p. Wystarczy obliczyć
(dziesiętną) wartość d liczby b i sprawdzić, czy p dzieli całkowicie d. W tym celu
wykorzystujemy dostępny w większości języków programowania operator mod obliczania
reszty z dzielenia liczb całkowitych i sprawdzamy, czy d mod p = 0. Do zamiany liczby
binarnej b na jej odpowiednik dziesiętny d można zastosować schemat Hornera. Prawda
jakie to proste? Jest tylko jeden mały problem. W kolejnych plikach z danymi są coraz
większe liczby. W pliku liczby1.txt długość zapisu każdej z liczb jest nie większa niż 12
i do zapisu każdej takiej liczby wystarczają dwa bajty, do zapisu jednej liczby z pliku
liczby2.txt potrzeba już 4 bajtów, natomiast do zapisu liczby z pliku liczby3.txt
może być potrzebnych 25 bajtów na każdą z nich. Jeśli język programowania użyty do
rozwiązania pozwala reprezentować tak duże liczby i umożliwia wykonywanie na nich
podstawowych arytmetycznych - dodawanie, mnożenie i branie modulo - to powyżej opisane
rozwiązanie jest wystarczające. Często jednak języki programowania nie umożliwiają
bezpośredniego operowania na bardzo dużych liczbach. Wówczas pozostaje albo
zaprogramować własną arytmetykę dużych liczb, albo, jak w tym przypadku, skorzystać
z pewnych własności używanych operacji arytmetycznych. Tutaj skorzystamy z własności
operacji modulo brania reszty z dzielenia, które to własności pozwalają nam operować tylko
na resztach z dzielenia przez dzielnik p, a nie na całych liczbach. Każda taka reszta jest nie
większa od p. Dwie podstawowe, wykorzystywane przez nas własności są następujące:
Przykładowe zadania z rozwiązaniami 73
Dla dodatnich liczb całkowitych a, b i p mamy:
(1) (a + b) mod p =( a mod p + b mod p) mod p
(2) (a*b) mod p = ((a mod p) * (b mod p)) mod p
Tak więc do policzenia reszty z dzielenia przez p dodatniej liczby całkowitej d, której wartość
jest taka sama jak wartość liczby binarnej b, należy po prostu zastosować schemat Hornera
obliczania wartości d z zapisu b pamiętając, żeby wszystkie obliczenia wykonywać modulo p.
Oto funkcja zapisana w języku programowania C++, która dla liczby binarnej b podanej
w postaci zero-jedynkowego napisu i dodatniego, całkowitego podzielnika p, oblicza resztę
z dzielenia wartości dziesiętnej liczby b przez p.
int Reszta(string b, int p){
const char zero = '0';
int dl = b.length(); //obliczenie długości zapisu liczby b
int d = 0; // po zakończeniu obliczeń wartością d będzie
// wartość dziesiętna liczby b modulo p
// schemat Hornera modulo p
for (int j = 0; j < dl; j++){
int cyfra = b[j] - zero;//odzyskanie kolejnej cyfry liczby b
// poczynając od najbardziej znaczącej
d = (d*2 + cyfra) % p; // % jest operatorem modulo w C++
}
return d;
}
Należy zwrócić jeszcze uwagę na drobiazg, jakim jest odzyskiwanie wartości liczbowych
kolejnych cyfr zapisu liczby b. Liczba b jest zadana jako napis złożony ze znaków ‘0’ i ‘1’.
Każdy ze znaków ‘0’ lub ‘1’ do obliczeń arytmetycznych należy zamienić odpowiednio na
liczbę 0 lub 1. Do tego celu najprościej wykorzystać fakt, że cyfry ‘0’, ‘1’, …, ‘9’ są
kodowane kolejnymi liczbami naturalnymi poczynając od kodu znaku ‘0’. Tak więc, gdy od
kodu cyfry odejmiemy kod cyfry ‘0’, to otrzymamy liczbę odpowiadającą tej cyfrze.
W przedstawionym powyżej rozwiązaniu wykorzystujemy ten fakt - wartość wyrażenia b[j]

\n\n

Poniżej przedstawiamy program Podzielnosc zapisany w języku C++, który oblicza
żądane wyniki dla jednego pliku. Dla przykładu, żeby uzyskać wyniki dla pliku
liczby1.txt można program wykonywalny Podzielnosc uruchomić w katalogu
zawierającym plik liczby1.txt następującą komendą z wiersza poleceń:
Podzielnosc < liczby1.txt > wyniki1.txt
Wyniki znajdą się w pliku tekstowym wyniki1.txt w tym samym katalogu. Na koniec
trzeba pamiętać, żeby wyniki obliczeń dla wszystkich trzech plików umieścić w jednym pliku
tekstowym podzielnosc.txt zgodnie z opisem w treści zadania.
//Program Podzielnosc
#include <iostream>
using namespace std;
int Reszta(string b, int p){
const char zero = '0';
74 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
int dl = b.length(); //obliczenie długości zapisu liczby b
int d = 0; //po zakończeniu obliczeń wartością d będzie
// wartość dziesiętna liczby b modulo p
// schemat Hornera modulo p
for (int j = 0; j < dl; j++){
int cyfra = b[j] - zero; //odzyskanie kolejnej cyfry liczby
b
//poczynając od najbardziej znaczącej
d = (d*2 + cyfra) % p; //% jest operatorem modulo w C++
}
return d;
}
int main(){
string liczba;
const int n = 1000; //rozmiar danych
int podz_2 = 0, podz_3 = 0, podz_5 = 0; // podz_p - liczba
liczb
// podzielnych przez p
for (int i = 0; i < n; i++){
cin >> liczba; //wczytanie kolejnej liczby;
if (Reszta(liczba,2) == 0) podz_2++;
if (Reszta(liczba,3) == 0) podz_3++;
if (Reszta(liczba,5) == 0) podz_5++;
}
cout << "podzielne przez " << 2 << " : " << podz_2 << "\\n";
cout << "podzielne przez " << 3 << " : " << podz_3 << "\\n";
cout << "podzielne przez " << 5 << " : " << podz_5 << "\\n";
return 0;
}
Przykładowe zadania z rozwiązaniami 75

","solutions":[]}