Misja matura: zadanie 1

Przykładowe zadanie typu maturalnego

Zadanie 1. Wiązka zadań Schemat Hornera

Schemat Hornera jest bardzo efektywną metodą obliczania wartości wielomianuwielomianwielomianu:

P (x) = a_{n} x^{n} + a_{n - 1} x^{n - 1} + . . . + a_{2} x^{2} + a_{1} x^{} + a_{0}

gdzie dane liczby rzeczywiste aIndeks dolny 0, aIndeks dolny 1, …, aIndeks dolny n nazywamy współczynnikami, a liczba całkowita n ≥ 0 oznacza stopień wielomianustopień wielomianustopień wielomianu. Schemat bazuje na zależności:

P (x) = x (a_{n} x^{n - 1} + a_{n - 1} x^{n - 2} + . . . + a_{2} x^{1} + a_{1}) + a_{0} = x \cdot Q (x) + a_{0}

gdzie:

Q (x) = a_{n} x^{n - 1} + a_{n - 1} x^{n - 2} + . . . + a_{2} x^{1} + a_{1}

Stąd otrzymujemy następujący schemat obliczania wartości $P (x)$

Dane:

$n$ – liczba całkowita, $n \geq 0$ ,
$x$ – liczba rzeczywista,
$a_{0}$ , $a_{1}$ , ..., $a_{n}$ – liczby rzeczywiste.

Wynik:

wartość $P (x)$

Algorytm (schemat Hornera):

w = aIndeks dolny n_n

dla k = n - 1, n - 2, ..., 0 wykonuj

(*) w = x * w + aIndeks dolny k_k

zwróć w i zakończ

Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i znajduje się w Maturalnym zbiorze zadań z informatyki jako zadanie 22.

Zadanie 1.1

Treść polecenia

Uzupełnij poniższą tabelkę, podając wartości danych, jakie należy przyjąć w powyższym schemacie, aby wyznaczyć wartość $P (6)$ dla wielomianu:

P (x) = 10 x^{5} - 13 x^{4} + x^{3} + 2 x^{2} - 8 x + 7

Dane	Wartości
liczba naturalna $n$
liczba rzeczywista $x$
liczby rzeczywiste $a_{0}$ , $a_{1}$ , ..., $a_{n}$

Rozwiązanie

Aby wykonać to zadanie, należy dokładnie zapoznać się ze specyfikacją schematu Hornera.

Z opisu wynika, że liczba naturalna $n$ oznacza stopień wielomianu, więc $n = 5$ .

Liczba rzeczywista x to po prostu wartość, dla jakiej podany wielomian ma zostać obliczony, czyli $P (6)$ . Wynika stąd, że $x = 6$ .

Liczby rzeczywiste $a_{0}$ , $a_{1}$ , ..., $a_{n}$ to kolejne współczynniki wielomianu. Zatem jako odpowiedź należy wypisać kolejno: 7, -8, 2, 1, -13, 10.

Poprawna odpowiedź

Dane	Wartości
liczba naturalna $n$	5
liczba rzeczywista $x$	6
liczby rzeczywiste $a_{0}$ , $a_{1}$ , ..., $a_{n}$	7, -8, 2, 1, -13, 10

Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i znajduje się w Maturalnym zbiorze zadań z informatyki jako zadanie 22.1.

Zadanie 1.2

Treść polecenia

Uzupełnij poniższą tabelkę, wyrażając wzorem liczbę operacji mnożenia i dodawania, jaka zostanie wykonana przez schemat Hornera – w wierszu oznaczonym przez $(*)$ – dla danego wielomianu:

P (x) = a_{n} x^{n} + a_{n - 1} x^{n - 1} + . . . + a_{2} x^{2} + a_{1} x^{} + a_{0}

Dane	Liczba operacji
Dodawanie
Mnożenie

Rozwiązanie

W tym zadaniu należy przeanalizować zapisany w pseudokodzie algorytmalgorytmalgorytm. Działanie oznaczone jako $(*)$ wykonywane jest każdorazowo dla wartości od $n - 1$ do $0$ . Występują w nim kolejno jedna operacja mnożenia i jedna operacja dodawania. Oznacza to, że każda z nich wykona się tyle samo razy, czyli $n$ .

Poprawna odpowiedź

Dane	Liczba operacji
Dodawanie	$n$
Mnożenie	$n$

Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i znajduje się w Maturalnym zbiorze zadań z informatyki jako zadanie 22.2.

Zadanie 1.3

Treść zadania

Wielomianem parzystym nazywamy wielomian stopnia 2n postaci

$P\left(x\right)=a_nx^{2n}+a_{n-1}x^{2n-2}+...+a_2x^4+a_1x^2+a_0$

tzn. taki, w którym występują tylko parzyste potęgi zmiennej x. Bazując na schemacie Hornera, napisz algorytm o poniższej specyfikacji (w pseudokodzie lub wybranym języku programowania), który oblicza wartość parzystego wielomianu R(x).

Dane

n – liczba całowita, n >= 0,

x – liczba rzeczywista,

aIndeks dolny 0, aIndeks dolny 1, …, aIndeks dolny n – liczby rzeczywiste.

Wynik

wartość R(x)

Przy ocenie rozwiązania będzie brana pod uwagę liczba operacji mnożenia i dodawania wykonywanych przez algorytm.

Rozwiązanie

Zauważ, że jedyną różnicą pomiędzy wzorem podanym w tym zadaniu a ogólnym wzorem na obliczenie wartości wielomianu metodą schematu Hornera jest potęga, do jakiej należy podnieść wartość x. Aby sprowadzić wzór z zadania do wzoru ogólnego, wystarczy wcześniej podnieść x do potęgi drugiej.

p = x * x

w = aIndeks dolny n_n

dla k = n - 1, n - 2, ..., 0 wykonuj

(*) w = p * w + aIndeks dolny k_k

zwróć w i zakończ

Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i znajduje się w Maturalnym zbiorze zadań z informatyki jako zadanie 22.4.

Strefa wyzwań

Misja matura: zadanie 2

Przykładowe zadanie typu maturalnego

Zadanie 1. Wiązka zadań Schemat Hornera

Zadanie 1.1

Treść polecenia

Rozwiązanie

Poprawna odpowiedź

Zadanie 1.2

Treść polecenia

Rozwiązanie

Poprawna odpowiedź

Zadanie 1.3

Treść zadania

Rozwiązanie