計算機科學中，有一些關於多項式求值的問題。對於多項式求值問題，我們最容易想到的算法是求出每一項的值然後把所求的值累加起來，這種算法的時間和空間效率都不高，對於數據規模不大的題目來說由於其直觀、簡單很容易被大家採納，可一旦數據規模過大時，這種算法就顯得無能為力了，下面介紹一種解決這類求值問題的高效算法――霍納法則。在中國，霍納法則也被稱為秦九韶算法。
基本介紹
- 中文名：霍納法則
- 別稱：秦九韶算法
- 表達式：Pn(x)= anx ^n+a(n－1)x^(n-1)+…+a1x+a0
- 提出者：霍納
- 套用學科：數學 計算機
- 適用領域範圍：多項式求值
介紹,程式實現,套用,
介紹
假設有n+1個實數a0，a1，…，an,和x的序列，要對多項式Pn(x)= anx ^n+a(n－1)x^(n-1)+…+a1x+a0求值，直接方法是對每一項分別求值，並把每一項求的值累加起來，這種方法十分低效，它需要進行n+(n－1)+…+1=n(n+1)/2次乘法運算和n次加法運算。有沒有更高效的算法呢?答案是肯定的。通過如下變換我們可以得到一種快得多的算法，即Pn(x)= anx ^n+a(n－1)x^(n-1)+…+a1x+a0=((…(((anx +an－1)x+an－2)x+ an－3)…)x+a1)x+a0，這種求值的安排我們稱為霍納法則。
例如，當x=3時，計算p(x)=2x^4－x^3+3x^2+x－5的值。對於多項式p(x)=2x^4－x^3+3x^2+x－5，我們按霍納法則進行變換，有：
p(x)=2x^4－x^3+3x^2+x－5
=x(2x^3－x^2+3x+1)－5
=x(x(2x^2－x+3)+1)－5
=x(x(x(2x－1)+3)+1)－5
在實際的操作過程中，為了得到上式，我們沒有必要經過上述的特定變換，我們只需要一個該多項式係數的原始列表。我們可以方便地用一個二維表格來幫助我們筆算求出這個多項式的值。該表第一行包含了該多項式的係數（如果存在等於0的係數，也都包含進來），從最高的an到最低的a0。第二行中除了第一個和第二個單元格用來存儲x和an外，其它單元格都用來存儲中間結果。在作了這樣的初始化後，在計算第二行的某一個單元格的值時，用該單元格的前一個單元格乘以x的值再加上該單元格的第一行的係數即可。用這種方式算出的最後一個單元格的值，就是該多項式的值。
係數 | a4 | a3 | a2 | a1 | a0 |
係數值 | 2 | -1 | 3 | 1 | -5 |
x=3 | 2 | 3*2－1=5 | 3*5+3=18 | 3*18+1=55 | 3*55－5=160 |
所以，P(3)=160。我們拿表格中的單元格和多項式x(x(x(2x－1)+3)+1)－5做比較，我們會發現3*2－1=5是2x－1在x=3時的值，3*5+3=18是x(2x－1)+3在x=3時的值，3*18+1=55是x(x(2x－1)+3)+1在x=3時的值，最後3*55－5=160是x(x(x(2x－1)+3)+1)－5在x=3時的值。
程式實現
上述的計算過程我們可以用一個遞推的關係表示，即Pi(x)= xPi－1(x)+an－i，遞推的臨界值P0(x)= an，其中i=1…n。具體在實現時使用了滾動數組技術。
PASCAL語言代碼如下:
function horner(x:integer):longint;//求形如anx ^n+a(n－1)x^(n-1)+…+a1x+a0多項式的值，a[i]數組用於存放係數ai。
var
p:longint;
i:integer;
begin
p:=a[n];
for i:=1 to n do
p:=x*p+a[n-i];
horner:=p;
end;
套用
霍納法則在多項式求值運算中的套用，顯示出了算法的高效性和優雅性。下面就是霍納法則的一個典型的套用。
奇怪的貿易(題目來源:game journey國慶模擬賽): 剛結束了CS戰鬥的小D又進入了EVE的遊戲世界,在遊戲中小D是一名商人,每天要做的事情就是在這裡買東西,再運到那裡去賣.這次小D來到了陌生的X星,X星上有n種貨物,小D決定每種都買走一些,他用ai來表示第i種貨物購買的數量,X星人對物品的單價有特別的決定方式.他們首先會選擇一個基本價x(x為整數),第一種物品單價為x,第二種物品單價為x平方,第三種物品單價為x立方……第i種物品單價為x的i次方.結算總價時,你還需要給他們一筆手續費a0,小D不知道自己帶的錢是否能夠進行這筆交易,所以請你幫助他計算這筆交易他要支付的總金額是多少
輸入格式:
x n
a0
a1
a2
.
.
.
an
第一行兩個數分別表示基準價x (x<=10),物品種數n (n<=100000)
第二行一個數,手續費a0 (a0<=100)
接下來的n行每行一個數,第i行表示第i種物品購買的數量(ai<=100)
輸出格式:
輸出結果的最後100位,若不足100位請高位用零補足
數據規模:
對20%的數據,n<=10
對50%的數據,n<=200
對100%的數據,n<=100000
