1-4算法的基本概念v第一章緒論見識算法圖靈獎與算法Hoare在26歲發(fā)明了聞名于世的快速排序算法；Ronald、Shamir和Adleman發(fā)明了國際上最具影響力的公鑰密碼算法RSA；Knuth編著的《程序設(shè)計的藝術(shù)》奠定了數(shù)據(jù)結(jié)構(gòu)與算法領(lǐng)域的主要內(nèi)容；Floyd發(fā)明了求解多源點最短路徑的Floyd算法以及堆結(jié)構(gòu)；Karp在網(wǎng)絡(luò)流和組合優(yōu)化問題領(lǐng)域都發(fā)明了許多高效算法；

Hopcroft和他的學生Tarjan在數(shù)據(jù)結(jié)構(gòu)和算法方面有眾多創(chuàng)造性貢獻；姚期智（Chi-ChihYao）發(fā)明了偽隨機數(shù)的生成算法以及加密/解密算法；Sutherland發(fā)明的圖形圖像算法改善了屏幕刷新的文件顯示；Dijkstra發(fā)明了單源點的最短路徑算法Dijkstra算法；Wilkinson在數(shù)值線性代數(shù)方面發(fā)現(xiàn)很多有意義的算法；Blum發(fā)現(xiàn)了著名的算法設(shè)計技術(shù)——分支限界法……算法是計算機科學的基石三大學報文章概覽見識算法算法及算法的特性學什么？算法的描述方法1-4-1算法及算法的特性v第一章緒論算法的起源算法的中文名稱出自《周髀算經(jīng)》（西周~秦漢）張倉《九章算術(shù)》創(chuàng)立的機械化算法體系今有三分之一，五分之二。問合之得幾何？答曰：十五分之十一。又有三分之二，七分之四，九分之五。問合之得幾何？答曰：得一、六十三分之五十。又有二分之一，三分之二，四分之三，五分之四。問合之得幾何？答曰：得二、六十分之四十三。合分（分數(shù)相加）術(shù)（算法）曰：母（分母）互乘子（分子），并以為實（被除數(shù)），母相乘為法（除數(shù)），實如（除以）法而一。不滿法者，以法命之，其母同者，直相從（加）之。歐幾里得《幾何原本》創(chuàng)立的邏輯演繹體系世界數(shù)學的兩大體系算法的英文名稱來自于波斯數(shù)學家阿勒·霍瓦里松《代數(shù)對話錄》

（公元825年）Algorithm在Webster'sNewWorldDictionary（1957版）中尚未出現(xiàn)Algorithm——算法；Logarithm——對數(shù)；Algorism——算術(shù)歐幾里得算法被人們認為是史上第一個算法算法的起源張倉《九章算術(shù)》創(chuàng)立的機械化算法體系歐幾里得《幾何原本》創(chuàng)立的邏輯演繹體系世界數(shù)學的兩大體系算法的定義輸入操作步驟：

1.………2.………3.………算法

:是對特定問題求解步驟的一種描述，是指令的有限序列算法不是問題的答案，而是解決問題的操作步驟1.柿子切塊，雞蛋加適量鹽攪拌2.鍋里放油3.把雞蛋倒進去炒熟4.加入蔥花5.把柿子放進去放少許鹽和味精6.翻炒幾下出鍋裝盤木須柿子的做法：輸出算法的操作步驟應(yīng)該滿足什么要求？（1）有窮性：總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成每一條指令都不是無限循環(huán)！有窮不是數(shù)學意義上的概念！算法的特性輸入操作步驟：

1.………2.………3.………輸出（1）有窮性：總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成（2）確定性：每一條指令必須有確切的含義，相同的輸入得到相同的輸出上下文無關(guān)算法的操作步驟應(yīng)該滿足什么要求？算法的特性輸入操作步驟：

1.………2.………3.………輸出（3）可行性：操作步驟可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)（1）有窮性：總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成（2）確定性：每一條指令必須有確切的含義，相同的輸入得到相同的輸出機器可執(zhí)行算法的操作步驟應(yīng)該滿足什么要求？算法的特性輸入操作步驟：

1.………2.………3.………輸出步驟1：找出

m的所有質(zhì)因子步驟2：找出

n的所有質(zhì)因子步驟3：從第1步和第2步得到的質(zhì)因子中找出所有公因子步驟4：將找到的所有公因子相乘，結(jié)果即為

m和

n的最大公約數(shù)【想法】將這兩個自然數(shù)分別進行質(zhì)因數(shù)分解，然后找出所有公因子并將這些公因子相乘。例如，48=2×2×2×2×3，36=2×2×3×3，公因子有2、2、3，因此，48和36的最大公約數(shù)為2×2×3=12。例1-12設(shè)計算法求兩個自然數(shù)的最大公約數(shù)?！舅惴ā吭O(shè)兩個自然數(shù)是m和n，算法如下：滿足算法的特性嗎？如何找出所有質(zhì)因子？如何找出所有公因子？質(zhì)因數(shù)分解尚未找到多項式時間算法不滿足確定性、有窮性！算法的特性好算法的特性（1）正確性：算法能滿足具體問題的需求，即對于任何合法的輸入，算法都會得出正確的結(jié)果。一個算法滿足什么特性才能稱之為好算法呢？（4）抽象分級：用合適的抽象分級組織表達算法的思想，

啟發(fā)式規(guī)則7±2。（2）健壯性：算法對非法輸入的抵抗能力，即對于錯誤的輸入，算法應(yīng)能識別并做出處理，而不是產(chǎn)生錯誤動作或陷入癱瘓。（3）可理解性：算法容易理解和實現(xiàn)。（5）高效性：具有較短的執(zhí)行時間并占用較少的輔助空間。米勒原則：人類的短期記憶能力一般限于一次記憶

5～9

個對象1-4-2算法的描述方法v第一章緒論歐幾里得算法輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））m

n

r35252510105【想法——基本思路】設(shè)兩個自然數(shù)為m和

n，歐幾里得算法的基本思想是將

m和

n輾轉(zhuǎn)相除直到余數(shù)為01050自然語言描述算法【算法——自然語言描述】設(shè)兩個自然數(shù)為m和

n，歐幾里得算法如下：步驟1：將m除以n得到余數(shù)r；步驟2：若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行步驟3；步驟3：將n的值放在m中，將r的值放在n中，重新執(zhí)行步驟1；優(yōu)點：容易理解；缺點：冗長、二義性使用方法：粗線條描述算法思想；注意事項：避免寫成自然段輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））流程圖描述算法優(yōu)點：流程直觀缺點：缺少嚴密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次【算法——流程圖描述】設(shè)兩個自然數(shù)為m和

n，算法為開始結(jié)束r=m%nr=0m=nn=r輸出nY輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））程序語言描述算法【算法——程序語言描述】設(shè)兩個自然數(shù)為m和

n，算法為優(yōu)點：能由計算機執(zhí)行缺點：抽象性差，對語言要求高使用方法：算法需要驗證注意事項：將算法寫成子函數(shù)輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））偽代碼描述算法什么是偽代碼呢？偽代碼：介于自然語言和程序設(shè)計語言之間的方法，它采用某一程序設(shè)計語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計。偽代碼有標準嗎？偽代碼不是一種實際的編程語言，但在表達能力上類似于編程語言，同時極小化了描述算法的不必要的技術(shù)細節(jié)偽代碼被稱為“算法語言”或“第一語言”【算法——偽代碼描述】設(shè)兩個自然數(shù)為m和

n，算法為優(yōu)點：表達能力強，抽象性強，

容易理解，容易實現(xiàn)使用方法：7±2偽代碼描述算法輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））米勒原則：人類的短期記憶能力一般限于一次記憶

5～9

個對象輸入：兩個自然數(shù)m和n輸出：m和n的最大公約數(shù)1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}只描述子函數(shù)；省略主函數(shù)和頭函數(shù)偽代碼描述算法輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））【算法——偽代