zadania z informatyki do części I egzaminu, p. rozszerzony - wskazówki, odpowiedzi

zadania z informatyki - Analiza algorytmów

Zadanie: 1 2 3 4 5 6 7 8 9 10

Zadanie 3.

Wiązka zadań Ciekawe mnożenia

Dana jest następująca funkcja rekurencyjna:

Dane:

x — liczba całkowita,
n — dodatnia liczba całkowita.

funkcja F(x, n)

jeżeli n = 1

podaj wynik x i zakończ

w przeciwnym razie

jeżeli n mod 3 = 0

k ← F(x, n div 3)

(*)

podaj wynik k*k*k i zakończ

w przeciwnym razie

(**)

podaj wynik x*F(x, n-1) i zakończ

Uwaga: „div” jest operatorem dzielenia całkowitego.

pokaż wskazówkę »

Zadanie 3.1.

Podaj wszystkie wywołania rekurencyjne funkcji F oraz obliczany po każdym wywołaniu wynik, jeśli na początku wywołamy F(2, 10).

wywołanie	wynik
F(2, 10)
F( ; )

pokaż wskazówkę »

Ta odpowiedź nie jest sprawdzana automatycznie. Zobacz odpowiedź i oceń się samodzielnie.

pokaż odpowiedź

Zadanie 3.2.

Uzupełnij tabelę o brakujące elementy:

x	n	wynik F(x, n)
2	2	4
2	3
3		81
	5	32
2		256
	10	1024

pokaż wskazówkę »

Ta odpowiedź nie jest sprawdzana automatycznie. Zobacz odpowiedź i oceń się samodzielnie.

pokaż odpowiedź

Zadanie 3.3.

Uzupełnij tabelę, podając łączną liczbę mnożeń wykonanych w wierszach oznaczonych (*) i (**) po wywołaniu F dla podanych argumentów x i n:

x	n	Liczba operacji mnożenia
2	2	1
2	3
3	4
4	7
4	8
4	9

pokaż wskazówkę »

Ta odpowiedź nie jest sprawdzana automatycznie. Zobacz odpowiedź i oceń się samodzielnie.

pokaż odpowiedź

Zadanie 3.4.

Podaj, która z poniższych funkcji określa liczbę wszystkich operacji mnożenia wykonywa- nych przez powyższy algorytm dla argumentu n będącego potęgą trójki (n = 3^m dla pewnego nieujemnego m):

lmnozen(n) = ndiv2
lmnozen(n) = log₂n
lmnozen(n) = 2 ⋅ log₃n
lmnozen(n) = 1 + √n

pokaż wskazówkę »

Ta odpowiedź nie jest sprawdzana automatycznie. Zobacz odpowiedź i oceń się samodzielnie.

pokaż odpowiedź

Udostępnij

« powrót

źródło: CKE

Reklama - Wykorzystajmy wspólnie nasz potencjał! • Kontakt • Patronat • Praca dla studentów •