新課標(biāo)人教A版必修三第一章算法初步1.算法的概念

黃牛課件 中國首家新課標(biāo)免費(fèi)資源網(wǎng) 不必注冊 免費(fèi)下載 請記住我們的網(wǎng)址 算法 廣州大學(xué)數(shù)學(xué)系沈紅輝 2004年7月 一 算法的基本概念 1什么是算法算法 algorithm 一詞源于算術(shù) algorism 算術(shù)方法的原義是一個(gè)由已知推求未知的運(yùn)算過程 后來 人們把它推廣到一般 指算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則 甚至把把進(jìn)行某一工作的方法和步驟也稱為算法 例如 人們在計(jì)算過程中 先乘除 后加減 從內(nèi)到外去括號(hào)等規(guī)則 都是按部就班必須遵守的算法 人類最早關(guān)于算法的記錄存在于在兩河流域發(fā)現(xiàn)的公元前兩三千年的泥板書上 其中的一個(gè)典型例子就是計(jì)算利息何時(shí)能夠夠等于本金 算法早期發(fā)展中值得一提的另一個(gè)成果應(yīng)歸功于古希臘的歐幾里得 他提出的計(jì)算最大公約數(shù)的輾轉(zhuǎn)相除法 又稱歐幾里得算法 至今仍在使用 歐幾里得是古代最有名望的學(xué)者之一 古希臘數(shù)學(xué)家 幾何學(xué)的鼻祖 公元前300年左右 他所著 幾何原本 13卷 是世界上最早公理化的數(shù)學(xué)著作 在 幾何原本 中他充分總結(jié)了前人的生產(chǎn)經(jīng)驗(yàn)和研究成果 從公理和公設(shè)出發(fā) 運(yùn)用演繹法 經(jīng)過邏輯推理和數(shù)學(xué)運(yùn)算 創(chuàng)立了著名的歐幾里得 簡稱歐氏幾何 在 幾何原本 中 歐幾里得還闡述了關(guān)于求兩個(gè)整數(shù)的最大公約數(shù)的過程 這就是著名的歐幾里得算法 輾轉(zhuǎn)相除法 其具體過程如下 設(shè)給定的兩個(gè)正整數(shù)為m和n 求它們的最大公約數(shù)的步驟為 1 以m除以n 令所得的余數(shù)為r r必小于n 2 若r 0 則輸出結(jié)果n 算法結(jié)束 否則 繼續(xù)步驟 3 3 令m n n r 并返回步驟 1 繼續(xù)進(jìn)行 中國古代數(shù)學(xué)研究中也有許多有關(guān)算法的成果 用我國傳統(tǒng)的開方術(shù)求高次方程的近似根 是算法上的一大成就 此外 在社會(huì)上得到廣泛使用的珠算口訣就可以看做是典型的算法 它把復(fù)雜的計(jì)算 例如除法 描述為一系列按口訣執(zhí)行的簡單的算珠撥動(dòng)操作 中國古代數(shù)學(xué)以算法為主要特征 其中最具代表性的就是 九章算術(shù) 九章算術(shù) 是戰(zhàn)國 秦 漢時(shí)期數(shù)學(xué)發(fā)展的總結(jié) 就其數(shù)學(xué)成就來說 堪稱是世界數(shù)學(xué)名著 其內(nèi)容按類分章 以數(shù)學(xué)問題的形式出現(xiàn) 包括分?jǐn)?shù)四則運(yùn)算 開平方與開立方 包括二次方程數(shù)值解法 盈不足術(shù) 各種面積和體積公式 線性方程組解法 正負(fù)數(shù)運(yùn)算的加減法則 勾股形解法 特別是勾股定理和求勾股數(shù)的方法 等 其中方程組解法和正負(fù)數(shù)加減法則在世界數(shù)學(xué)發(fā)展上是遙遙領(lǐng)先的 就其特點(diǎn)來說 它形成了一個(gè)以籌算為中心 與古希臘數(shù)學(xué)完全不同的獨(dú)立體系 在11 14世紀(jì)約300年期間著名的數(shù)學(xué)家的著作中 如賈憲的 黃帝九章算法細(xì)草 劉益的 議古根源 秦九昭的 數(shù)書九章 李治的 測圓海鏡 和 益古演段 楊輝的 詳解九章算法 日用算法 和 楊輝算法 中 算法的特點(diǎn)得到了進(jìn)一步的強(qiáng)化和發(fā)展 其中包括發(fā)展了一套求高次方程近似根的方法 2 算法的一般特征算法實(shí)際上是一種抽象的解題方法 它具有動(dòng)態(tài)性 因此 算法的行為非常重要 作為一個(gè)算法 應(yīng)具有以下四個(gè)特征 1 能行性 effectiveness 算法的能行性包括兩個(gè)方面 一是算法中的每一個(gè)步驟必須是能實(shí)現(xiàn)的 例如 在算法中 不允許出現(xiàn)分母為零的情況 在實(shí)數(shù)范圍內(nèi)不能求一個(gè)負(fù)數(shù)的平方根等 二是算法執(zhí)行的結(jié)果要能達(dá)到預(yù)期的目的 通常 針對實(shí)際問題設(shè)計(jì)的算法 人們總是希望能夠得到滿意的結(jié)果 2 確定性 definiteness 算法的確定性 是指算法中的每一個(gè)步驟都必須是有明確定義的 不允許有模棱兩可的解釋 也不允許有多義性 這一特征也反映了算法與數(shù)學(xué)公式的明顯差異 在解決實(shí)際問題時(shí) 可能會(huì)出現(xiàn)這樣的情況 針對某種特特殊問題 數(shù)學(xué)公式是正確的 但按此數(shù)學(xué)公式設(shè)計(jì)的計(jì)算過程可能會(huì)使計(jì)算機(jī)系統(tǒng)無所適從 這是因?yàn)?根據(jù)數(shù)學(xué)公式設(shè)計(jì)的計(jì)算過程只考慮了正常使用的情況 而當(dāng)出現(xiàn)異常情況時(shí) 該計(jì)算過程就不能適應(yīng)了 例如 某計(jì)算工具規(guī)定 大于100的數(shù)認(rèn)為是比1大很多 而小于10的數(shù)不能認(rèn)為是比1大很多 且在正常情況下出現(xiàn)的數(shù)或是大于100 或是小于10 但指令 輸入一個(gè)X 若x比1大很多 則輸出數(shù)字1 否則輸出數(shù)字0 是不確定的 這是因?yàn)?在正常的輸入情況下 這一指令的執(zhí)行可以得到正確的結(jié)果 但在異常情況下 輸入的x在10與100之間 這一指令執(zhí)行的結(jié)果就不確定了 例如 某計(jì)算工具具有七位有效數(shù)字 如FORTRAN中的單精度運(yùn)算 在計(jì)算下列三個(gè)量A B 1 C 的和時(shí) 如果采用不同的運(yùn)算順序 就會(huì)得到不同的結(jié)果 即A B C 1 0A C十B 1 1而在數(shù)學(xué)上 A B C與A C B是完全等價(jià)的 這可知 算法和計(jì)算公式是有差別的 3 有窮性 finiteness 算法的有窮性是指算法必須能在有限的時(shí)間內(nèi)執(zhí)行完 即算法必須能在執(zhí)行有限個(gè)步驟之后終止 數(shù)學(xué)中的無窮級數(shù) 在實(shí)際計(jì)算時(shí)只能取有限項(xiàng) 即計(jì)算無窮級數(shù)的過程只能是有窮的 因此 一個(gè)數(shù)的無窮級數(shù)的表示只是一種計(jì)算公式 而根據(jù)精度要求確定的計(jì)算過程才是有窮的算法 算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義 如果一個(gè)算法的執(zhí)行時(shí)間是有窮的 但卻需要執(zhí)行千萬年 顯然這就失去了算法的實(shí)用價(jià)值 例如 克萊姆 Cramer 規(guī)則是求解線性代數(shù)方程組的一種數(shù)學(xué)方法 但不能以此為算法 這是因?yàn)?雖然總可以根據(jù)克萊姆規(guī)則設(shè)計(jì)出一個(gè)計(jì)算過程用于計(jì)算所有可能出現(xiàn)的行列式 但這樣的計(jì)算過程所需的時(shí)間實(shí)際上是不能容忍的 還例如 從理論上講 總可以寫出一個(gè)正確的弈棋程序 而且這也并不是一件很困難的工作 由于在一個(gè)棋盤上安排棋子的方式總是有限的 而且 根據(jù)一定的規(guī)則 在有限次移動(dòng)棋子之后比賽一定結(jié)束 因此 弈棋程序可以考慮計(jì)算機(jī)每一次可能的移動(dòng) 它的對手每一次可能的應(yīng)答 以及計(jì)算機(jī)對這些移動(dòng)的可能應(yīng)答等等 直到每個(gè)可能的移動(dòng)停止下來為止 此外 由于計(jì)算機(jī)可以知道每次移動(dòng)的結(jié)果 因此總可以選擇一種最好的移動(dòng)方式 但即使如此 這種弈棋程序還是不可能執(zhí)行 因?yàn)樗羞@些可能移動(dòng)的次數(shù)太多 所要花費(fèi)的時(shí)間不能容忍 由上述兩個(gè)例子可以看出 雖然許多計(jì)算過程是有限的 但仍有可能無實(shí)用價(jià)值 4 算法必須擁有足夠的情報(bào)一個(gè)算法是否有效 還取決于為算法的執(zhí)行所提供的情報(bào)是否足夠 例如 對于指令 如果小明是學(xué)生 則輸出字母Y 否則輸出N 當(dāng)算法執(zhí)行過程中提供了小明一定不是學(xué)生的某種信息時(shí) 執(zhí)行的結(jié)果將輸出字母N 當(dāng)提供的只是部分學(xué)生的名單 且小明恰在此名單之中 則執(zhí)行的結(jié)果將輸出字母Y 但如果在提供的部分學(xué)生的名單中找不到小明的名字 則在執(zhí)行該指令時(shí)無法確定小明是否是學(xué)生 通常 算法中的各種運(yùn)算總是要施加到各個(gè)運(yùn)算對象上 而這些運(yùn)算對象又可能具有某種初始狀態(tài) 這是算法執(zhí)行的起點(diǎn)或是依據(jù) 因此 一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān) 不同的輸入將會(huì)有不同的結(jié)果輸出 如果輸入不夠或輸入錯(cuò)誤 則算法本身也就無法執(zhí)行或執(zhí)