1.3算 法 案 例 秦 九 韶 算 法 問 題 1 某 位 同 學 求 多 項 式 f(x)=x5+x4+x3+x2+x+1當 x=5時 的 值 ， 設 計 一 個 算 法 后 寫 出 程 序 如 下 ：x=5f=x5 + x4 + x3 + x2 + x + 1PRINT fEND程 序 上 述 算 法 一 共 做 了 次 乘 法 運 算 , 次 加 法 運 算 .優(yōu) 點 是 簡 單 ,易 懂 ;缺 點 是 不 通 用 ,不 能 解 決 任 意 多項 多 求 值 問 題 ,而 且 計 算 效 率 不 高 .1 0 5 能 否 找 到更 高 效 的算 法 ? 問 題 2 怎 樣 找 到 更 高 效 的 算 法 ?分 析 :計 算 x的 冪 時 ,應 充 分 利 用 前 面 的 計 算 結(jié) 果 ,以 減 少 計 算 量 , 如 ： 先 計 算 x2,然 后 依 次 計 算2 2 2,( ) ,( ) )x x x x x x x x x 的 值 . 此 時 算 法 一 共 做了 次 乘 法 運 算 , 次 加 法 運 算 .45f(x)=x5+x4+x3+x2+x+1可 變 形 為f(x)=(x4+x3+x2+x+1)x+1 =(x3+x2+x+1)x+1)x+1 =(x 2+x+1)x+1)x+1 )x+1 =(x+1)x+1)x+1)x+1)x+1 f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我 們 可 以 改 寫 成 如 下 形 式 :f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求 多 項 式 的 值 時 ,首 先 計 算 最 內(nèi) 層 括 號 內(nèi) 一次 多 項 式 的 值 ,即 v1=anx+an-1,然 后 由 內(nèi) 向 外 逐 層 計 算 一 次 多 項 式 的 值 ,即一 般 地 ,對 于 一 個 n次 多 項 式v2=v1x+an-2, v3=v2x+an-3, , vn=vn-1x+a0.這 樣 ,求 n次 多 項 式 f(x)的 值 就 轉(zhuǎn) 化 為 求 n個一 次 多 項 式 的 值 .這 種 算 法 稱 為 秦 九 韶 算 法 . f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7 v0=2v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所 以 ,當 x=5時 ,多 項 式 的 值 是 2677.這 種 求 多 項 式 值 的 方 法 就 是 秦 九 韶 算 法 .例 1:用 秦 九 韶 算 法 求 多 項 式 f(x)=2x5-5x4-4x3+3x2-6x+7當 x=5時 的 值 . 變 形 前 的 計 算 ，需 要 多 少 次 乘 法計 算 和 多 少 次 加法 計 算 ？變 形 后 利 用 秦 九 韶 算 法 計 算 n次 多 項 式 當 x=x 0時 ， 需 要 多 少 次 乘 法 計 算 和 多 少 次 加 法 計 算 ？ 所 以 ,當 x=5時 ,多 項 式 的 值 是 2677. 原 多 項 式的 系 數(shù)例 1:用 秦 九 韶 算 法 求 多 項 式 f(x)=2x5-5x4-4x3+3x2-6x+7當 x=5時 的 值 .2 -5 -4 3 -6 7x=5 105 2521 105108 540534 26702677多 項 式的 值 .解 法 二 :列 表2V0 V1 V2 V3 V4 V5 所 以 ,當 x=5時 ,多 項 式 的 值 是 15170. 練 :用 秦 九 韶 算 法 求 多 項 式 f(x)=2x6-5x5-4x3+3x2-6x當 x=5時 的 值 .解 :原 多 項 式 先 化 為 : f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列 表 2 -5 0 -4 3 -6 0 x=5 105 2525 125121 605608 304030342 1517015170 注 意 :n次 多 項 式 有 n+1項 ,因 此 缺 少 哪 一 項應 將 其 系 數(shù) 補 0. 觀 察 上 述 秦 九 韶 算 法 中 的 n個 一 次 式 ,可 見vk的 計 算 要 用 到 vk-1的 值 . 若 令 v0=an,得 遞 推 式v0=an,vK=vK-1x+an-k(k=1,2,n） 這 是 一 個 在 秦 九 韶 算 法 中 反 復 執(zhí) 行 的 步 驟 ,因 此 可 用 循 環(huán) 結(jié) 構(gòu) 來 實 現(xiàn) .試 寫 出 程 序 框 圖 。變式訓練，深化提高 程 序 框 圖 否開 始輸 入 n, x, ani=0?v=ani=n-1 i=i-1輸 出 v結(jié) 束 是 v=vx+ai輸 入 a i程序：對比課本第3 9頁 2 .試搜索材料了解秦久韶，談談你對他的偉大之處的認識。 【 點 評 】 秦 九 韶 算 法 是 求 一 元 多 項 式的 值 的 一 種 方 法 .它 的 特 點 是 :把 求 一 個 n次 多 項 式 的 值轉(zhuǎn) 化 為 求 n個 一 次 多 項 式 的 值 ,通 過 這 種 轉(zhuǎn)化 ,把 運 算 的 次 數(shù) 由 至 多 n(n+1)/2次 乘 法 運算 和 n次 加 法 運 算 ,減 少 為 n次 乘 法 運 算 和 n次 加 法 運 算 ,大 大 提 高 了 運 算 效 率 . 思 考 ： 例 1計 算 時 ， 進 行 了 多 少 次 乘 法 計 算 ？多 少 次 加 法 計 算 ？例 1:用 秦 九 韶 算 法 求 多 項 式 f(x)=2x5-5x4-4x3+3x2-6x+7當 x=5時 的 值 .