回覆列表
  • 1 # 曇花一現71742

    秦九韶演算法是中國南宋時期的數學家秦九韶提出的一種多項式簡化演算法。在西方被稱作霍納演算法。

    秦九韶演算法是一種將一元n次多項式的求值問題轉化為n個一次式的演算法。其大大簡化了計算過程,即使在現代,利用計算機解決多項式的求值問題時,秦九韶演算法依然是最優的演算法。

    一般地,一元n次多項式的求值需要經過[n(n+1)]/2次乘法和n次加法,而秦九韶演算法只需要n次乘法和n次加法。在人工計算時,一次大大簡化了運算過程。

    把一個n次多項式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改寫成如下形式

    f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0]   

    =(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0]   

    =((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0]   

    =......   

    =(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0].   

    求多項式的值時,首先計算最內層括號內一次多項式的值,即   v[1]=a[n]x+a[n-1]   然後由內向外逐層計算一次多項式的值,即   

    v[2]=v[1]x+a[n-2]   

    v[3]=v[2]x+a[n-3]

      ......   

    v[n]=v[n-1]x+a[0]

      這樣,求n次多項式f(x)的值就轉化為求n個一次多項式的值。(注:中括號裡的數表示下標)  

    結論:對於一個n次多項式,至多做n次乘法和n次加法

  • 中秋節和大豐收的關聯?
  • 為什麼朱元璋要重啟殉葬制度?