Schemat Hornera
Schemat Hornera
Czym jest schemat Hornera ?
Schemat Hornera – sposób obliczenia
wartości wielomianu dla danej wartości
argumentu wykorzystujący minimalną liczbę
mnożeń.
Przykład wyznaczenia wartości wielomianu
schematem Hornera
3x
4
+2x
3
+7x
2
+9x+5
Weźmy pod uwagę pierwsze cztery elementy naszego
wielomianu. Możemy dla tych elementów wyłączyć
wspólny czynnik przed nawias. Tym czynnikiem jest x:
(3x
3
+2x
2
+7x+9)x+5
Teraz "wyciągamy" przed nawias x z pierwszych trzech
elementów w nawiasie:
((3x
2
+2x+7)x+9)x+5)
Następnie wyłączmy przed nawias następne x z dwóch
pierwszych elementów w wewnętrznym nawiasie:
(((3x+2)x+7)x+9)x+5
Schemat Hornera a schemat klasyczny
Stąd:
3*x*x*x*x+2*x*x*x+7*x*x+9*x+5,
czyli 10 mnożeń i 4
dodawania
(((3*x+2)*x+7)*x+9)*x+5,
czyli 4 mnożenia i 4 dodawania
n*(1+n)/2
–dla wielomianu w zwykłej postaci
n
– dla wartości wielomianu obliczonej przy pomocy schematu
Hornera
Przykład dla wielomianów wyższych stopni
Dla wielomianu stopnia 100 (n=100):
Schematem klasycznym:
n*(1+n)/2=100*(1+100)/2=
5050
mnożeń
Schematem Hornera:
100
mnożeń
Pętle w Delphi (w Pascalu)
Pętla pozwala na powtórzenie przez program
danej operacji określoną ilość razy. Są trzy
rodzaje pętli w Delphi (Pascal’u):
Pętla „while”
Pętla „repeat”
Pętla „for”
Pętla „while”
while <warunek> do <instrukcje>
Dopóki warunek spełniony wykonywane są
instrukcję
Warunek sprawdzany jest na początku
Przykład:
suma:=0;
while suma<10 do suma:=suma+1;
Pętla „repeat”
repeat <instrukcje> until <waunek>
powtarzaj <instrukcję> do momentu , aż zostanie
spełniony <warunek>
- zawsze wykona się przynajmniej jeden raz;
- rozkazy nie muszą być ograniczone przez begin-
end, robi to tutaj para repeat-until;
Przykład:
suma:=0;
repeat suma:=suma+1 until suma=4;
Pętla „for”:
For <p wartość zmiennej sterującej> to <k wartość
zmiennej sterującej> do <instrukcje>
Przykład:
For i:=0 to 10 do
write (‘liczba’,i);
- „i” jest zmienną typu integer, którą należy wcześniej
zadeklarować;
- wartość i zwiększa się z o 1 z każdym wykonaniem
<instrukcji>
Pętle for stosujemy wtedy gdy wiemy ile razy
<instrukcje> mają być wykonane
Pętla „for”
Przykład:
For i:=10 downto 0 do
write (‘liczba’,i);
Odmiana pętli for gdzie wartość zmienne
sterującej jest w każdym kroku zmniejszana o
1;
Instrukcja warunkowa „if”
if <warunek> then <instrukcje gdy spelniony> else
<instrukcje gdy nie spełniony>
Instrukcja „if” sprawdza <warunek> jeżeli jest on spełniony
wykonywane są odpowiednie instrukcję jeżeli nie to
wykonywana jest instrukcja wpisana po słowie kluczowym
„else”.
Przykłady:
if a>0 then write(‘wieksze’);
If a=>0 then write(‘wieksze lub rowne’) else
write(‘mniejsze’);
Instrukcja wielokrotnego wyboru
„case”
wybór 1: <instrukcje>;
...
wybór n: <instrukcje>;
else
(kod)
Słowo case wraz z of tworzą instrukcję warunkową (case..of). Może
być używana jako
zamiennik instrukcji warunkowych
. Stosuje się ją w
przypadku mało efektywnego wykorzystania instrukcji if ... then, tzn.
gdy należy sprawdzić większą liczbę możliwych warunków.
Instrukcja case ma to do siebie, że działa jedynie na typach
wyliczeniowych jak Char, Byte, Integer,
Instrukcja wielokrotnego wyboru
„case”
Przykład:
liczba:byte;
case liczba of
1: write(‘wybrales 1’);
2: write (‘wybrales 2’);
else
write (‘wybrales inna liczbe’);
end;