課程內(nèi)容

《算法案例—秦九韶算法》
知識探究（一）：秦九韶算法的基本思想
思考1：對于多項式f（x）=x⁵+x⁴+x³+x²+x+1，求f（5）的值。若先計算各項的值，然后再相加，那么一共要做多少次乘法運算和多少次加法運算？
思考2：在上述問題中，若先計算x²的值然后依次計算x²·x，（x²·x）·x，（（x²·x）·x）·x的值，這樣每次都可以利用上一次計算的結(jié)果，再將這些數(shù)與x和1相加，那么一共做了多少次乘法運算和多少次加法運算？
思考3：利用后一種算法求多項式f（x）=a_nxⁿ+a_n-1x^n-1+……+a₁x+a₀的值，這個多項式應(yīng)寫成哪種形式？
思考4：對于f（x）=（…（（a_nx+a_n-1）x+a_n-2）x+…+a₁）x+a₀，由內(nèi)向外逐層計算一次多項式的值，其算法步驟如何？
思考5：上述求多項式f（x）=a_nxⁿ+a_n-1x^n-1+……+a₁x+a₀的值的方法稱為秦九韶算法，利用該算法求f（x₀）的值，一共需要多少次乘法運算，多少次加法運算？
思考6：在秦九韶算法中，記v₀=a_n，那么第k步的算式是什么？
知識探究（二）：秦九韶算法的程序設(shè)計
思考1：用秦九韶算法求多項式的值，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？
思考2：該算法的程序框圖如何表示？
思考3：該程序框圖對應(yīng)的程序如何表述？
典型例題
例1：已知一個5次多項式為f（x）=5x⁵+2x⁴+3.5x³-2.6x²+1.7x-0.8，用秦九韶算法求f（5）的值。
例2：閱讀下列程序，說明它解決的實際問題是什么？
  INPUT “x=”；a
  n=0
  y=0
  WHILE n<5
    y=y+（n+1）*a^n
    n=n+1
  WEND
  PRINT y
  END
小結(jié)
秦九韶算法是求一元多項式的值的一種方法，它的特點是：把求一個n次多項式的值轉(zhuǎn)化為求n個一次多項式的值，通過這種轉(zhuǎn)化，把運算的次數(shù)由至多n（n+1）/2次乘法運算和n次加法運算，減少為n次乘法運算和n次加法運算，大大提高了運算效率。評價一個算法好壞的一個重要標(biāo)志是運算的次數(shù)，在一元多項式求值的各種算法中，秦九韶算法至今仍是比較先進的算法。