《2015高中數(shù)學(xué)1.3算法案例課件新人教A版必修》由會(huì)員分享,可在線閱讀,更多相關(guān)《2015高中數(shù)學(xué)1.3算法案例課件新人教A版必修(15頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1.3算 法 案 例 秦 九 韶 算 法 問(wèn) 題 1 某 位 同 學(xué) 求 多 項(xiàng) 式 f(x)=x5+x4+x3+x2+x+1當(dāng) x=5時(shí) 的 值 , 設(shè) 計(jì) 一 個(gè) 算 法 后 寫 出 程 序 如 下 :x=5f=x5 + x4 + x3 + x2 + x + 1PRINT fEND程 序 上 述 算 法 一 共 做 了 次 乘 法 運(yùn) 算 , 次 加 法 運(yùn) 算 .優(yōu) 點(diǎn) 是 簡(jiǎn) 單 ,易 懂 ;缺 點(diǎn) 是 不 通 用 ,不 能 解 決 任 意 多項(xiàng) 多 求 值 問(wèn) 題 ,而 且 計(jì) 算 效 率 不 高 .1 0 5 能 否 找 到更 高 效 的算 法 ? 問(wèn) 題 2 怎 樣 找 到 更
2、高 效 的 算 法 ?分 析 :計(jì) 算 x的 冪 時(shí) ,應(yīng) 充 分 利 用 前 面 的 計(jì) 算 結(jié) 果 ,以 減 少 計(jì) 算 量 , 如 : 先 計(jì) 算 x2,然 后 依 次 計(jì) 算2 2 2,( ) ,( ) )x x x x x x x x x 的 值 . 此 時(shí) 算 法 一 共 做了 次 乘 法 運(yùn) 算 , 次 加 法 運(yùn) 算 .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-1
3、xn-1+an-2xn-2+a1x+a0.我 們 可 以 改 寫 成 如 下 形 式 :f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求 多 項(xiàng) 式 的 值 時(shí) ,首 先 計(jì) 算 最 內(nèi) 層 括 號(hào) 內(nèi) 一次 多 項(xiàng) 式 的 值 ,即 v1=anx+an-1,然 后 由 內(nèi) 向 外 逐 層 計(jì) 算 一 次 多 項(xiàng) 式 的 值 ,即一 般 地 ,對(duì) 于 一 個(gè) n次 多 項(xiàng) 式v2=v1x+an-2, v3=v2x+an-3, , vn=vn-1x+a0.這 樣 ,求 n次 多 項(xiàng) 式 f(x)的 值 就 轉(zhuǎn) 化 為 求 n個(gè)一 次 多 項(xiàng) 式 的 值 .這 種 算 法 稱 為
4、 秦 九 韶 算 法 . 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所 以 ,當(dāng) x=5時(shí) ,多 項(xiàng) 式 的 值 是 2677.這 種 求 多 項(xiàng) 式 值 的 方 法 就 是 秦 九 韶 算 法 .例 1:用 秦 九 韶 算 法
5、 求 多 項(xiàng) 式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng) x=5時(shí) 的 值 . 變 形 前 的 計(jì) 算 ,需 要 多 少 次 乘 法計(jì) 算 和 多 少 次 加法 計(jì) 算 ?變 形 后 利 用 秦 九 韶 算 法 計(jì) 算 n次 多 項(xiàng) 式 當(dāng) x=x 0時(shí) , 需 要 多 少 次 乘 法 計(jì) 算 和 多 少 次 加 法 計(jì) 算 ? 所 以 ,當(dāng) x=5時(shí) ,多 項(xiàng) 式 的 值 是 2677. 原 多 項(xiàng) 式的 系 數(shù)例 1:用 秦 九 韶 算 法 求 多 項(xiàng) 式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng) x=5時(shí) 的 值 .2 -5 -4 3 -6 7x=5 105 2
6、521 105108 540534 26702677多 項(xiàng) 式的 值 .解 法 二 :列 表2V0 V1 V2 V3 V4 V5 所 以 ,當(dāng) x=5時(shí) ,多 項(xiàng) 式 的 值 是 15170. 練 :用 秦 九 韶 算 法 求 多 項(xiàng) 式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng) x=5時(shí) 的 值 .解 :原 多 項(xiàng) 式 先 化 為 : 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次 多 項(xiàng) 式 有 n+1項(xiàng) ,因 此
7、缺 少 哪 一 項(xiàng)應(yīng) 將 其 系 數(shù) 補(bǔ) 0. 觀 察 上 述 秦 九 韶 算 法 中 的 n個(gè) 一 次 式 ,可 見(jiàn)vk的 計(jì) 算 要 用 到 vk-1的 值 . 若 令 v0=an,得 遞 推 式v0=an,vK=vK-1x+an-k(k=1,2,n) 這 是 一 個(gè) 在 秦 九 韶 算 法 中 反 復(fù) 執(zhí) 行 的 步 驟 ,因 此 可 用 循 環(huán) 結(jié) 構(gòu) 來(lái) 實(shí) 現(xiàn) .試 寫 出 程 序 框 圖 。變式訓(xùn)練,深化提高 程 序 框 圖 否開(kāi) 始輸 入 n, x, ani=0?v=ani=n-1 i=i-1輸 出 v結(jié) 束 是 v=vx+ai輸 入 a i程序:對(duì)比課本第3 9頁(yè) 2 .試搜
8、索材料了解秦久韶,談?wù)勀銓?duì)他的偉大之處的認(rèn)識(shí)。 【 點(diǎn) 評(píng) 】 秦 九 韶 算 法 是 求 一 元 多 項(xiàng) 式的 值 的 一 種 方 法 .它 的 特 點(diǎn) 是 :把 求 一 個(gè) n次 多 項(xiàng) 式 的 值轉(zhuǎn) 化 為 求 n個(gè) 一 次 多 項(xiàng) 式 的 值 ,通 過(guò) 這 種 轉(zhuǎn)化 ,把 運(yùn) 算 的 次 數(shù) 由 至 多 n(n+1)/2次 乘 法 運(yùn)算 和 n次 加 法 運(yùn) 算 ,減 少 為 n次 乘 法 運(yùn) 算 和 n次 加 法 運(yùn) 算 ,大 大 提 高 了 運(yùn) 算 效 率 . 思 考 : 例 1計(jì) 算 時(shí) , 進(jìn) 行 了 多 少 次 乘 法 計(jì) 算 ?多 少 次 加 法 計(jì) 算 ?例 1:用 秦 九 韶 算 法 求 多 項(xiàng) 式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng) x=5時(shí) 的 值 .