Wróć do informacji o e-podręczniku Wydrukuj Pobierz materiał do PDF Pobierz materiał do EPUB Pobierz materiał do MOBI Zaloguj się, aby dodać do ulubionych Zaloguj się, aby skopiować i edytować materiał Zaloguj się, aby udostępnić materiał Zaloguj się, aby dodać całą stronę do teczki

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(anxn1+an1xn2+...+a2x1+a1)+a0=xQ(x)+a0

gdzie:

Q(x)=anxn1+an1xn2+...+a2x1+a1

Stąd otrzymujemy następujący schemat obliczania wartości Px

Dane:

  • n – liczba całkowita, n0,

  • x – liczba rzeczywista,

  • a0, a1, ..., an – liczby rzeczywiste.

Wynik:

  • wartość Px

Algorytm (schemat Hornera):

w = aIndeks dolny n

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

(*) w = x * w + aIndeks dolny 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ść P6 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 a0, a1, ..., an

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 P6. Wynika stąd, że x=6.

Liczby rzeczywiste a0, a1, ..., an 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 a0, a1, ..., an

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

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

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

(*) w = p * w + aIndeks dolny 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
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
wielomian

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

stopień wielomianu
stopień wielomianu

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

algorytm
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
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
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 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
wykonanie elementarne w rekurencji

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