Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Schemat Hornera

No description
by

Claudia Khan

on 23 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Schemat Hornera

Background photo by t.shigesa
Schemat Hornera
Spójrzmy bliżej
Schemat Hornera nie jest typowym, normalnym algorytmem. Jest to jedynie efektywniejszy sposób liczenia wartości wielomianów. Ponieważ mnożenie zajmuje procesorowi bardzo dużo czasu, więc wszelkie ograniczenie tego działania w jakimkolwiek algorytmie zwiększa jego szybkość w znacznym stopniu. Na tym właśnie polega Schemat Hornera.
O co kaman?

Weźmy na przykład pod uwagę następujący wielomian:

7x4 + 3x3 + 5x2 + 9x + 1



Algorytm obliczania wielomianów
Służy do szybkiego bliczania wielomanów, redukując ilość mnożenia do minimum.
Następny krok
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:

Teraz "wyciągamy" przed nawias x z pierwszych trzech elementów w nawiasie:

Wyciągamy
Wyłączanie przed nawias
Następnie wyłączmy przed nawias następne x z dwóch pierwszych elementów w wewnętrznym nawiasie:
((7x + 3)x + 5)x + 9)x + 1
(7x2 + 3x + 5)x + 9)x + 1
(7x2 + 3x + 5)x + 9)x + 1
I to wszystko! Na tym polega cały schemat Hornera. Niby nic... Proszę teraz porównać liczbę mnożeń w początkowym wielomianie i w tym na końcu.
A jednak bółka z masłem
Zwykłe mnożenie wielomianu
7*x*x*x*x + 3*x*x*x + 5*x*x + 9*x + 1, czyli 10 mnożeń i 4 dodawania
Mnożenie Schematem Hornera
((7*x + 3)*x + 5)*x + 9)*x + 1, czyli 4 mnożenia i 4 dodawania
Wnioski
Obydwa wyrażenia reprezentują to samo, ale dzięki zastosowaniu schematu Hornera drugie zawiera dużo mniej mnożeń.
Dla wielomianu n-tego stopnia w zwykłej postaci należy wykonać n*(1+n)/2 mnożeń, a dla wielomianu po zastosowaniu schematu Hornera tylko n mnożeń! Różnica jest olbrzymia.
Dziękuję za uwagę
Wykonała Klaudia Klimek :))
I ładnie prosi o 5! :>>
THE END
Dziękuję za uwagę! :)
Made by Klaudia Klimek
Proszę ładnie Pana o 5! ^-^
Full transcript