Konspekt ten dotyczy wykorzystania schematu Hornera do obliczania wartości wielomianu oraz obliczania dziesiętnej wartości liczb zapisanych w różnych systemach pozycyjnych.
Temat: Schemat Hornera i jego zastosowanie.
Czas trwania zajęć: 2 godz.
Cel ogólny: uczeń zna schemat Hornera i potrafi obliczyć wartość wielomianu iteracyjnie i rekurencyjnie.
Cele operacyjne:
a) wiadomości:
- umie podać różnice między iteracją a rekurencją
- wie, jak wygląda postać ogólna wielomianu
- rozumie znaczenie optymalizacji algorytmu
b) umiejętności
- potrafi zastosować schemat Hornera do obliczeń
- potrafi napisać program obliczający wartość dowolnego wielomianu iteracyjnie i rekurencyjnie
- potrafi prawidłowo interpretować znaczenie komunikatów oprogramowania
- potrafi ocenić złożoność algorytmu
Środki dydaktyczne: stanowiska komputerowe, środowisko FreePascal, kalkulator, tablica
Metoda pracy: problemowa, dyskusji, ćwiczeń
Forma pracy: częściowo praca zbiorowa jednolita oraz praca samodzielna przy komputerze
Przebieg zajęć:
I. Część wprowadzająca
Nauczyciel przedstawia uczniom zagadnienie omawiane na lekcji.
Przypomina postać ogólną wielomianu:
w(x) = a0xn + a1xn-1 + a2xn-2 + ... + an-1x + an
Nauczyciel pyta uczniów, jak obliczamy wartość wielomianu.
Zapis działań, jakie należy wykonać w celu obliczenia wartości wielomianu:
w = 3x4 + 2x3 + x2 - 4x + 2, dla x= 3
Nauczyciel podaje przykłady zastosowania umiejętności obliczania wartości wielomianu:
1) Wielomiany to podstawowe funkcje w informatyce, gdyż wartości większości innych funkcji są obliczane jako wartości odpowiednich wielomianów.
2) Zapis liczby dziesiętnej w dowolnym systemie pozycyjnym przy ustalonej podstawie np. 2.
Jest to wielomian, w którym współczynniki mogą przyjmować tylko określone wartości (np. 0, 1), a w miejscu zmiennej xwystępuje podstawa systemu.
Przykład:
(1011011)2 = 1*26+ 0*25 + 1*24 + 1*23 + 0*22+ 1*21 + 1*20
II. Część główna
Nauczyciel prosi o określenie złożoności tego sposobu obliczania wartości wielomianu.
Uczniowie podają, ile mnożeń i dodawań należy wykonać wykorzystując ten sposób obliczeń dla przykładu wielomianu w - 10 i 4).
Nauczyciel podaje wzór ogólny mnożeń i n dodawań.
A. Schemat Hornera
Nauczyciel wskazuje na inny sposób obliczania wartości wielomianu (wyprowadzając wzór):
dla wielomianu w z przykładu:
w = (((3x + 2)x + 1)x - 4)x + 2
dla postaci ogólnej wielomianu:
w(x) = (...((a0x + a1)x + a2)x + ... + an-1)x + an
Nauczyciel zwraca uwagę uczniów na prostotę obliczania wartości wielomianu tym sposobem (np. na kalkulatorze bez wykorzystywania pamięci).
Nauczyciel prosi uczniów o określenie złożoności tego sposobu na przykładzie wielomianu w, i ogólnie - n mnożeń i n dodawań.
Nauczyciel i uczniowie wspólnie formułują wniosek: Obliczając wartość wielomianu tym sposobem zmniejszymy ilość mnożeń - jest to sposób efektywniejszy i okazuje się, że jest on najbardziej
efektywny.
Uczniowie odpowiadają na pytanie: Dlaczego to jest tak ważne?
Mnożenie zajmuje procesorowi bardzo dużo czasu, więc wszelkie ograniczanie tego działania w jakimkolwiek algorytmie zwiększa jego szybkość w znacznym stopniu (mnożenie jest operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów).
Interpretacja schematu Hornera w sposób iteracyjny.
Uczniowie wskazują na operacje, które się powtarzają (można je
wykorzystać do zbudowania pętli - jako działanie
wi = wi-1*x+ ai, dla i = 1, ..., n
- w przypadku programowania można ten wzór zapisać, wykorzystując operator podstawiania, jako
w = w*x + ai, dla i = 1, ..., n).
Wspólne zapisanie schematu Hornera w postaci schematu blokowego.
Dane:
n - liczba naturalna - stopień wielomianu,
a0, a1, ..., an - liczby rzeczywiste - współczynniki wielomianu,
x - liczba rzeczywista - argument, dla którego będzie obliczana wartość wielomianu
Użyte zmienne:
i - liczba naturalna - licznik kontrolujący kolejne współczynniki,
w - liczba rzeczywista - wartość kolejnych obliczeń wykonywanych w pętlach
Wynik:
wartość wielomianu (ostatnia wartość zmiennej w) obliczona według schematu Hornera
Zapisanie schematu Hornera w postaci funkcji w języku Pascal (przypomnienie, że współczynniki wielomianu najłatwiej zapisać w pamięci komputera w postaci tablicy):
function wartosc:real;
var i:byte;
w:real;
begin
w:=a[0];
for i:=1 to n do
w:=w*x+a[i];
wartosc:=w;
end;
Nauczyciel prosi o dokończenie programu i sprawdzenie poprawności działania.
Interpretacja schematu Hornera w sposób rekurencyjny.
Nauczyciel przypomina, że algorytmy iteracyjne da się przedstawić w sposób rekurencyjny, i odwrotnie.
Zapisanie kolejnych iteracji w postaci wzorów:
w0 = a0
w1 = w0*x + a1
w2 = w1*x + a2
...
wn = wn-1*x + an
oraz wzoru rekurencyjnego:
w0 = a0
wn = wn-1*x + an
Na podstawie wzoru tworzymy funkcję rekurencyjną w języku Pascal.
function wartoscrek(k:byte):real;
begin
if k=0 then
wartoscrek:=t[0]
else
wartoscrek:=wartoscrek(k-1)*x+a[k];
end;
B. Zastosowanie schematu Hornera
Obliczanie wartości wielomianu.
Nauczyciel poleca uczniom uruchomienie programu Kalkulator (widok podstawowy) i obliczenie wartości przykładowego wielomianu, wykorzystując schemat Hornera oraz działania mnożenia i dodawania/odejmowania.
Dziesiętna reprezentacja liczb zapisanych w różnych systemach pozycyjnych.
Nauczyciel prosi o obliczenie wartości dziesiętnej liczby zapisanej w systemie dwójkowym, wykorzystując schemat Hornera (kolejne cyfry - współczynniki wielomianu, argument - liczba 2 - podstawa systemu).
(((((1*2 + 0)*2 + 1)*2 + 1)*2 + 0)*2 + 1)*2 + 1 =
Tak można obliczyć dziesiętną wartość liczby w dowolnym systemie (przy podstawach
większych od 10 problemem może być zamiana współczynników).
Nauczyciel zauważa, że w przypadku systemu dwójkowego, można jeszcze bardziej
zoptymalizować ten program – mnożenie współczynnika przez 2 można zastąpić dodawaniem.
III. Część podsumowująca
Uczniowie odpowiadają na pytania:
Co to jest schemat Hornera?
Dlaczego jest tak ważny?
Do czego można go wykorzystać?
Nauczyciel zadaje uczniom pracę domową:
Odnaleźć w książce do matematyki schemat Hornera, dotyczący dzielenia wielomianu przez
dwumian i przeanalizować go.
Zastanowić się, jak napisać program dotyczący schematu Hornera bez użycia tablic.
Opracował: Maciej Milczarek