{"id":"informator-maturalny-informatyka-2015/zad/16","paper_id":"informator-maturalny-informatyka-2015","number":"16","points":null,"ptype":"open","subject":"informatyka","category":"informator-maturalny","year":2015,"month":null,"level":null,"text":"Zadanie 16. Miejsce zerowe (0-6)\nPrzedstawiona poniżej rekurencyjna funkcja Mzer znajduje metodą bisekcji miejsce zerowe\nfunkcji f , ciągłej w przedziale\n,a b , z dokładnością do 2\n [epsilon].\nSpecyfikacja\nDane: liczby a i b takie, że a\nb\n\noraz\n\n\n0\nf a\nf b\n\n\nliczba\n0\n\nWynik: liczba rzeczywista x z przedziału\n,a b taka, że \n\n0\nf x \n\n\ndla pewnego  takiego,\nże\n2\n2\n\n\n\n\n\n\nFunkcja\n\n\n, ,\nMzer a b \n1. jeżelib\na\n\n\n\n, to wykonaj:\na.\n\n/ 2\ns\na b\n\n\nb. jeżeli\n\n0\nf s \n, to podaj s jako wynik\nc. jeżeli\n\n\n0\nf a\nf s\n\n\n, to podaj\n\n\n, ,\nMzer a s  jako wynik\nw przeciwnym przypadku podaj\n\n\n, ,\nMzer s b  jako wynik\n2. w przeciwnym przypadku podaj \n/ 2\na\nb\n\njako wynik\na)\nPoniżej prezentujemy fragment wykresu funkcji f , dla której wywołujemy funkcję Mzer:\nWykres funkcji f w przedziale <0,128>\n-40\n-20\n0\n20\n40\n60\n80\n100\n0\n5\n10\n15\n20\n25\n30\n35\n40\n45\n50\n55\n60\n65\n70\n75\n80\n85\n90\n95 100 105 110 115 120 125\nPrzykładowe zadania z rozwiązaniami 37\nWykres przecina oś OX w punkcie 72,7. Załóżmy, że funkcja Mzer została wywołana\ndla\n0\na \ni\n128\nb \n. W poniższej tabelce podaj liczbę kolejnych rekurencyjnych wywołań\nfunkcji Mzer przy podanych poniżej początkowych wartościach .\n\nliczba wywołań Mzer\n10\n4\n32\n25\n5\n1\n5\nMiejsce na obliczenia\nb) Poniżej\nprezentujemy\nzapis\nalgorytmu\nopisanego\nfunkcją\nMzer\nw\npostaci\nnierekurencyjnej. Zapis poniższego algorytmu jest niepełny, uzupełnij brakujące\nelementy tak, aby realizował tę samą metodę poszukiwania miejsca zerowego, którą\nopisuje funkcja Mzer.\nAlgorytm:\n1. dopóki b\na\n\n\n\nwykonuj\na)\ns \nb) jeżeli\n\n0\nf s \n, to podaj s jako wynik i zakończ wykonywanie algorytmu\nc) jeżeli\n\n\n0\nf a\nf s\n\n\n, to\nb \nw przeciwnym przypadku\n2. podaj \n/ 2\na\nb\n\njako wynik\n38 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\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,\n5) posługuje się podstawowymi technikami\nalgorytmicznymi,\n9) stosuje rekurencję w prostych sytuacjach\nproblemowych,\n11) opisuje podstawowe algorytmy.\nSchemat punktowania\nPodpunkt\nCzynność\nLiczba\npunktów\nza\npodpunkt\nLiczba\npunktów\nza\nzadanie\na\nZa wszystkie poprawne odpowiedzi - 3 punkty.\nZa trzy poprawne odpowiedzi - 2 punkty.\nZa dwie poprawne odpowiedzi - 1 punkt.\n3\n6\nb\nZa każde poprawne uzupełnienie brakującego\nelementu - 1 punkt.\n3\nZadanie 16. Miejsce zerowe (0-6) - rozwiązanie\nPrzedstawiona poniżej rekurencyjna funkcja Mzer znajduje metodą bisekcji miejsce zerowe\nfunkcji f ciągłejw przedziale\n,a b z dokładnością do 2\n [epsilon].\nSpecyfikacja:\nDane: liczby a i b takie, że a\nb\n\noraz\n\n\n0\nf a\nf b\n\n\nliczba\n0\n\nWynik: liczba rzeczywista x z przedziału\n,a b taka, że \n\n0\nf x \n\n\ndla pewnego \ntakiego, że\n2\n2\n\n\n\n\n\n\nFunkcja\n\n\n, ,\nMzer a b \n1. jeżelib\na\n\n\n\n, to wykonaj:\na.\n2\na\nb\ns\n\n\nb. jeżeli\n\n0\nf s \n, to podaj s jako wynik\nc. jeżeli\n\n\n0\nf a\nf s\n\n\n, topodaj\n\n\n, ,\nMzer a s  jako wynik\nw przeciwnym przypadku podaj\n\n\n, ,\nMzer s b  jako wynik\nPrzykładowe zadania z rozwiązaniami 39\n2. w przeciwnym przypadku podaj \n/ 2\na\nb\n\njako wynik\n)\nPoniżej prezentujemy fragment wykresu funkcji f , dla której wywołujemyfunkcję Mzer:\nWykres przecina oś OX w punkcie 72,7. Załóżmy, że funkcja Mzer została wywołana\ndla\n0\na \ni\n128\nb \n. W poniższej tabelce podaj liczbę kolejnych rekurencyjnych wywołań\nfunkcji Mzerprzy podanych poniżej wartościach \n\nliczba wywołań Mzer\n10\n4\n32\n2\n25\n3\n5\n5\n1\n5\n10\nb) Poniżej prezentujemy zapis algorytmu opisanego funkcją Mzer w postaci\nnierekurencyjnej. Zapis poniższego algorytmu jest niepełny, uzupełnij brakujące\nelementy tak, aby realizował tę samą metodę poszukiwania miejsca zerowego, którą\nopisuje funkcja Mzer.\nAlgorytm\n1. dopóki b\na\n\n\n\nwykonuj\na)\n2\na\nb\ns\n\n\nb) jeżeli\n\n0\nf s \n, to podaj s jako wynik i zakończ wykonywanie algorytmu\nWykres funkcji f w przedziale <0,128>\n-40\n-20\n0\n20\n40\n60\n80\n100\n0\n5\n10\n15\n20\n25\n30\n35 40\n45\n50 55\n60\n65\n70 75\n80\n85\n90\n95 100 105 110 115 120 125\n40 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nc) jeżeli\n\n\n0\nf a\nf s\n\n\n, to b\ns\n\nw przeciwnym przypadku a\ns\n\n2. podaj \n/ 2\na\nb\n\njako wynik\nKomentarz\nPodpunkt a\nAby obliczyć liczbę kolejnych rekurencyjnych wywołań funkcji Mzer dla każdej podanej\nwartości , należy ustalić wartości zmiennych z jakimi będzie ona wywoływana w kolejnych\nkrokach. Funkcja zakończy działanie w momencie, gdy b\na\n\n\n\nDla każdej dokładności startujemy od wywołania funkcji\n\n\n0,128,\nMzer\n, zaś kolejne\nwywołania to:\nDla\n32\n\nmamy dwa wywołania:\n\n\n64,128,32\nMzer\n\n\n64,96,32\nMzer\nDla\n25\n\nmamy trzy wywołania:\n\n\n64,128,25\nMzer\n\n\n64,96,25\nMzer\n\n\n64,80,25\nMzer\nDla\n5\n\nmamy pięć wywołań:\n\n\n64,128,5\nMzer\n\n\n64,96,5\nMzer\n\n\n64,80,5\nMzer\n\n\n72,80,5\nMzer\n\n\n72,76,5\nMzer\nDla\n1\n5\n\nmamy dziesięć wywołań:\n1\n64,128, 5\nMzer \n\n\n\n\n\n1\n64,96, 5\nMzer \n\n\n\n\n\n1\n64,80, 5\nMzer \n\n\n\n\n\n1\n72,80, 5\nMzer \n\n\n\n\n\n1\n72,76, 5\nMzer \n\n\n\n\n\n1\n72,74, 5\nMzer \n\n\n\n\n\nPrzykładowe zadania z rozwiązaniami 41\n1\n72,73, 5\nMzer \n\n\n\n\n\n1\n72,5;73; 5\nMzer \n\n\n\n\n\n1\n72,5;72,75; 5\nMzer \n\n\n\n\n\n1\n72,625;72,75; 5\nMzer \n\n\n\n\n\nPodpunkt b\nAby uzupełnić luki w przedstawionej nierekurencyjnej wersji funkcji Mzer, należy zauważyć\nprostą własność: w kolejnych krokach zawsze ustalamy środek aktualnego przedziału, tzn.\n2\na\nb\ns\n\n\n, a następnie sprawdzamy czy miejsce zerowe funkcji leży na lewo od punktu s\n(wtedy b\ns\n\n), czy na prawo od punktu s(as).\nPodpunkt a) sprowadza się do przeanalizowania algorytmu zaprezentowanego w treści\nzadania na konkretnych danych i wyznaczenia liczby wywołań funkcji rekurencyjnej. Funkcja\nMzer opisuje podręcznikowy algorytm znajdowania miejsca zerowego funkcji ciągłej f\nmetodą bisekcji. Zadaniem zaprezentowanej implementacji tego algorytmu jest podanie\nmiejsca zerowego funkcji w przedziale \n\n,a b , z dokładnością do 2\n przy założeniu, że\n\n\n0\nf a\nf b\n\n\n(zauważmy, że ciągłość funkcji f w powiązaniu z warunkiem\n\n\n0\nf a\nf b\n\n\ngwarantuje, że f ma miejsce zerowe w przedziale \n\n,a b ).\nW treści zadania przedstawiono pseudokod rekurencyjnej wersji algorytmu, która\nrozpoczyna się od sprawdzenia czy odległość między krańcami przedziału [a,b] jest większa\nod  (czyli podwojonej dokładności wyniku):\n1. Gdy b - a , wówczas mamy gwarancję że środek przedziału \n\n,a b znajduje się nie dalej\nniż 2\n od miejsca zerowego funkcji f. Dlatego też jako wynik zwracany jest właśnie\nśrodek przedziału, czyli wartość (a+b)/2.\n2. Gdy b - a  , mamy dwie możliwości. Jeśli środek przedziału \n\n,a b jest miejscem\nzerowym funkcji f, zwracamy go oczywiście jako wartość. W przeciwnym razie\nredukujemy zadanie wyszukania miejsca zerowego w \n\n,a b do zadania poszukiwania\nmiejsca zerowego w [a,s] lub [s,b], gdzie s to środek przedziału \n\n,a b . Efektem redukcji\njest więc dwukrotne zmniejszenie długości przedziału, w którym poszukujemy miejsca\nzerowego.\nZauważmy, że gdyby wywołania funkcji Mzer dla a=0 i b=128 oraz podanych w punkcie a)\nwartości  nigdy nie kończyły się znalezieniem dokładnej wartości miejsca zerowego (czyli\nspełnieniem warunku f(s)=0), odpowiedzi w punkcie a) sprowadzałyby się do wskazania\nilokrotnie trzeba „połowić” przedział o długości 128 aby uzyskać przedział o długości nie\nwiększej niż . W rozwiązaniu można by więc ograniczyć się do policzenia, ile takich\n„połowień” należy wykonać. Aby jednak mieć pewność poprawności rozwiązania, trzeba\nsprawdzić że wartość środka przedziału s rzeczywiście w naszym przykładzie nie „trafi”\nidealnie w miejsce zerowe (równe 72,7) w kolejnych wywołaniach rekurencyjnych. Taką\nskrupulatną analizę przedstawiliśmy omawiając rozwiązanie punktu a).\n42 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nPunkt b) zadania wymaga zastosowania standardowej techniki zamiany rekurencji na\niterację. Zamiast wywoływać funkcję z nowymi wartościami krańców przedziałów,\nzmieniamy w pętli wartości zmiennych a i b tak, aby odpowiadały one końcom coraz\nmniejszych przedziałów dla których wywoływana jest funkcja rekurencyjna Mzer.\nPrzedstawiony szkielet algorytmu z pozostawionymi miejscami do uzupełnienia sugeruje\nsposób, w jaki w tym przypadku należy dokonać zamiany rekurencji na iterację.\nPrzykładowe zadania z rozwiązaniami 43","answer":null,"answer_text":null,"solution":null,"image":"img/informator-maturalny-informatyka-2015/zad-16.webp","solution_image":null,"topics":null,"page_from":36,"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 16. Miejsce zerowe (0-6)
Przedstawiona poniżej rekurencyjna funkcja Mzer znajduje metodą bisekcji miejsce zerowe
funkcji f , ciągłej w przedziale
,a b , z dokładnością do 2
 [epsilon].
Specyfikacja
Dane: liczby a i b takie, że a
b

oraz


0
f a
f b


liczba
0

Wynik: liczba rzeczywista x z przedziału
,a b taka, że 

0
f x 


dla pewnego  takiego,
że
2
2






Funkcja


, ,
Mzer a b 

\n
  1. jeżelib
\n

a



, to wykonaj:
a.

/ 2
s
a b


b. jeżeli

0
f s 
, to podaj s jako wynik
c. jeżeli


0
f a
f s


, to podaj


, ,
Mzer a s  jako wynik
w przeciwnym przypadku podaj


, ,
Mzer s b  jako wynik

\n
  1. w przeciwnym przypadku podaj 
\n

/ 2
a
b

jako wynik
a)
Poniżej prezentujemy fragment wykresu funkcji f , dla której wywołujemy funkcję Mzer:
Wykres funkcji f w przedziale <0,128>
-40
-20
0
20
40
60
80
100
0
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95 100 105 110 115 120 125
Przykładowe zadania z rozwiązaniami 37
Wykres przecina oś OX w punkcie 72,7. Załóżmy, że funkcja Mzer została wywołana
dla
0
a 
i
128
b 
. W poniższej tabelce podaj liczbę kolejnych rekurencyjnych wywołań
funkcji Mzer przy podanych poniżej początkowych wartościach .

liczba wywołań Mzer
10
4
32
25
5
1
5
Miejsce na obliczenia
b) Poniżej
prezentujemy
zapis
algorytmu
opisanego
funkcją
Mzer
w
postaci
nierekurencyjnej. Zapis poniższego algorytmu jest niepełny, uzupełnij brakujące
elementy tak, aby realizował tę samą metodę poszukiwania miejsca zerowego, którą
opisuje funkcja Mzer.
Algorytm:

\n
  1. dopóki b
\n

a



wykonuj
a)
s 
b) jeżeli

0
f s 
, to podaj s jako wynik i zakończ wykonywanie algorytmu
c) jeżeli


0
f a
f s


, to
b 
w przeciwnym przypadku

\n
  1. podaj 
\n

/ 2
a
b

jako wynik
38 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
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. posługuje się podstawowymi technikami
\n

algorytmicznymi,

\n
  1. stosuje rekurencję w prostych sytuacjach
\n

problemowych,

\n
  1. opisuje podstawowe algorytmy.
\n

Schemat punktowania
Podpunkt
Czynność
Liczba
punktów
za
podpunkt
Liczba
punktów
za
zadanie
a
Za wszystkie poprawne odpowiedzi - 3 punkty.
Za trzy poprawne odpowiedzi - 2 punkty.
Za dwie poprawne odpowiedzi - 1 punkt.
3
6
b
Za każde poprawne uzupełnienie brakującego
elementu - 1 punkt.
3
Zadanie 16. Miejsce zerowe (0-6) - rozwiązanie
Przedstawiona poniżej rekurencyjna funkcja Mzer znajduje metodą bisekcji miejsce zerowe
funkcji f ciągłejw przedziale
,a b z dokładnością do 2
 [epsilon].
Specyfikacja:
Dane: liczby a i b takie, że a
b

oraz


0
f a
f b


liczba
0

Wynik: liczba rzeczywista x z przedziału
,a b taka, że 

0
f x 


dla pewnego 
takiego, że
2
2






Funkcja


, ,
Mzer a b 

\n
  1. jeżelib
\n

a



, to wykonaj:
a.
2
a
b
s


b. jeżeli

0
f s 
, to podaj s jako wynik
c. jeżeli


0
f a
f s


, topodaj


, ,
Mzer a s  jako wynik
w przeciwnym przypadku podaj


, ,
Mzer s b  jako wynik
Przykładowe zadania z rozwiązaniami 39

\n
  1. w przeciwnym przypadku podaj 
\n

/ 2
a
b

jako wynik
)
Poniżej prezentujemy fragment wykresu funkcji f , dla której wywołujemyfunkcję Mzer:
Wykres przecina oś OX w punkcie 72,7. Załóżmy, że funkcja Mzer została wywołana
dla
0
a 
i
128
b 
. W poniższej tabelce podaj liczbę kolejnych rekurencyjnych wywołań
funkcji Mzerprzy podanych poniżej wartościach 

liczba wywołań Mzer
10
4
32
2
25
3
5
5
1
5
10
b) Poniżej prezentujemy zapis algorytmu opisanego funkcją Mzer w postaci
nierekurencyjnej. Zapis poniższego algorytmu jest niepełny, uzupełnij brakujące
elementy tak, aby realizował tę samą metodę poszukiwania miejsca zerowego, którą
opisuje funkcja Mzer.
Algorytm

\n
  1. dopóki b
\n

a



wykonuj
a)
2
a
b
s


b) jeżeli

0
f s 
, to podaj s jako wynik i zakończ wykonywanie algorytmu
Wykres funkcji f w przedziale <0,128>
-40
-20
0
20
40
60
80
100
0
5
10
15
20
25
30
35 40
45
50 55
60
65
70 75
80
85
90
95 100 105 110 115 120 125
40 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
c) jeżeli


0
f a
f s


, to b
s

w przeciwnym przypadku a
s

\n
  1. podaj 
\n

/ 2
a
b

jako wynik
Komentarz
Podpunkt a
Aby obliczyć liczbę kolejnych rekurencyjnych wywołań funkcji Mzer dla każdej podanej
wartości , należy ustalić wartości zmiennych z jakimi będzie ona wywoływana w kolejnych
krokach. Funkcja zakończy działanie w momencie, gdy b
a



Dla każdej dokładności startujemy od wywołania funkcji


0,128,
Mzer
, zaś kolejne
wywołania to:
Dla
32

mamy dwa wywołania:


64,128,32
Mzer


64,96,32
Mzer
Dla
25

mamy trzy wywołania:


64,128,25
Mzer


64,96,25
Mzer


64,80,25
Mzer
Dla
5

mamy pięć wywołań:


64,128,5
Mzer


64,96,5
Mzer


64,80,5
Mzer


72,80,5
Mzer


72,76,5
Mzer
Dla
1
5

mamy dziesięć wywołań:
1
64,128, 5
Mzer 





1
64,96, 5
Mzer 





1
64,80, 5
Mzer 





1
72,80, 5
Mzer 





1
72,76, 5
Mzer 





1
72,74, 5
Mzer 





Przykładowe zadania z rozwiązaniami 41
1
72,73, 5
Mzer 





1
72,5;73; 5
Mzer 





1
72,5;72,75; 5
Mzer 





1
72,625;72,75; 5
Mzer 





Podpunkt b
Aby uzupełnić luki w przedstawionej nierekurencyjnej wersji funkcji Mzer, należy zauważyć
prostą własność: w kolejnych krokach zawsze ustalamy środek aktualnego przedziału, tzn.
2
a
b
s


, a następnie sprawdzamy czy miejsce zerowe funkcji leży na lewo od punktu s
(wtedy b
s

), czy na prawo od punktu s(as).
Podpunkt a) sprowadza się do przeanalizowania algorytmu zaprezentowanego w treści
zadania na konkretnych danych i wyznaczenia liczby wywołań funkcji rekurencyjnej. Funkcja
Mzer opisuje podręcznikowy algorytm znajdowania miejsca zerowego funkcji ciągłej f
metodą bisekcji. Zadaniem zaprezentowanej implementacji tego algorytmu jest podanie
miejsca zerowego funkcji w przedziale 

,a b , z dokładnością do 2
 przy założeniu, że


0
f a
f b


(zauważmy, że ciągłość funkcji f w powiązaniu z warunkiem


0
f a
f b


gwarantuje, że f ma miejsce zerowe w przedziale 

,a b ).
W treści zadania przedstawiono pseudokod rekurencyjnej wersji algorytmu, która
rozpoczyna się od sprawdzenia czy odległość między krańcami przedziału [a,b] jest większa
od  (czyli podwojonej dokładności wyniku):

\n
  1. Gdy b - a , wówczas mamy gwarancję że środek przedziału 
\n


,a b znajduje się nie dalej
niż 2
 od miejsca zerowego funkcji f. Dlatego też jako wynik zwracany jest właśnie
środek przedziału, czyli wartość (a+b)/2.

\n
  1. Gdy b - a  , mamy dwie możliwości. Jeśli środek przedziału 
\n


,a b jest miejscem
zerowym funkcji f, zwracamy go oczywiście jako wartość. W przeciwnym razie
redukujemy zadanie wyszukania miejsca zerowego w 

,a b do zadania poszukiwania
miejsca zerowego w [a,s] lub [s,b], gdzie s to środek przedziału 

,a b . Efektem redukcji
jest więc dwukrotne zmniejszenie długości przedziału, w którym poszukujemy miejsca
zerowego.
Zauważmy, że gdyby wywołania funkcji Mzer dla a=0 i b=128 oraz podanych w punkcie a)
wartości  nigdy nie kończyły się znalezieniem dokładnej wartości miejsca zerowego (czyli
spełnieniem warunku f(s)=0), odpowiedzi w punkcie a) sprowadzałyby się do wskazania
ilokrotnie trzeba „połowić” przedział o długości 128 aby uzyskać przedział o długości nie
większej niż . W rozwiązaniu można by więc ograniczyć się do policzenia, ile takich
„połowień” należy wykonać. Aby jednak mieć pewność poprawności rozwiązania, trzeba
sprawdzić że wartość środka przedziału s rzeczywiście w naszym przykładzie nie „trafi”
idealnie w miejsce zerowe (równe 72,7) w kolejnych wywołaniach rekurencyjnych. Taką
skrupulatną analizę przedstawiliśmy omawiając rozwiązanie punktu a).
42 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
Punkt b) zadania wymaga zastosowania standardowej techniki zamiany rekurencji na
iterację. Zamiast wywoływać funkcję z nowymi wartościami krańców przedziałów,
zmieniamy w pętli wartości zmiennych a i b tak, aby odpowiadały one końcom coraz
mniejszych przedziałów dla których wywoływana jest funkcja rekurencyjna Mzer.
Przedstawiony szkielet algorytmu z pozostawionymi miejscami do uzupełnienia sugeruje
sposób, w jaki w tym przypadku należy dokonać zamiany rekurencji na iterację.
Przykładowe zadania z rozwiązaniami 43

","solutions":[]}