Matura 2017 (maj). Zadania 2. Rekurencja
Funkcja licz(x) przyjmuje jako argument dodatnią liczbę całkowitą x, natomiast jako wynik daje pewną liczbę całkowitą.
licz(x)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2)
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
Uwaga: div – dzielenie całkowite, mod – reszta z dzielenia całkowitego.
Zadanie 1.
Uzupełnij tabelę – podaj wartość licz(x) dla podanych argumentów x.
| x | licz(x) |
| 11 | 2 |
| 13 | 2 |
| 21 | 1 |
| 32 | -4 |
Obliczenia:
Rekurencja działa na zasadzie wywoływania funkcji dopóki x nie będzie równy 1. Na zielono zaznaczyłem kod który wykona się przy x = 11.
licz(11)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 11 div 2 = 5
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
Zwróci nam wartość 5, ponieważ teraz w = 11 div 2 = 5. Teraz ponownie wywołujemy funkcje licz(x) z wartością x = 5.
licz(5)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 5 div 2 = 2
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
Zwróci nam wartość 2, ponieważ teraz w = 5 div 2 = 2. Teraz ponownie wywołujemy funkcje licz(x) z wartością x = 2.
licz(2)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 2 div 2 = 1
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
Zwróci nam wartość 1, ponieważ teraz w = 2 div 2 = 1. Teraz ponownie wywołujemy funkcje licz(x) z wartością x = 1, ale to już zwróci nam w = 1.
licz(1)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2)
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
Musimy wrócić do naszych funkcji licz(x) i wykonać dalszą część kodu, którą zaznaczę kolorem czerwonym, wracamy do funkcji licz(2). Pamiętamy że w = 1.
licz(2)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 2 div 2 = 1
jeżeli x mod 2 = 1 // 2 mod 2 = 0
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1 // w = 1 – 1 = 0
Po wykonaniu tej funkcji w = 0, teraz wracamy do funkcji licz(5).
licz(5)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 5 div 2 = 2
jeżeli x mod 2 = 1 // 5 mod 2 = 1
podaj wynik w+1 // w = 0 + 1 = 1
w przeciwnym przypadku
podaj wynik w-1
Po wykonaniu tej funkcji w = 1, teraz wracamy do funkcji licz(11).
licz(11)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 11 div 2 = 5
jeżeli x mod 2 = 1 // 11 mod 2 = 1
podaj wynik w+1 // w = 1 + 1 = 2
w przeciwnym przypadku
podaj wynik w-1
Po wykonaniu tej funkcji w = 2, teraz już nie mamy w pamięci żadnej funkcji licz(x), to wynik naszej funkcji zwraca wartość 2.
Pozostałe rozwiązania:
Zadanie 2.
Dana jest dodatnia liczba całkowita k. Jaka jest najmniejsza dodatnia liczba całkowita x, dla której obliczanie wartości licz(x) wymaga dokładnie k wywołań funkcji licz, licząc także pierwsze wywołanie licz(x)? Podkreśl prawidłową odpowiedź.
Przykład: obliczenie licz(13) wymaga dokładnie 4 wywołań funkcji licz.
A) x = k2
B) x = 2k–1
C) x = k+1
D) x = 2k
Przykład odpowiedzi nr 1:
Najmniejsza dodatnia liczba całkowita x, dla której dokładne będzie k wywołań funkcji licz() jest to liczba sprawdzając od początku jeden (1). Wywołanie funkcji licz(x) z wartością 1 wykona się dokładnie jeden raz, ponieważ:
licz(1)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 11 div 2 = 5
jeżeli x mod 2 = 1 // 11 mod 2 = 1
podaj wynik w+1 // w = 1 + 1 = 2
w przeciwnym przypadku
podaj wynik w-1
W funkcji licz(1) wykona się tylko kod zaznaczony zielono i funkcja ta zwróci wynik 1. Następnie musimy sprawdzić dla jakiego k równe jest x, czyli kiedy x = k (1 = k).
Sprawdzamy dla x= 1:
A)
x = k2
k = 1 ⇒ x = 12 ⇒ 1 = 1
B)
x = 2k–1
k = 1 ⇒ x = 21-1 ⇒ x = 20 ⇒ 1 = 1
C)
x = k+1
k = 0 ⇒ x = 0 + 1 ⇒ 1 = 1 (k musi być liczbą dodatnią całkowitą!!! To odpada!!!)
D)
x = 2k
k = 0 ⇒ x = 20 ⇒ 1 = 1 (k musi być liczbą dodatnią całkowitą!!! To odpada!!!)
Mamy dwie odpowiedzi prawidłowe: A i B. Zastanawiając się, która odpowiedź jest prawidłowa i dlaczego jest to B, doszedłem do wniosku, iż musi to być to związane z liczbą binarną, dlatego postawiłem na odpowiedź B.
Przykład odpowiedzi nr 2 :
Jest to rozwiązanie, gdzie zostało założone, iż do sprawdzenia należy wybrać x ≠ 1. Padło na początek na liczbę x = 2 i tak dla tek liczby funkcja licz(2) wykona się dwa razy.
licz(2) ⇒ wywołań tej funkcji jest dokładnie 2 razy.
licz(2) ⇒ licz(1)
A)
x = k2
k = 2 ⇒ x = 22 ⇒ 2 = 4 ( to odpada ponieważ x = k2 )
B)
x = 2k–1
k = 2 ⇒ x = 22-1 ⇒ x = 21 ⇒ 2 = 2 (ta odpowiedź jest prawidłowa)
C)
x = k+1
k = 2 ⇒ x = 2 + 1 ⇒ 2 = 3 (równanie to nie jest prawdziwe!!! To odpada!!!)
D)
x = 2k
k = 2 ⇒ x = 22 ⇒ 2 = 4 (równanie to nie jest prawdziwe!!! To odpada!!!)
Odpowiedź jest prawidłowa, ale nie jest to najmniejsza dodatnia liczba całkowita. Tu moja uwaga, nie wiadomo co miał na myśli autor zadania.
Odpowiedź otrzymałem od Pana Jakuba. Dziękuje!!!
UWAGA!!! Jeśli ktoś ma bardziej racjonalne wyjaśnienie proszę napisać na kontakt@informatyka.dwojka.net. Dziękuję.
Zadanie 3.
Podaj najmniejszą liczbę całkowitą x większą od 100, dla której wynikiem wywołania licz(x) będzie 0.
Odpowiedź:
x = 135
Obliczenia:
W naszym przypadku podany algorytm jest to zamiana liczby dziesiętnej na liczbę binarną. W zadaniu tym należy wziąć po uwagę, kiedy otrzymamy wynik 0 (zero). Będzie to wtedy kiedy ilość zer i jedynej w liczbie binarnej będzie równa sobie. Kolejnym problem jest podanie liczy powyżej 10010, taka liczba zawiera 7 cyfr w zapisie binarnym. Szukamy liczby która w zapisie binarnym będzie miała parzystą ilość liczb, tj. w tym przypadku 8.
100000002 = 12810
Szukana najmniejsza liczba binarna zawierająca 8 cyfr, która składa się z 4 jedynek i 4 zer.
100001112 = 13510
