{"id":"informator-maturalny-informatyka-2015/zad/13","paper_id":"informator-maturalny-informatyka-2015","number":"13","points":null,"ptype":"open","subject":"informatyka","category":"informator-maturalny","year":2015,"month":null,"level":null,"text":"Zadanie 13. Zapisy binarne (0-7)\nW tym zadaniu badamy zapisy binarne dodatnich liczb całkowitych. Rozważamy następujący\nalgorytm:\nSpecyfikacja\nDane: dodatnia liczba całkowita n\nWynik: dodatnia liczba całkowita j równa\n(1) j 0;\n(2) powtarzaj\n(3)\njeśli n mod 2 = 1, to\n(4)\njj+1;\n(5)\nnn div 2;\n(6) aż n = 0;\nUwaga: użyte operatory mod i div oznaczają odpowiednio resztę z dzielenia i dzielenie\ncałkowite. Na przykład 5 mod 2 = 1, 5 div 2 = 2, 6 mod 2 = 0, 6 div 2 = 3.\na) Przeanalizuj powyższy algorytm i podaj wartości zmiennej j po zakończeniu jego\ndziałania dla n = 183 oraz dla n = 1022. Uzupełnij brakujący fragment specyfikacji.\nn\nj\n183\n1022\nMiejsce na obliczenia.\nb) Ułóż algorytm i zapisz go w wybranej przez siebie notacji (lista kroków lub język\nprogramowania, który wybrałeś na egzamin), który dla danej dodatniej liczby całkowitej\nn oblicza maksymalną liczbę kolejnych jedynek pojawiających się w zapisie binarnym tej\nliczby.\nSpecyfikacja\nDane: dodatnia liczba całkowita n\nWynik: dodatnia liczba całkowita m - maksymalna liczba kolejnych jedynek w zapisie\nbinarnym n\nPrzykład: dla n = 187 wynikiem jest m = 3, ponieważ 187 = (10111011)2\nPrzykładowe zadania z rozwiązaniami 21\nAlgorytm\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:\n2) stosuje podejście algorytmiczne do rozwiązywania\nproblemu,\n4) dobiera efektywny algorytm do rozwiązania\nsytuacji problemowej i zapisuje go w wybranej\nnotacji,\n5) posługuje się podstawowymi technikami\nalgorytmicznymi,\n11) opisuje podstawowe algorytmy,\n12) projektuje rozwiązanie problemu (realizację\nalgorytmu) i dobiera odpowiednią strukturę danych.\n22 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nSchemat punktowania\nPodpunkt\nCzynność\nLiczba\npunktów\nza\npodpunkt\nLiczba\npunktów\nza\nzadanie\na\nZa każdą poprawną odpowiedź - 1 punkt.\n3\n7\nb\nZa poprawny algorytm - 4 punkty.\nW przypadku niepoprawnego algorytmu:\n za prawidłowe wyznaczanie maksimum długości\nbloków jedynek - 1 punkt.\n za prawidłowe wyznaczanie długości bloków\njedynek - 1 punkt.\n4\nZadanie 13. Zapisy binarne (0-7) - rozwiązanie\nW tym zadaniu badamy zapisy binarne dodatnich liczb całkowitych. Rozważamy następujący\nalgorytm:\nSpecyfikacja\nDane: dodatnia liczba całkowita n\nWynik: dodatnia liczba całkowita j równa liczbie jedynek w zapisie binarnym liczby n\n(1) j 0;\n(2) powtarzaj\n(3)\njeśli n mod 2 = 1, to\n(4)\njj+1;\n(5)\nn :n div 2;\n(6) aż n = 0;\nUwaga: użyte operatory mod i div oznaczają odpowiednio resztę z dzielenia i dzielenie\ncałkowite, np. 5 mod 2 = 1, 5 div 2 = 2, 6 mod 2 = 0, 6 div 2 = 3.\na) Przeanalizuj powyższy algorytm i podaj wartości zmiennej j po zakończeniu jego\ndziałania dla n = 183 oraz dla n = 1022. Uzupełnij brakujący fragment specyfikacji.\nn\nj\n183\n6\n1022\n9\nMiejsce na obliczenia.\n183 = (10110111)2\n1022 = (1111111110)2\nPrzykładowe zadania z rozwiązaniami 23\nb) Ułóż algorytm i zapisz go w wybranej przez siebie notacji (lista kroków lub język\nprogramowania, który wybrałeś na egzamin), który dla danej dodatniej liczby całkowitej\nn oblicza maksymalną liczbę kolejnych jedynek pojawiających się w zapisie binarnym tej\nliczby.\nSpecyfikacja\nDane: dodatnia liczba całkowita n\nWynik: dodatnia liczba całkowita m - maksymalna liczba kolejnych jedynek w zapisie\nbinarnym n\nPrzykład: dla n = 187 wynikiem jest m = 3, ponieważ 187 = (10111011)2\nAlgorytm\nKażdy ciąg kolejnych jedynek w zapisie binarnym liczby, który nie można już wydłużyć,\nnazywamy blokiem. W zapisie binarnym liczby 187 mamy trzy bloki jedynek o długościach\njeden, trzy i dwa: (10111011)2. Naszym celem jest policzenie długości najdłuższego bloku.\nModyfikujemy algorytm z podpunktu a), wyznaczając kolejne cyfry liczby n, od cyfr najmniej\nznaczących do cyfr najbardziej znaczących. W momencie wykrycia bloku (pierwszej jedynki\nw tym bloku) rozpoczynamy zliczanie jedynek w nim zawartych, aż w zapisie binarnym\nnapotkamy zero lub wyznaczymy już wszystkie cyfry zapisu. Po przetworzeniu bloku\nporównujemy jego długość z długością dotychczas najdłuższego bloku i jeśli policzona\ndługość jest większa od dotychczas największej, aktualizujemy informację o długości\nnajdłuższego bloku.\nOto zapis opisanego słowami algorytmu:\n(1) m  0;\n(2) powtarzaj\n// m - długość dotychczas najdłuższego bloku\n(3)\njeśli n mod 2 = 1, to\n// nowy blok\n(4)\ndl_bloku 0; // tu zliczamy liczbę jedynek w bloku\n(5)\npowtarzaj\n(6)\ndl_blokudl_bloku + 1;\n(7)\nn n div 2;\n(8)\naż n mod 2 = 0;\n(9)\njeśli dl_bloku >m, to\n(10)\nm dl_bloku;\n(11)\nnn div 2;\n(12) aż n = 0;\nKomentarz\nPodpunkt a) w tym zadaniu nie powinien sprawić żadnych trudności. Przedstawiony w nim\nalgorytm jest typowym szkolnym algorytmem wyznaczania kolejnych cyfr dodatniej liczby\ncałkowitej w jej zapisie binarnym, poczynając od cyfry najmniej znaczącej, a kończąc na\ncyfrze najbardziej znaczącej. Warto zauważyć, że w ten sam sposób można wyznaczyć cyfry\nw zapisie pozycyjnym przy dowolnej podstawie p, 2 ≤ p ≤ 10. Wystarczy wykonywać\n24 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\noperacje dzielenia całkowitego i brania reszty z dzielenia z parametrem p zamiast 2. Dla\nliczby naturalnej n, n mod p jest najmniej znaczącą cyfrą w zapisie pozycyjnym liczby n przy\npodstawie p. Dla przykładu 187 mod 10 = 7, 187 mod 2 = 1. Jeśli najmniej znaczącą cyfrą\nw zapisie przy podstawie p liczby n jest cyfra c, to n = n’•p + c, dla pewnej liczby naturalnej\nn’. Wówczas n div p = n’ i kolejna cyfrą w zapisie n jest najmniej znacząca cyfra w zapisie\nn’. Te własności właśnie wykorzystano w algorytmie z podpunktu a).\nW punkcie b), oprócz wyznaczania cyfr liczby n, należy zliczać jedynki w blokach kolejnych\njedynek. Tutaj najpierw trzeba wykryć blok. To jest proste - blok rozpoczyna się od jedynki.\nNastępnie należy zliczać w pętli kolejne napotkane jedynki, aż pojawi się zero. Tak\nnaprawdę w tym celu wykorzystujemy pętlę z algorytmu w punkcie a). Tak więc cały\nalgorytm składa się z dwóch zagnieżdżonych pętli, których struktury są podobne do pętli\nz punktu a).\nMożna sobie wyobrazić inne rozwiązanie. W tym nowym rozwiązaniu zliczamy jedynki za\nkażdym razem od momentu pojawienia się pierwszej jedynki w bloku. Pojawienie się zera\npowoduje wyzerowanie licznika jedynek. Oto formalny zapis tego algorytmu:\n(1) m  0;\n(2) dl_bloku 0;\n(3) dopóki n ≠ 0 wykonuj\n(4)\njeśli n mod 2 = 1 to\n(5)\ndl_blokudl_bloku + 1;\n(6) w przeciwnym wypadku\n(7)\njeśli dl_bloku >m to\n(8)\nm := dl_bloku;\n(9)\ndl_bloku 0;\n(10)\nn n div 2;\nPrzykładowe zadania z rozwiązaniami 25","answer":null,"answer_text":null,"solution":null,"image":"img/informator-maturalny-informatyka-2015/zad-13.webp","solution_image":null,"topics":null,"page_from":20,"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 13. Zapisy binarne (0-7)
W tym zadaniu badamy zapisy binarne dodatnich liczb całkowitych. Rozważamy następujący
algorytm:
Specyfikacja
Dane: dodatnia liczba całkowita n
Wynik: dodatnia liczba całkowita j równa
(1) j 0;
(2) powtarzaj
(3)
jeśli n mod 2 = 1, to
(4)
jj+1;
(5)
nn div 2;
(6) aż n = 0;
Uwaga: użyte operatory mod i div oznaczają odpowiednio resztę z dzielenia i dzielenie
całkowite. Na przykład 5 mod 2 = 1, 5 div 2 = 2, 6 mod 2 = 0, 6 div 2 = 3.
a) Przeanalizuj powyższy algorytm i podaj wartości zmiennej j po zakończeniu jego
działania dla n = 183 oraz dla n = 1022. Uzupełnij brakujący fragment specyfikacji.
n
j
183
1022
Miejsce na obliczenia.
b) Ułóż algorytm i zapisz go w wybranej przez siebie notacji (lista kroków lub język
programowania, który wybrałeś na egzamin), który dla danej dodatniej liczby całkowitej
n oblicza maksymalną liczbę kolejnych jedynek pojawiających się w zapisie binarnym tej
liczby.
Specyfikacja
Dane: dodatnia liczba całkowita n
Wynik: dodatnia liczba całkowita m - maksymalna liczba kolejnych jedynek w zapisie
binarnym n
Przykład: dla n = 187 wynikiem jest m = 3, ponieważ 187 = (10111011)2
Przykładowe zadania z rozwiązaniami 21
Algorytm
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. stosuje podejście algorytmiczne do rozwiązywania
\n

problemu,

\n
  1. dobiera efektywny algorytm do rozwiązania
\n

sytuacji problemowej i zapisuje go w wybranej
notacji,

\n
  1. posługuje się podstawowymi technikami
\n

algorytmicznymi,

\n
  1. opisuje podstawowe algorytmy,
  2. projektuje rozwiązanie problemu (realizację
\n

algorytmu) i dobiera odpowiednią strukturę danych.
22 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
Schemat punktowania
Podpunkt
Czynność
Liczba
punktów
za
podpunkt
Liczba
punktów
za
zadanie
a
Za każdą poprawną odpowiedź - 1 punkt.
3
7
b
Za poprawny algorytm - 4 punkty.
W przypadku niepoprawnego algorytmu:
 za prawidłowe wyznaczanie maksimum długości
bloków jedynek - 1 punkt.
 za prawidłowe wyznaczanie długości bloków
jedynek - 1 punkt.
4
Zadanie 13. Zapisy binarne (0-7) - rozwiązanie
W tym zadaniu badamy zapisy binarne dodatnich liczb całkowitych. Rozważamy następujący
algorytm:
Specyfikacja
Dane: dodatnia liczba całkowita n
Wynik: dodatnia liczba całkowita j równa liczbie jedynek w zapisie binarnym liczby n
(1) j 0;
(2) powtarzaj
(3)
jeśli n mod 2 = 1, to
(4)
jj+1;
(5)
n :n div 2;
(6) aż n = 0;
Uwaga: użyte operatory mod i div oznaczają odpowiednio resztę z dzielenia i dzielenie
całkowite, np. 5 mod 2 = 1, 5 div 2 = 2, 6 mod 2 = 0, 6 div 2 = 3.
a) Przeanalizuj powyższy algorytm i podaj wartości zmiennej j po zakończeniu jego
działania dla n = 183 oraz dla n = 1022. Uzupełnij brakujący fragment specyfikacji.
n
j
183
6
1022
9
Miejsce na obliczenia.
183 = (10110111)2
1022 = (1111111110)2
Przykładowe zadania z rozwiązaniami 23
b) Ułóż algorytm i zapisz go w wybranej przez siebie notacji (lista kroków lub język
programowania, który wybrałeś na egzamin), który dla danej dodatniej liczby całkowitej
n oblicza maksymalną liczbę kolejnych jedynek pojawiających się w zapisie binarnym tej
liczby.
Specyfikacja
Dane: dodatnia liczba całkowita n
Wynik: dodatnia liczba całkowita m - maksymalna liczba kolejnych jedynek w zapisie
binarnym n
Przykład: dla n = 187 wynikiem jest m = 3, ponieważ 187 = (10111011)2
Algorytm
Każdy ciąg kolejnych jedynek w zapisie binarnym liczby, który nie można już wydłużyć,
nazywamy blokiem. W zapisie binarnym liczby 187 mamy trzy bloki jedynek o długościach
jeden, trzy i dwa: (10111011)2. Naszym celem jest policzenie długości najdłuższego bloku.
Modyfikujemy algorytm z podpunktu a), wyznaczając kolejne cyfry liczby n, od cyfr najmniej
znaczących do cyfr najbardziej znaczących. W momencie wykrycia bloku (pierwszej jedynki
w tym bloku) rozpoczynamy zliczanie jedynek w nim zawartych, aż w zapisie binarnym
napotkamy zero lub wyznaczymy już wszystkie cyfry zapisu. Po przetworzeniu bloku
porównujemy jego długość z długością dotychczas najdłuższego bloku i jeśli policzona
długość jest większa od dotychczas największej, aktualizujemy informację o długości
najdłuższego bloku.
Oto zapis opisanego słowami algorytmu:
(1) m  0;
(2) powtarzaj
// m - długość dotychczas najdłuższego bloku
(3)
jeśli n mod 2 = 1, to
// nowy blok
(4)
dl_bloku 0; // tu zliczamy liczbę jedynek w bloku
(5)
powtarzaj
(6)
dl_blokudl_bloku + 1;
(7)
n n div 2;
(8)
aż n mod 2 = 0;
(9)
jeśli dl_bloku >m, to
(10)
m dl_bloku;
(11)
nn div 2;
(12) aż n = 0;
Komentarz
Podpunkt a) w tym zadaniu nie powinien sprawić żadnych trudności. Przedstawiony w nim
algorytm jest typowym szkolnym algorytmem wyznaczania kolejnych cyfr dodatniej liczby
całkowitej w jej zapisie binarnym, poczynając od cyfry najmniej znaczącej, a kończąc na
cyfrze najbardziej znaczącej. Warto zauważyć, że w ten sam sposób można wyznaczyć cyfry
w zapisie pozycyjnym przy dowolnej podstawie p, 2 ≤ p ≤ 10. Wystarczy wykonywać
24 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
operacje dzielenia całkowitego i brania reszty z dzielenia z parametrem p zamiast 2. Dla
liczby naturalnej n, n mod p jest najmniej znaczącą cyfrą w zapisie pozycyjnym liczby n przy
podstawie p. Dla przykładu 187 mod 10 = 7, 187 mod 2 = 1. Jeśli najmniej znaczącą cyfrą
w zapisie przy podstawie p liczby n jest cyfra c, to n = n’•p + c, dla pewnej liczby naturalnej
n’. Wówczas n div p = n’ i kolejna cyfrą w zapisie n jest najmniej znacząca cyfra w zapisie
n’. Te własności właśnie wykorzystano w algorytmie z podpunktu a).
W punkcie b), oprócz wyznaczania cyfr liczby n, należy zliczać jedynki w blokach kolejnych
jedynek. Tutaj najpierw trzeba wykryć blok. To jest proste - blok rozpoczyna się od jedynki.
Następnie należy zliczać w pętli kolejne napotkane jedynki, aż pojawi się zero. Tak
naprawdę w tym celu wykorzystujemy pętlę z algorytmu w punkcie a). Tak więc cały
algorytm składa się z dwóch zagnieżdżonych pętli, których struktury są podobne do pętli
z punktu a).
Można sobie wyobrazić inne rozwiązanie. W tym nowym rozwiązaniu zliczamy jedynki za
każdym razem od momentu pojawienia się pierwszej jedynki w bloku. Pojawienie się zera
powoduje wyzerowanie licznika jedynek. Oto formalny zapis tego algorytmu:
(1) m  0;
(2) dl_bloku 0;
(3) dopóki n ≠ 0 wykonuj
(4)
jeśli n mod 2 = 1 to
(5)
dl_blokudl_bloku + 1;
(6) w przeciwnym wypadku
(7)
jeśli dl_bloku >m to
(8)
m := dl_bloku;
(9)
dl_bloku 0;
(10)
n n div 2;
Przykładowe zadania z rozwiązaniami 25

","solutions":[]}