Przeczytaj

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.

Słownik

William George Horner

brytyjski matematyk żyjący w latach 1786–1837; w wieku $14$ lat został asystentem nauczyciela w szkole w Bristolu, a w $1809$ roku założył własną szkołę w Bath; podał sposób wyznaczania wartości wielomianu z wykorzystaniem minimalnej liczby operacji możenia

wielomian

wyrażenie algebraiczne będące sumą jednomianów, czyli wyrażeń postaci aIndeks dolny nxIndeks górny n

stopień wielomianu

najwyższa potęga przy zmiennej, która nie jest równa zero

algorytm

przepis postępowania prowadzący do rozwiązania ustalonego problemu, określający ciąg czynności elementarnych, które należy w tym celu wykonać

iteracja

technika programowania polegająca na powtarzaniu tych samych operacji w pętli określoną liczbę razy lub do momentu, aż zostanie spełniony zadany warunek

rekurencja

technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego

przypadek podstawowy

przypadek, dla którego funkcja rekurencyjna nie wywołuje samej siebie, a zamiast tego zwraca z góry określoną wartość

wykonanie elementarne w rekurencji

moment, gdy funkcja rekurencyjna zwraca konkretną wartość zamiast kolejnego wywołania rekurencyjnego

Wprowadzenie

Prezentacja multimedialna

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

Słownik