Пример. Анализирајмо пример у којем учитавамо редом цифре 3, 2, 7 и 5 и треба да добијемо број 3275. На основу дефиниције позиционог записа тај број је једнак вредности израза \(3\cdot 10^3 + 2 \cdot 10^2 + 7 \cdot 10 + 5\). Међутим, претходни израз можемо израчунати на следећи начин \(((3\cdot 10 + 2) \cdot 10 + 7)\cdot 10 + 5\), што доводи до Хорнеровог поступка. Ако се он имплементира итеративно, променљива n
којом се представља вредност броја узима редом вредности \(0\), \(3\), \(32\), \(327\) и \(3275\).
Пошто број цифара није унапред познат, цифре ћемо учитавати у петљи којом учитавамо бројеве до краја стандардног улаза.
Број који формирамо памтићемо у променљивој n
коју иницијизујемо на нулу. Када прочитамо цифру, додајемо је као цифру јединица на до сада формирани број. Додавање цифре јединица на број n
, постижемо тако што помножимо броја n
са 10 и додамо му учитану цифру. Ако унесемо \(k\) цифара, на описан начин цифру коју смо прву прочитали множићемо са 10 тачно \(k-1\) пут, другу прочитану цифру множимо са 10 тачно \(k-2\) пута, и тако редом, последњу прочитану цифру не множимо са 10 (то је цифра јединица).
#include <iostream>
using namespace std;
int main() {
int cifra;
int n = 0;
while (cin >> cifra)
10 + cifra;
n = n *
cout << n << endl;return 0;
}
Доказ коректности. Докажимо и формално коректност Хорнерове схеме. Претпоставимо да ће се редом учитавати цифре \(a_{k-1}\), \(a_{k-2}\), \(\ldots\), \(a_1\), \(a_0\). Инваријанта петље је то да је \(n\) вредност броја који се добија записом до сада прочитаних и обрађених цифара. Након \(i\) извршавања тела петље то су цифре од \(a_{k-1}\) до \(a_{k-i}\) и тврдимо да важи
\[n = (a_{k-1}\ldots a_{k-i})_{10} = a_{k-1}10^{i-1} + a_{k-2}10^{i-2} + \ldots + a_{k-i}10^0.\]
База. Након 0 извршавања тела петље важи да је \(n=0\) и \(i=0\). Број \((a_{k-1}\ldots a_{k-i})_{10} = (a_{k-1}\ldots a_{k})_{10}\) нема ниједну цифру и вредност му је нула.
Корак. Претпоставимо да инваријанта важи на уласку у тело петље. Нека је \(i' = i + 1\). Из тела петља види се да је \(n' = 10 \cdot n + a_{k-i-1}\). Пошто на основу индуктивне хипотезе важи \(n = a_{k-1}10^{i-1} + a_{k-2}10^{i-2} + \ldots + a_{k-i}10^0\), важи и да је
\(n' = 10(a_{k-1}10^{i-1} + a_{k-2}10^{i-2} + \ldots + a_{k-i}10^0) + a_{k-i-1} = a_{k-1}10^i + a_{k-2}10^{i-1} + \ldots + a_{k-i}10 + a_{k-i-1}.\)
Пошто је \(i' = i+1\), важи да је
\(n' = a_{k-i}10^{i'-1} + a_{k-2}10^{i'-2} + \ldots + a_{k-i'+1}10 + a_{k-i'},\)
па је инваријанта очувана.
Када се петља заврши, биће учитано \(k\) цифара, па ће важити да је \(i=k\), тј.
\[n = (a_{k-1}\ldots a_{k-i})_{10} = a_{k-1}10^{i-1} + a_{k-2}10^{i-2} + \ldots + a_1\cdot 10^1 + a_0\cdot 10^0,\]
што значи да \(n\) садржи декадну вредност броја формираног од свих \(k\) цифара.