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

zadania z informatyki - Tworzenie algorytmów

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

Zadanie 7.

Wiązka zadań Poszukiwania

Dana jest liczba naturalna n > 0 oraz uporządkowana tablica liczb całkowitych T[1..n]. Rozważmy następującą funkcję F dla trzech argumentów p, k, e, które są liczbami całkowitymi dodatnimi:

funkcja F (p, k, e)
jeżeli (k = p)
jeżeli (T [p] > e)
zwróć p i zakończ
w przeciwnym razie
zwróć p + 1 i zakończ
w przeciwnym razie
s ← (p+k) div 2
jeżeli T [s] > e
zwróć F (p, s, e)
w przeciwnym razie
zwróć F (s+1, k, e)

Zadanie 7.1.

Przeanalizuj działanie funkcji F i uzupełnij poniższą tabelkę dla p = 1, k = 5, e = 10:

T	F (p, k, e)
[3, 4, 6, 8, 9]
[15, 16, 18, 22, 24]
[2, 10, 16, 24, 26]
[1, 3, 10, 10, 18]

pokaż wskazówkę »

pokaż odpowiedź

Zadanie 7.2.

Zdecyduj, które z dokończeń podanego niżej zdania czynią z niego zdanie prawdziwe. Wybierz właściwą odpowiedź.

Funkcja F wykorzystuje

A) metodę zachłanną.

B) strategię „dziel i zwyciężaj”.

C) programowanie dynamiczne.

pokaż wskazówkę »

Zadanie 7.3.

Zdecyduj, które z dokończeń podanego niżej zdania czynią z niego zdanie prawdziwe. Wybierz właściwą odpowiedź.

Liczba wywołań rekurencyjnych funkcji F dla początkowych wartości p = 1 oraz k = n, będącej potęgą dwójki, jest w najgorszym przypadku równa

A) n div 2

B) √n

C) log₂ n

pokaż wskazówkę »

Zadanie 7.4.

Napisz algorytm, który korzystając z funkcji F, obliczy, ile jest liczb należących do przedziału [a, b] w uporządkowanej niemalejąco tablicy T[1..n], składającej się z liczb całkowitych dodatnich.

Specyfikacja
Dane:
n — liczba całkowita dodatnia
T[1..n] — uporządkowana tablica n liczb całkowitych, złożona z różnych liczb całkowitych dodatnich, taka że T[1] ≤ T[2] ≤ … ≤ T[n]
a — liczba całkowita dodatnia
b — liczba całkowita dodatnia
Wynik:
w — liczba elementów tablicy T[1..n] należących do przedziału [a, b].

pokaż wskazówkę »

pokaż odpowiedź

Udostępnij

« powrót

źródło: CKE

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