Temat 1
Obliczanie wielomianu metodą klasyczną i
metodą Hornera
Tomasz Walocha
Akademia Górniczo-Hutnicza w Krakowie
Kierunek Metalurgia
Wydział odlewnictwa
Rok I
Grupa VI
Spis treści
1. Metoda Hornera
2. Wykonywanie obliczeń metodą
klasyczną i Hornera
3. Przedstawienie różnicy czasu
wykonywania obliczeń obiema
metodami (tabelka)
4. Przedstawienie różnicy czasu
wykonywania obliczeń obiema
metodami (wykres)
5. Wnioski
1. Metoda Hornera
Metoda Hornera: Schemat Hornera sposób obliczania wartości wielomianu dla danej
wartości argumentu wykorzystujący minimalną liczbę mnożeń, jest to również algorytm
dzielenia wielomianu W(x) przez dwumian x-C. Schemat ten wiązany jest z nazwiskiem
Hornera, był jednak już znany Newtonowi, Ruffiniemu i matematykom chińskim w XII
wieku.
Przy dzieleniu wielomianów schemat Hornera można stosować tylko wtedy gdy w dwumianie
nie ma przy x żadnej potęgi i współczynnika. Dla przykładu: dla dzielenia przez dwumian
x-5 można stosować schemat Hornera. Jednak dla dzielenia przez dwumian 4x2-1 schematu
Hornera stosować już nie wolno. Dla dzielenia wielomianu przez dwumian 3x-6 można
stosować schemat Hornera, jeżeli najpierw podzieli się dwumian i wielomian, przez 3.
2. Wykonywanie obliczeń metodą klasyczną i
Hornera
Metoda klasyczna:
W(x)= 2x2+3x-5 W(x)=5
W(5)=2*5*5+3*5-5
W(5)=60
Metoda hornera:
W(x)=(2x+3)x-5
W(5)=(2*5+3)5-5
W(5)=13*5-5
W(5)=60
Metoda klasyczna:
W(x)=3x3+4x2+3x+6 W(x)=3
W(3)=3*3*3+4*3*3+3*3+6
W(3)=81+36+9+6
W(3)=132
Metoda hornera:
W(x)=(3x2+4x+3)x+6
W(3)=((3x+4)x+3)x+6
W(3)=((3*3+4)3+3)3+6
W(3)=((9+4)3+3)3+6
W(3)=(13*3+3)3+6
W(3)=(39+3)3+6
W(3)=42*3+6
W(3)=126+6
W(3)=132
Metoda klasyczna:
W(x)=2x4+4x3+5x2+2x-4 W(x)=2
W(2)=2*2*2*2*2+4*2*2*2+5*2*2+2*2-4
W(2)=32+32+20+4-4
W(2)=84
Metoda Hornera:
W(x)=(2x3+4x2+5x+2)x-4
W(2)=((2x2+4x+5)x+2)x-4
W(2)=(((2x+4)x+5)x+2)x-4
W(2)=(((2*2+4)2+5)2+2)2-4
W(2)=((8*2+5)2+2)2-4
W(2)=(21*2+2)2-4
W(2)=44*2-4
W(2)=88-4
W(2)=84
Metoda klasyczna:
W(x)=3x5+2x4+3x3+5x2+2x-10 W(x)=1
W(1)=3*1+2*1+3*1+5*1+2*1-10
W(1)=3+2+3+5+2-10
W(1)=15-10
W(1)=5
Metoda Hornera:
W(x)=(3x4+2x3+3x2+5x+2)x-10
W(1)=((3x3+2x2+3x+5)x+2)x-10
W(1)=(((3x2+2x+3)x+5)x+2)x-10
W(1)=((((3x+2)x+3)x+5)x+2)x-10
W(1)=((((3*1+2)1+3)1+5)1+2)1-10
W(1)=(((5*1+3) 1+5)1+2)1-10
W(1)=((8*1+5)1+2)1-10
W(1)=13*1+2)1-10
W(1)=15*1-10
W(1)=5
Metoda klasyczna:
W(x)=2x6+3x5+4x4+2x3+3x2+5x-120 W(x)=2
W(2)=2*2*2*2*2*2*2+3*2*2*2*2*2+4*2*2*2*2+2*2*2*2+3*2*2+5*2-120
W(2)=128+96+64+16+12+10-120
W(2)=326-120
W(2)=206
Metoda hornera:
W(x)=(2x5+3x4+4x3+2x2+3x+5)x-120
W(2)=((2x4+3x3+4x2+2x+3)x+5)x-120
W(2)=(((2x3+3x2+4x+2)x+3)x+5)x-120
W(2)=((((2x2+3x+4)x+2)x+3)x+5)x-120
W(2)=(((((2x+3)x+4)x+2)x+3)x+5)x-120
W(2)=(((((2*2+3)2+4)2+2)2+3)2+5)2-120
W(2)=((((7*2+4)2+2)2+3)2+5)2-120
W(2)=(((18*2+2)2+3)2+5)2-120
W(2)=((38*2+3)2+5)2-120
W(2)=(79*2+5)2-120
W(2)=163*2-120
W(2)=206
3. Przedstawienie różnicy czasu wykonywania
obliczeo obiema metodami (tabelka)
Liczba 7-12 (9) Czas hornera Czas klasyczny
1000 0 1
10000 0 4
100000 6 45
1000000 59 447
10000000 589 4473
100000000 5885 44732
Liczba 15-19 (17) Czas hornera Czas klasyczny
1000 0 1
10000 1 14
100000 11 137
1000000 107 1374
10000000 1070 13742
100000000 10699 137420
Liczba 20-25 (22) Czas hornera Czas klasyczny
1000 0 3
10000 1 22
100000 14 221
1000000 137 2209
10000000 1372 22095
100000000 13725 220952
4. Przedstawienie różnicy czasu wykonywania
obliczeo obiema metodami (wykres)
Wykres liczb o potędze 9
50000
45000
40000
35000
30000
25000
Czas hornera
Czas klasyczny
20000
15000
10000
5000
0
1000 10000 100000 1000000 10000000 100000000
Wykres liczby o potędze 17
160000
140000
120000
100000
80000
Czas hornera
Czas klasyczny
60000
40000
20000
0
1000 10000 100000 1000000 10000000 10000000
Wykres liczby o potędze 22
250000
200000
150000
Czas hornera
Czas klasyczny
100000
50000
0
1000 10000 100000 1000000 10000000 100000000
5. Wnioski
Na podstawie zaobserwowanych wyników przedstawionych w tabelach oraz
wykresach możemy stwierdzid iż metoda hornera jest dużo szybsza i
skuteczniejsza od metody klasycznej. Przy porównaniu czasów wykonania
działania obiema metodami widzimy że metoda hornera jest przy dużych
liczbach nawet 12x szybsza od metody klasycznej a przy dokładniejszej
obserwacji wykresu widzimy ze przy liczbie 10000000 czas obliczeo metoda
klasyczna gwałtownie wzrasta i z większymi liczbami staje się coraz większy
Bibliografia:
www.wikipedia.pl
Doświadczenie przeprowadzono na programie:
TurboDelphii
Wyszukiwarka
Podobne podstrony:
Obliczenia ramy Metodą przemieszczeń temperatura projekt39OBLICZENIE RAMY METODĄ PRZEMIESZCZEŃ OD OSIADANIA PODPÓR projekt42OBLICZENIE RAMY METODĄ PRZEMIESZCZEŃOD TEMPERATURY projekt43Badanie czystości metodą klasycznąCwiczenie 12 Obliczanie statecznosci danych metoda Fp MaslowaObliczanie wspolczynnika przenikania ciepla dla przegrod w kontakcie z gruntem metoda uproszczonaĆwiczenie 7 Identyfikacja bakterii (metoda klasyczna i testy API)metoda kierunkowa obliczeniaObliczanie wspolczynnika przenikania ciepla dla przegrod w kontakcie z gruntem metoda dokladnaObliczanie sieci poligonowych metodą punktów węzłowychcwicz mechanika budowli obliczanie ukladow statycznie niewyznaczalnych metoda sil rama6 własności estymatora parametrów klasycznego modelu liniowego uzyskanego metodą najmniejszych kwadrwięcej podobnych podstron