Schemat Hornera


Podrozdziały   Tematy pokrewne

 

Wyprowadzenie schematu Hornera

W poprzednim rozdziale podaliśmy algorytm obliczania wartości liczby na podstawie wzoru:

 

Cn-1Cn-2...C2C1C0 = Cn-1 pn-1 + Cn-2 pn-2 + ... + C2 p2 + C1 p1 + C0 p0

 

W zastosowaniach informatycznych korzysta się z innego rozwiązania, zwanego schematem Hornera. Właściwie schemat ten ma zastosowanie przy wyznaczaniu wartości wielomianu, lecz jeśli przyjrzymy się dokładnie powyższemu wzorowi, to na pewno zauważymy podobieństwo do wzoru na wartość wielomianu:

 

W(x) = an-1 xn-1 + an-2 xn-2 + ... + a2 x2 + a1 x + a0

 

Współczynniki ai dla i = 0,1,2,...,n-1 odpowiadają wartościom cyfr C. Natomiast kolejne potęgi zmiennej x to oczywiście potęgi podstawy p. Schemat Hornera wyznaczymy dla 5-cio cyfrowej liczby (dla n-cyfrowej zasada jest identyczna, jednakże uczniowie gubią się w rachunkach). Liczba zapisana jest w systemie pozycyjnym o podstawie p ciągiem cyfr C4C3C2C1C0 i ma wartość:

 

L = C4 p4 + C3 p3 + C2 p2 + C1 p1 + C0 p0

 

Ponieważ p1 = p oraz p0 = 1, powyższy wzór można nieco uprościć i zapisać go w postaci:

 

L = C4 p4 + C3 p3 + C2 p2 + C1 p + C0

 

Wyprowadzamy przed nawias wspólny czynnik p:

 

L = p (C4 p3 + C3 p2 + C2 p + C1) + C0

 

Zwróć uwagę, iż wyrażenie w nawiasie ma niższy stopień. Znów wyprowadzamy przed nawias wspólny czynnik p.

 

L = p (p (C4 p2 + C3 p + C2) + C1) + C0

 

I jeszcze raz:

 

L = p (p (p (C4 p + C3) + C2) + C1) + C0

 

I po raz ostatni:

 

L = p (p (p (p (C4)+ C3) + C2) + C1) + C0

 

Ze względu na przemienność operacji mnożenia otrzymany wzór możemy zapisać w postaci:

 

L = ((((C4) p + C3) p + C2) p + C1) p + C0

 

Teraz wartość liczby obliczamy wyliczając wartości wyrażeń w kolejnych nawiasach:

 

L0 = C4 - wartość początkowa
L1 = L0 p + C3 = C4 p + C3
L2 = L1 p + C2 = (C4 p + C3) p + C2 = C4 p2 + C3 p + C2
L3 = L2 p + C1 = (C4 p2 + C3 p + C2) p + C1 = C4 p3 + C3 p2 + C2 p + C1
L4 = L3 p + C0 = (C4 p3 + C3 p2 + C2 p + C1) p + C0 = C4 p4 + C3 p3 + C2 p2 + C1 p + C0

 

Zwróć uwagę na sposób wyliczania wartości liczby. Wyraźnie widoczny jest pewien schemat postępowania. Najpierw za wartość liczby przyjmujemy C4. Następnie do wyczerpania pozostałych cyfr wykonujemy te same obliczenia: nową wartość otrzymujemy mnożąc poprzednią wartość przez podstawę systemu i dodając kolejną cyfrę. Rachunki kończymy po dodaniu ostatniej cyfry zapisu liczby.

Schemat ten nosi nazwę schematu Hornera.

 

Przykład:

Obliczyć za pomocą schematu Hornera wartość liczby piątkowej 4223213(5).

 

L0 = 4
L1 = 45 + 2 = 22
L2 = 225 + 2 = 112
L3 = 1125 + 3 = 563
L4 = 5635 + 2 = 2817
L5 = 28175 + 1 = 14086
L6 = 140865 + 3 = 70433 - koniec, ponieważ wyczerpaliśmy wszystkie cyfry

 

4223213(5) = 70433(10).

 

Zalety schematu Hornera

Po co to wszystko jest potrzebne? Po pierwsze oszczędność w mnożeniu. Sprawdźmy. Dla pięciu cyfr musimy wykonać następujące rachunki przy zastosowaniu standardowego wzoru:

 

L = C4 p p p p + C3 p p p + C2 p p + C1 p + C0

 

Daje to w sumie 10 mnożeń i 4 dodawania. Ten sam rachunek schematem Hornera prowadzi do wykonania 4 mnożeń i 4 dodawań. Mniej mnożeń oznacza większą efektywność algorytmu Hornera ponieważ mnożenie zajmuje procesorowi komputera więcej czasu od dodawania. Drugą zaletą jest sposób przetwarzania cyfr. Bierzemy je kolejno jedna po drugiej z ciągu wejściowego aż do napotkania końca zapisu. Ponieważ taka kolejność cyfr jest zwykle zgodna z kolejnością ich przechowywania w łańcuchu tekstowym, zatem sposób ten daje nam kolejne przyspieszenie i uproszczenie działania algorytmu (w poprzednim algorytmie cyfry przetwarzaliśmy w kierunku odwrotnym poczynając od ostatniej w zapisie).

 

Algorytm

Podsumujmy podane dotychczas informacje w formie algorytmu.

 

Specyfikacja problemu

Dane wejściowe

p - podstawa systemu pozycyjnego zapisu liczby p ∈ N,   p ∈ {2,3,...,10}
s - tekst zawierający ciąg znaków ASCII przedstawiających poprawny zapis liczby.

Dane wyjściowe

Liczba L będąca wartością liczby o podstawie p i zapisanej w postaci ciągu znaków s. L ∈ N + {0}

Zmienne pomocnicze i funkcje

i - numery pozycji znaków w s, i ∈ N
c - przechowuje wartość cyfry, c ∈ N + {0}
kod(znak) - funkcja zwraca kod ASCII znaku
długość(tekst) - zwraca liczbę znaków zawartych w tekście

 

Lista kroków

K01: Czytaj p i s
K02: L ← kod(s[1]) - kod("0")
K03: Dla i = 2,3,...,długość(s) wykonuj K04...K05
K04:     c ← kod(s[i]) - kod("0")
K05:     L ← L × p + c
K06: Pisz L
K07: Zakończ

 

Schemat blokowy

Odczytujemy podstawę p systemu liczbowego, w którym zapisana jest liczba. Podstawa musi należeć do zakresu od 2 do 10. Następnie odczytujemy ciąg znaków s reprezentujących cyfry. W zmiennych łańcuchowych pozycje znaków są numerowane od 1 (w C++, Pythonie i JavaScript od 0) począwszy od strony lewej do prawej.

Po odczytaniu danych wejściowych inicjujemy zmienne robocze. Początkowa wartość liczby L ustawiana jest na wartość pierwszej cyfry zapisu. Zmienna i steruje pętlą iteracyjną. Wprowadzamy do niej indeks drugiego znaku odczytanego łańcucha s i rozpoczynamy pętlę.

Pętla wykonuje się o jeden raz mniej niż liczba znaków w łańcuchu s. W pętli wyznaczamy wartość kolejnej cyfry w c.  Za nową wartość liczby L przyjmujemy poprzednią wartość pomnożoną przez p i zwiększoną o wartość cyfry c (schemat Hornera). Zwiększamy indeks i przechodzimy na początek pętli.

Po zakończeniu pętli w zmiennej L mamy wartość liczby. Wypisujemy ją i kończymy algorytm.



Programy

Na podstawie algorytmu tworzymy programy obliczające wartość liczby podanej w systemie pozycyjnym o podstawach od 2 do 10. Zwróć uwagę, iż algorytm nie sprawdza poprawności danych wprowadzonych przez użytkownika. Zastanów się nad sposobami usunięcia tej wady.

 

Efekt uruchomienia programu
Obliczanie wartości liczby zapisanej
w systemie pozycyjnym  o podstawie p
    przy pomocy schematu Hornera
------------------------------------
(C)2005 mgr J. Wałaszek  I LO Tarnów

Podaj p (2..10) = 8

Podaj liczbę    = 777

Liczba 777(8) = 511(10)

KONIEC. Naciśnij dowolny klawisz...

 

Borland
Delphi 7.0
Personal
Edition
// Zastosowanie schematu Hornera przy obliczaniu
// wartości liczb zapisanych w różnych systemach
// pozycyjnych o podstawie p od 2 do 10
//----------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
//                     I Liceum Ogólnokształcące
//                     im. K. Brodzińskiego
//                     w Tarnowie
//-----------------------------------------------

program horner;

{$APPTYPE CONSOLE}

var
  s : string;
  p,L,i,c : cardinal;

begin
  writeln('Obliczanie wartosci liczby zapisanej');
  writeln('w systemie pozycyjnym  o podstawie p');
  writeln('    przy pomocy schematu Hornera');
  writeln('------------------------------------');
  writeln('(C)2005 mgr J. Walaszek  I LO Tarnow');
  writeln;
  write('Podaj p (2..10) = '); readln(p);
  writeln;
  write('Podaj liczbe    = '); readln(s);
  writeln;
  L := ord(s[1]) - ord('0');
  for i := 2 to length(s) do
  begin
    c := ord(s[i]) - ord('0');
    L := L * p + c;
  end;
  writeln('Liczba ',s,'(',p,') = ',L,'(10)');
  writeln;
  writeln('Nacisnij klawisz ENTER...');
  readln;
end.
Borland
C++ Builder
6.0
Personal
Edition
// Zastosowanie schematu Hornera przy obliczaniu
// wartości liczb zapisanych w różnych systemach
// pozycyjnych o podstawie p od 2 do 10
//----------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
//                     I Liceum Ogólnokształcące
//                     im. K. Brodzińskiego
//                     w Tarnowie
//-----------------------------------------------

#include <iostream>
#include <string>

using namespace std;

main()
{
  string s;
  unsigned i,p,L,c;
  char z[1];
  
  cout << "Obliczanie wartosci liczby zapisanej\n"
          "w systemie pozycyjnym  o podstawie p\n"
          "    przy pomocy schematu Hornera\n"
          "------------------------------------\n"
          "(C)2005 mgr J. Walaszek  I LO Tarnow\n\n"
          "Podaj p (2..10) = ";
  cin >> p;
  cout << "\nPodaj liczbe    = ";
  getline(cin,s);
  getline(cin,s);
  L = s[0] - int('0');
  for(i = 1; i < s.length(); i++)
  {
    c = s[i] - int('0');
    L = L * p + c;
  }
  cout << "\nLiczba " << s << "(" << p << ") = " << L << "(10)"
          "\n\nNacisnij ENTER...\n";
  cin.getline(z,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
' Zastosowanie schematu Hornera przy obliczaniu
' wartości liczb zapisanych w różnych systemach
' pozycyjnych o podstawie p od 2 do 10
'----------------------------------------------
' (C)2005 mgr Jerzy Wałaszek
'                     I Liceum Ogólnokształcące
'                     im. K. Brodzińskiego
'                     w Tarnowie
'-----------------------------------------------

Option Explicit On

Module Module1

 Sub Main()

    Dim s As String
    Dim p, L, i, c As UInteger

    Console.WriteLine("Obliczanie wartości liczby zapisanej")
    Console.WriteLine("w systemie pozycyjnym  o podstawie p")
    Console.WriteLine("    przy pomocy schematu Hornera")
    Console.WriteLine("------------------------------------")
    Console.WriteLine("(C)2005 mgr J. Wałaszek  I LO Tarnów")
    Console.WriteLine()
    Console.Write("Podaj p (2..10) = ") : p = Val(Console.ReadLine)
    Console.WriteLine()
    Console.Write("Podaj liczbę    = ") : s = Val(Console.ReadLine)
    Console.WriteLine()
    L = Asc(s.Chars(0)) - Asc("0")
    For i = 1 To s.Length() - 1
      c = Asc(s.Chars(i)) - Asc("0")
      L = L * p + c
    Next
    Console.WriteLine("Liczba {0}({1}) = {2}(10)", s, p, L)
    Console.WriteLine()
    Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
    Console.ReadLine()

  End Sub

End Module
JavaScript
<html>
  <head>
  </head>
  <body>
    <div align="center">
      <form style="BORDER-RIGHT: #ff9933 1px outset;
                   PADDING-RIGHT: 4px;
                   BORDER-TOP: #ff9933 1px outset;
                   PADDING-LEFT: 4px;
                   PADDING-BOTTOM: 1px;
                   BORDER-LEFT: #ff9933 1px outset;
                   PADDING-TOP: 1px;
                   BORDER-BOTTOM: #ff9933 1px outset;
                   BACKGROUND-COLOR: #ffcc66"
            name="frmhorner">
        <h3 id="data_out" style="text-align: center">
          Obliczanie wartości liczby zapisanej<br>
          w systemie pozycyjnym o podstawie p<br>
          za pomocą schematu Hornera
        </h3>
        <p style="TEXT-ALIGN: center">
          (C)2005 mgr Jerzy Wałaszek&nbsp;&nbsp; I LO w Tarnowie
        </p>
        <hr>
        <div align="center">
          <table border="0" cellpadding="4"
                 style="border-collapse: collapse">
            <tr>
              <td align="right">podstawa (2...10) =</td>
              <td>
<input value="5" name="inp_p" size="20" style="text-align: right">
              </td>
            </tr>
            <tr>
              <td align="right">liczba =</td>
              <td>
<input value="23314" name="inp_s" size="20" style="text-align: right">
              </td>
            </tr>
          </table>
        </div>
        <p style="TEXT-ALIGN: center">
          <input onclick="main();"
                 type="button"
                 value="Oblicz wartość liczby"
                 name="B1">
        </p>
        <p id="out_t" style="TEXT-ALIGN: center">...</p>
      </form>

<script language=javascript>

// Wyznaczanie wartości liczby zapisanej
// w systemie pozycyjnym o podstawie
// p równej od 2 do 10
//--------------------------------------
// (C)2005 mgr Jerzy Wałaszek
//             I Liceum Ogólnokształcące
//             im. K. Brodzińskiego
//             w Tarnowie
//--------------------------------------

function main()
{
  var s,p,L,c,i,t;

  p = parseInt(document.frmhorner.inp_p.value);
  s = document.frmhorner.inp_s.value;
  t = "<font color=Red><b>Złe dane</b></font>";
  if(!isNaN(p) && !(s==""))
  {
    L = s.charCodeAt(0) - 48;
    for(i = 1; i < s.length; i++)
    {
      c = s.charCodeAt(i) - 48;
      L = L * p + c;
    };
    t = s + "<sub>(" + p + ")</sub> = " + L + "<sub>(10)</sub>";
  };
  document.getElementById("out_t").innerHTML = t;
}
</script>
    </div>
  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Obliczanie wartości liczby zapisanej
w systemie pozycyjnym o podstawie p
za pomocą schematu Hornera

(C)2005 mgr Jerzy Wałaszek   I LO w Tarnowie
podstawa (2...10) =
liczba =

...

 


DLA
GENIUSZA

Zadania

Zadanie 1 (proste)

Obliczyć przy pomocy schematu Hornera wartości następujących liczb pozycyjnych:
1100110101101(2) =   

.

2320112(4) =   

.

7553327(8) =   

.

212122112(3) =   

.

4404324(5) =   

.

 

Podsumowanie

Wyznacz ilość mnożeń i dodawań przy obliczaniu wartości n cyfrowej liczby za pomocą schematu Hornera. Określ złożoność obliczeniową tego algorytmu. Porównaj otrzymane wyniki z wynikami uzyskanymi dla algorytmu podanego w poprzednim rozdziale.

 


Zobacz dalej...

Wartość liczby pozycyjnej | Przeliczenia na inny zapis pozycyjny | Wartość liczby stałoprzecinkowej | Przeliczanie na zapis stałoprzecinkowy | Systemy pozycyjne o podstawie większej od 10 | Zapis zmiennoprzecinkowy



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.