{"id":"informatyka-2010-maj-matura-rozszerzona/zad/2","paper_id":"informatyka-2010-maj-matura-rozszerzona","number":"2","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2010,"month":"maj","level":"rozszerzona","text":"Zadanie 2. Tablica zero-jedynkowa (8 pkt)\nW tablicy a[1…1023] zapisano ciąg zer i jedynek w taki sposób, że wszystkie zera\npoprzedzają jedynki.\nUwaga: W tablicy mogą być same zera lub same jedynki.\nOto niepełny algorytm obliczania liczby zer w tablicy a:\n← - oznacza instrukcję przypisania\ndiv - oznacza dzielenie całkowite\nliczba_zer ← 0\nl ← 1, p ← 1023\ndopóki l\np\n≤\nwykonuj\n(\n)\n2\ns\nl\np div\n←\njeśli [ ]\n1\na s = to\n1\np\ns\n←\nw przeciwnym przypadku\nliczba_zer ← liczba_zer +\nl ←\na) Uzupełnij opis algorytmu, wstawiając w miejsce kropek stosowne wyrażenie, tak aby\nobliczał on zawsze poprawnie liczbę zer z tablicy a.\nb) Ile instrukcji przypisania\n(\n)\n2\ns\nl\np div\n←\njest wykonywanych w każdym przebiegu\nalgorytmu? Odpowiedź uzasadnij.\nNr zadania\n2a)\n2b)\nMaks. liczba pkt\n4\n4\nWypełnia\negzaminator\nUzyskana liczba pkt\nPoziom rozszerzony - część I\n6","answer":"2a) pierwsza luka: s-l+1, druga luka: s+1; 2b) 10 (⌈log2 1023⌉), bo to wyszukiwanie binarne","answer_text":null,"solution":"Oficjalna odpowiedź CKE (Klucz punktowania odpowiedzi, poziom rozszerzony, maj 2010):\n\nZadanie 2. Tablica zero-jedynkowa (8 pkt) — a), b):\n\nAlgorytm (wyszukiwanie binarne granicy między zerami a jedynkami w a[1..1023]):\nliczba_zer ← 0\nl ← 1, p ← 1023\ndopóki l ≤ p wykonuj\ns ← (l + p) div 2\njeśli a[s] = 1 to\np ← s - 1\nw przeciwnym przypadku\nliczba_zer ← liczba_zer + (s - l + 1)\nl ← s + 1\n\na) (4 pkt) Uzupełnienie luk:\npierwsza luka (przy \"liczba_zer ← liczba_zer + …\"): s - l + 1\ndruga luka (przy \"l ← …\"): s + 1\n\nb) (4 pkt) Liczba wykonań instrukcji przypisania s ← (l+p) div 2 w każdym przebiegu algorytmu:\n⌈log2 1024⌉ = ⌈log2 1023⌉ = 10 (dokładnie 10 wykonań).\nUzasadnienie: to wyszukiwanie binarne — w każdym kroku pętli zakres tablicy pozostały do\nsprawdzenia zmniejsza się o połowę, więc liczba kroków potrzebnych do przeszukania tablicy\no 1023 elementach wynosi ⌈log2 1023⌉ = 10.","image":"img/informatyka-2010-maj-matura-rozszerzona/zad-2.webp","solution_image":null,"topics":null,"page_from":5,"source":"ai","answer_source":"ai","answer_text_source":null,"solution_source":"ai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2010 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"<p>Zadanie 2. Tablica zero-jedynkowa (8 pkt)<br>W tablicy a[1…1023] zapisano ciąg zer i jedynek w taki sposób, że wszystkie zera<br>poprzedzają jedynki.<br>Uwaga: W tablicy mogą być same zera lub same jedynki.<br>Oto niepełny algorytm obliczania liczby zer w tablicy a:<br>← - oznacza instrukcję przypisania<br>div - oznacza dzielenie całkowite<br>liczba_zer ← 0<br>l ← 1, p ← 1023<br>dopóki l<br>p<br>≤<br>wykonuj<br>(<br>)<br>2<br>s<br>l<br>p div<br>←<br>jeśli [ ]<br>1<br>a s = to<br>1<br>p<br>s<br>←<br>w przeciwnym przypadku<br>liczba_zer ← liczba_zer +<br>l ←<br>a) Uzupełnij opis algorytmu, wstawiając w miejsce kropek stosowne wyrażenie, tak aby<br>obliczał on zawsze poprawnie liczbę zer z tablicy a.<br>b) Ile instrukcji przypisania<br>(<br>)<br>2<br>s<br>l<br>p div<br>←<br>jest wykonywanych w każdym przebiegu<br>algorytmu? Odpowiedź uzasadnij.<br>Nr zadania<br>2a)<br>2b)<br>Maks. liczba pkt<br>4<br>4<br>Wypełnia<br>egzaminator<br>Uzyskana liczba pkt<br>Poziom rozszerzony - część I<br>6</p>","solutions":[{"source":"ai","label":"AI","kind":"text","html":"<p>Oficjalna odpowiedź CKE (Klucz punktowania odpowiedzi, poziom rozszerzony, maj 2010):</p>\n<p>Zadanie 2. Tablica zero-jedynkowa (8 pkt) — a), b):</p>\n<p>Algorytm (wyszukiwanie binarne granicy między zerami a jedynkami w a[1..1023]):<br>liczba_zer ← 0<br>l ← 1, p ← 1023<br>dopóki l ≤ p wykonuj<br>s ← (l + p) div 2<br>jeśli a[s] = 1 to<br>p ← s - 1<br>w przeciwnym przypadku<br>liczba_zer ← liczba_zer + (s - l + 1)<br>l ← s + 1</p>\n<p>a) (4 pkt) Uzupełnienie luk:<br>pierwsza luka (przy &quot;liczba_zer ← liczba_zer + …&quot;): s - l + 1<br>druga luka (przy &quot;l ← …&quot;): s + 1</p>\n<p>b) (4 pkt) Liczba wykonań instrukcji przypisania s ← (l+p) div 2 w każdym przebiegu algorytmu:<br>⌈log2 1024⌉ = ⌈log2 1023⌉ = 10 (dokładnie 10 wykonań).<br>Uzasadnienie: to wyszukiwanie binarne — w każdym kroku pętli zakres tablicy pozostały do<br>sprawdzenia zmniejsza się o połowę, więc liczba kroków potrzebnych do przeszukania tablicy<br>o 1023 elementach wynosi ⌈log2 1023⌉ = 10.</p>"}]}