算法算法1一.算法的基本概念1什么是算法算法（algorithm）一詞源于算術(algorism),算術方法的原義是一個由已知推求未知的運算過程。后來，人們把它推廣到一般,指算法是在有限步驟內求解某一問題所使用的一組定義明確的規則,甚至把把進行某一工作的方法和步驟也稱為算法。

一.算法的基本概念1什么是算法

2例如，人們在計算過程中，先乘除，后加減，從內到外去括號等規則，都是按部就班必須遵守的算法。人類最早關于算法的記錄存在于在兩河流域發現的公元前兩三千年的泥板書上，其中的一個典型例子就是計算利息何時能夠夠等于本金。算法早期發展中值得一提的另一個成果應歸功于古希臘的歐幾里得，他提出的計算最大公約數的輾轉相除法（又稱歐幾里得算法）至今仍在使用。例如，人們在計算過程中，先乘除，后加減，從內到外去括號等規則3歐幾里得是古代最有名望的學者之一，古希臘數學家，幾何學的鼻祖。公元前300年左右，他所著《幾何原本》13卷，是世界上最早公理化的數學著作。在《幾何原本》中他充分總結了前人的生產經驗和研究成果，從公理和公設出發，運用演繹法，經過邏輯推理和數學運算，創立了著名的歐幾里得（簡稱歐氏幾何）。在《幾何原本》中，歐幾里得還闡述了關于求兩個整數的最大公約數的過程，這就是著名的歐幾里得算法——輾轉相除法，其具體過程如下：歐幾里得是古代最有名望的學者之一，古希臘數學家，幾何學的鼻祖4設給定的兩個正整數為m和n，求它們的最大公約數的步驟為：（1）以m除以n，令所得的余數為r（r必小于n）；（2）若r＝0，則輸出結果n，算法結束；否則，繼續步驟（3)（3）令m=n，n=r,并返回步驟（1）繼續進行。設給定的兩個正整數為m和n，求它們的最大公約數的步驟為：（15中國古代數學研究中也有許多有關算法的成果。用我國傳統的開方術求高次方程的近似根，是算法上的一大成就。此外,在社會上得到廣泛使用的珠算口訣就可以看做是典型的算法,它把復雜的計算(例如除法)描述為一系列按口訣執行的簡單的算珠撥動操作。中國古代數學以算法為主要特征，其中最具代表性的就是《九章算術》。中國古代數學研究中也有許多有關算法的成果。用我國傳統的開方術6《九章算術》是戰國、秦、漢時期數學發展的總結，就其數學成就來說，堪稱是世界數學名著。其內容按類分章，以數學問題的形式出現，包括分數四則運算、開平方與開立方（包括二次方程數值解法）、盈不足術、各種面積和體積公式、線性方程組解法、正負數運算的加減法則、勾股形解法（特別是勾股定理和求勾股數的方法）等。其中方程組解法和正負數加減法則在世界數學發展上是遙遙領先的。就其特點來說，它形成了一個以籌算為中心，與古希臘數學完全不同的獨立體系。

《九章算術》是戰國、秦、漢時期數學發展的總結，就其數學成就來7在11~14世紀約300年期間著名的數學家的著作中，如賈憲的《黃帝九章算法細草》，劉益的《議古根源》，秦九昭的《數書九章》，李治的《測圓海鏡》和《益古演段》，楊輝的《詳解九章算法》、《日用算法》和《楊輝算法》中，算法的特點得到了進一步的強化和發展（其中包括發展了一套求高次方程近似根的方法。在11~14世紀約300年期間著名的數學家的著作中，如賈憲的82。算法的一般特征

算法實際上是一種抽象的解題方法，它具有動態性。因此，算法的行為非常重要。作為一個算法，應具有以下四個特征。1）能行性(effectiveness）算法的能行性包括兩個方面：一是算法中的每一個步驟必須是能實現的。例如，在算法中，不允許出現分母為零的情況；在實數范圍內不能求一個負數的平方根等。二是算法執行的結果要能達到預期的目的。通常，針對實際問題設計的算法，人們總是希望能夠得到滿意的結果。

2。算法的一般特征1）能行性(effectiveness）9（2）確定性(definiteness）算法的確定性，是指算法中的每一個步驟都必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。這一特征也反映了算法與數學公式的明顯差異。在解決實際問題時，可能會出現這樣的情況：針對某種特特殊問題，數學公式是正確的，但按此數學公式設計的計算過程可能會使計算機系統無所適從，這是因為，根據數學公式設計的計算過程只考慮了正常使用的情況，而當出現異常情況時，該計算過程就不能適應了。（2）確定性(definiteness）10例如，某計算工具規定：大于100的數認為是比1大很多，而小于10的數不能認為是比1大很多；且在正常情況下出現的數或是大于100,或是小于10.但指令“輸入一個X，若x比1大很多，則輸出數字1，否則輸出數字0”是不確定的。這是因為，在正常的輸入情況下，這一指令的執行可以得到正確的結果，但在異常情況下（輸入的x在10與100之間），這一指令執行的結果就不確定了．例如，某計算工具規定：大于100的數認為是比1大很多，而小于11例如，某計算工具具有七位有效數字（如FORTRAN中的單精度運算）,在計算下列三個量A＝，B＝1，C＝的和時，如果采用不同的運算順序，就會得到不同的結果，即A＋B＋C=＋1＋=0A＋C十B=＋＋1=1而在數學上，A+B+C與A+C+B是完全等價的。這可知，算法和計算公式是有差別的。例如，某計算工具具有七位有效數字（如FORTRAN中的單精度123）有窮性(finiteness）算法的有窮性是指算法必須能在有限的時間內執行完，即算法必須能在執行有限個步驟之后終止。數學中的無窮級數，在實際計算時只能取有限項，即計算無窮級數的過程只能是有窮的。因此，一個數的無窮級數的表示只是一種計算公式，而根據精度要求確定的計算過程才是有窮的算法。3）有窮性(finiteness）13算法的有窮性還應包括合理的執行時間的含義。如果一個算法的執行時間是有窮的，但卻需要執行千萬年．顯然這就失去了算法的實用價值。例如，克萊姆(Cramer)規則是求解線性代數方程組的一種數學方法，但不能以此為算法，這是因為，雖然總可以根據克萊姆規則設計出一個計算過程用于計算所有可能出現的行列式，但這樣的計算過程所需的時間實際上是不能容忍的。算法的有窮性還應包括合理的執行時間的含義。如果一個算法的執行14還例如，從理論上講，總可以寫出一個正確的弈棋程序，而且這也并不是一件很困難的工作。由于在一個棋盤上安排棋子的方式總是有限的，而且，根據一定的規則．在有限次移動棋子之后比賽一定結束。因此．弈棋程序可以考慮計算機每一次可能的移動，它的對手每一次可能的應答，以及計算機對這些移動的可能應答等等，直到每個可能的移動停止下來為止。此外，由于計算機可以知道每次移動的結果，因此總可以選擇一種最好的移動方式。但即使如此，這種弈棋程序還是不可能執行，因為所有這些可能移動的次數太多，所要花費的時間不能容忍。由上述兩個例子可以看出，雖然許多計算過程是有限的．但仍有可能無實用價值。還例如，從理論上講，總可以寫出一個正確的弈棋程序，而且這也并15（4）算法必須擁有足夠的情報一個算法是否有效，還取決于為算法的執行所提供的情報是否足夠。例如，對于指令“如果小明是學生，則輸出字母Y，否則輸出N”。當算法執行過程中提供了小明一定不是學生的某種信息時，執行的結果將輸出字母N；當提供的只是部分學生的名單，且小明恰在此名單之中，則執行的結果將輸出字母Y。但如果在提供的部分學生的名單中找不到小明的名字．則在執行該指令時無法確定小明是否是學生。（4）算法必須擁有足夠的情報16通常，算法中的各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態．這是算法執行的起點或是依據。因此，一個算法執行的結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。如果輸入不夠或輸入錯誤，則算法本身也就無法執行或執行有錯。一般來說，只有當算法擁有足夠的情報時，該算法才是有效的；而如果提供的情報不夠，則算法并不是有效的。通常，算法中的各種運算總是要施加到各個運算對象上，而這些運算17綜上所述，所謂算法，是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的且是明確的，此順序將在有限的次數下終止綜上所述，所謂算法，是一組嚴謹地定義運算順序的規則，并且每一181.1.2程序框圖1.1.2程序框圖19狹義而言,算法是專指用計算機解決某一問題的方法和步驟.著名計算機科學家D.E.Knuth在其《計算機程序設計技巧》一書中為算法所下的定義是：“一個算法,就是一個有窮規則的集合,其中之規則規定了一個解決某一特定類型問題的運算系列”.1.算法的概念復習回顧

是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的且是明確的，此順序將在有限的次數下終止。狹義而言,算法是專指用計算機解決某一問題20用自然語言表達問題容易理解，但往往不嚴格，易出現“歧義性”，即對于同一段文字，不同的人可能會有不同的理解。例如請同學們理解“這個人連老張也不認識。”這句話的含義。算法的描述：自然語言用自然語言表達問題容易理解，但往往不嚴格，易出現“歧義性”，21新課引入為了使算法的程序或步驟表達得更為直觀,且不容易出現歧異，我們更經常地用圖形方式來表達它.例如上一節“例1.任意給定一個大于1的整數n,試設計一個程序或步驟對n是否為質數做出判定”的算法可以用以下形式來表達.新課引入為了使算法的程序或步驟表達得更為直觀,且不容易出現歧22開始輸入ni=2i=i+1i≥n或r=0?n不是質數結束r=0?1否是求n除以i的余數1n是質數是否這樣的圖我們稱為程序框圖開始輸入ni=2i=i+1i≥n或r=0?n不是質數結束r=23i=i+1i≥n或r=0?否是求n除以i的余數輸入ni=2n不是質數r=0?n是質數是否盡管不同的算法千差萬別,但它們都是由三種基本的邏輯結構構成的,這三種邏輯結構就是順序結構、選擇結構、循環結構.下面分別介紹這三種結構．三種不同的邏輯結構.i=i+1i≥n或r=0?否是求n除以i輸入ni=2n不是質24程序框圖又稱流程圖,是一種用規定的圖形、指向線及文字說明來準確、直觀地表示算法的圖形.講授新課1.程序框圖的概念2.常見的程序框圖流程線連接循環框連結點連接循環框圖的兩部分一、程序框圖程序框圖又稱流程圖,是一種用規定的圖形、指向25終端框(起止框)輸入、輸出框處理框(執行框)判斷框表示一個算法的起始和結束表示一個算法輸入和輸出的信息賦值、計算判斷某一條件是否成立,成立時在出口處標明“是”或“Y”,不成立時標明“否”或“N”.終端框輸入、處理框判斷框表示一個算法的表示一個算法輸賦值、計26(1)起止框:框內填寫開始、結束,任何程序框圖中，起止框是必不可少的；(2)輸入、輸出框:框內填寫輸入、輸出的字母、符號等;(3)處理框(執行框):算法中需要的算式、公式、對變量進行賦值等要用執行框表示.(4)判斷框:當算法要求在不同的情況下執行不同的運算時，需要判斷框.框內填寫判斷條件.3.四種基本的框圖及其功能用法:(1)起止框:框內填寫開始、結束,任何程序框圖中，起止框是必27為了使大家彼此之間能夠讀懂各自畫出的框圖,必須遵守一些共同的規則,下面對一些常用的規則作一簡單的介紹.(1)使用標準的框圖符號.(2)框圖一般按從上到下、從左到右的方向畫.(3)除判斷框外，大多數程序框圖符號只有一個進入點和一個退出點，判斷框是具有超過一個退出點的唯一符號.(4)一類判斷框是“是”與“否”兩分支的判斷,而且有且僅有兩個結果;另一類是多分支判斷,有幾種不同的結果.4.畫流程圖的規則為了使大家彼此之間能夠讀懂各自畫出的框圖,必須遵守28(5)在圖形符號內描述的語言要非常簡練清楚.(7)一個程序框圖包括以下幾部分:表示相應操作的程序框;帶箭頭的流程線;程序框外必要的文字說明．(6)起始框只允許一條流出線,終止框只允許一條流入線,輸入框、輸出框、處理框只有一條流入線和一條流出線,判斷框有一條流入線和兩條流出線,但任何時候只有一條流出線起作用.(5)在圖形符號內描述的語言要非常簡練清楚.(7)一個程序框29二、順序結構及框圖表示1.順序結構:按照步驟依次執行的一個算法,稱為具有“順序結構”的算法,或者稱為算法的順序結構.語句A語句B2.順序結構的流程圖

順序結構是最簡單的算法結構,語句與語句之間,框與框之間是按從上到下的順序進行的.它是由若干個處理步驟組成的,這是任何一個算法都離不開的基本結構.二、順序結構及框圖表示1.順序結構:按照步驟依次執行的一個算303.畫順序結構程序框圖時注意事項左圖中,語句Ａ和語句Ｂ是依次執行的,只有在執行完語句Ａ指定的操作后,才能接著執行語句Ｂ所指定的操作．(1)在程序框圖中,開始框和結束框不可少；(2)在算法過程中，第一步輸入語句是必不可少的;(3)順序結構在程序框圖中的體現就是用流程線將程序框自上而下地連接起來,按順序執行算法步驟．3.畫順序結構程序框圖時注意事項左圖中,語句Ａ和語句Ｂ是依次31【例1】已知一個三角形的三邊邊長分別為2,3,4,利用海倫—秦九韶公式設計一個算法,求出它的面積,畫出算法的程序框圖.開始輸出S結束開始框處理框輸出框結束框【例1】已知一個三角形的三邊邊長分別為2,3,4,利用海倫—32【1】求兩個實數a,b的算術平均值aver.S1:輸入兩個實數a,b；S2：計算c=a+b；S3:計算aver=c/2；S4:輸出aver.輸出c開始輸入a,baver=c/2結束解：用自然語言【1】求兩個實數a,b的算術平均值aver.S1:33【2】“雞兔同籠”是我國隋朝時期的數學著作《孫子算經》中的一個有趣而具有深遠影響的題目:“今有雉兔同籠,上有三十五頭,下有九十四足,問雉兔各幾何.”請你設計一個這類問題的通用算法.并畫出算法的程序框圖.設有X只雞,Y只兔.則解:雞兔同籠,設雞兔總頭數為H,總腳數為F,求雞兔各有多少只.算法分析如下：

解方程組,得【2】“雞兔同籠”是我國隋朝時期的數學著作《孫子算經》中的一34第一步:輸入總頭數H,總腳數F；第二步:計算雞的個數x=(4H-F)/2；第三步:計算兔的個數y=(F-2H)/2；第四步:輸出x,y開始輸出X,Y結束X=(4H-F)/2Y=(F-2H)/2輸入H和F解：用自然語言程序框圖第一步:輸入總頭數H,開始輸出X,Y結束X=(4H-F)/35第四步:計算;【3】試描述求點(x0,y0)到直線Ax+By+C=0的距離的算法,并畫出算法的程序框圖.第一步:輸入x0,y0,A,B,C;第二步:計算Z1=Ax0+By0+C;第三步:計算Z2=A2+B2;第五步:輸出d.解：用自然語言第四步:計算;【3】試描述求點(36開始輸入x0,y0,A,B,CZ1=Ax0+By0+CZ2=A2+B2輸出d結束程序框圖開始輸入x0,y0,A,B,CZ1=Ax0+By0+CZ2=37課堂小結2.三種基本結構：順序條件循環結構現以證明,無論多么復雜的問題，其算法都可表示為這三種基本結構的組合.其結構清晰、易于理解、易于驗證其正確性，也易于查錯和排錯.1.算法的描述：(1)自然語言(2)程序框圖:由于圖形的描述方法既形象,又直觀,設計者的思路表達得清楚易懂，便于檢查修改,所以得到廣泛的應用.課堂小結2.三種基本結構：順序條件循環結構1381.2基本算法語句1.2.1輸入語句輸出語句賦值語句1.2基本算法語句1.2.1輸入語句39溫故而知新1.什么是程序框圖？2.算法的基本邏輯結構有哪些？

程序框圖是一中用規定的圖形、指向線及文字說明來準確、直觀的表示算法的圖形。

算法的基本結構有三種：順序結構、條件結構、循環結構，其中循環結構又分為當型結構和直到型結構兩種。溫故而知新1.什么是程序框圖？2.算法的基本邏輯結構有401.計算機能夠"理解"的語言與人的語言有什么區別？

計算機不同于人：人有大腦，可以思考問題，而計算機則不能.用自然語言和程序框圖描述的算法，計算機無法識別，必須轉化為其能理解的語言，即程序語言。2、基本的算法語句有哪些？各自對應怎樣的算法結構？

基本的算法語句有：輸入語句、輸出語句、賦值語句、條件語句、循環語句；輸入語句、輸出語句、賦值語句基本上是對應順序結構，條件語句對應條件結構、循環語句對應循環結構。1.計算機能夠"理解"的語言與人的語言有什么區別？41例１用描點法作函數y=x3+3x2-24x+30的圖象是時，需要求出自變量和函數的一組對應值。編寫程序，分別計算當x=-5,-4,-3,-2,-1,0,1,2,3,4,5時的函數值。程序：INPUT“x=“;xy=x^3+3*x^2-24*x+30PRINTxPRINTyEND算法：開始輸入x輸出x、y結束i=1i=i+1i>11否是例１用描點法作函數y=x3+3x2-24x+30的圖象是時，421、輸入語句的一般格式是：舉例：輸入語、數、英三門課成績或INPUT”Maths,Chinese,English”;a,b,cINPUT“maths”;aINPUT“Chinese”;bINPUT“English”;cINPUT“提示內容”；變量INPUT“提示內容1，提示內容2，提示內容3，…”；變量1，變量2，變量3，…2、輸入語句的作用是：實現算法的輸入信息功能（即對程序中的變量賦值）3、“提示內容”提示用戶輸入什么樣的信息

變量是指程序在運行時其值是可以變化的量；

（一）輸入語句：1、輸入語句的一般格式是：舉例：輸入語、數、英三門課成績或43INPUT“n=”;nINPUT“a,b,c”;a,b,c輸入框：INPUT“請輸入需判斷的整數n=”；n注：①“提示內容”與變量之間必須用分號“；”隔開。②各“提示內容”之間以及各變量之間必須用逗號“，”隔開。但最后的變量的后面不需要。③提示內容和它后面的“；”可省略

④由鍵盤輸入的數據必須是常量，不能是函數、變量或表達式,輸入多個時用“，”分隔，個數與變量個數要相同思考：能用輸入語句表達１．１．２中程序框圖中的輸入框的內容嗎？INPUT“n=”;nINPUT“a,b,c”;a,44輸出語句的一般格式PRINT“提示內容”；表達式輸出語句的作用是實現算法的輸出結果功能；“提示內容”提示用戶輸入什么樣的信息，表達式是指程序要輸出的數據；

輸出語句可以輸出常量、變量或表達式的值以及字符。

（二）輸出語句輸出語句的一般格式PRINT“提示內容”；表達式輸出語45TheFibonacciProgressionis：11235813213455…輸出框：PRINTn；“是質數。”輸出框：PRINTn；“不是質數。”PRINT

“TheFibonacciProgressionis：”；11235813213455“…”此時屏幕上顯示為：〖思考〗：在1.1.2中程序框圖中的輸出框的內容怎樣用輸出語句來表達？TheFibonacciProgressionis：146例2：編寫程序，計算一個學生數學、語文、英語三門課的平均成績。程序算法開始輸入a,b,c結束輸出yINPUT“數學=”;aINPUT“語文=”;bINPUT“英語=”;cPRINT

“Theaverage=”;(a+b+c)/3

END例2：編寫程序，計算一個學生數學、語文、英語三門課的平均成47（三）賦值語句：用來表明賦給某一個變量一個具體的確定值的語句。

變量=表達式賦值語句也可以給變量提供初值。它的一般格式是：其中“=”叫做賦值號。

賦值語句的作用：先計算出賦值號右邊表達式的值，然后把這個值賦給賦值號左邊的變量，使該變量的值等于表達式的值。（三）賦值語句：用來表明賦給某一個變量一個具體的確定值的語句48注：①賦值號左邊只能是變量名字，而不能是表達式;右邊表達式可以是一個數據、常量或算式.如：2=X是錯誤的②賦值號左右不能對換。如“A=B”“B=A”的含義運行結果是不同的。③不能利用賦值語句進行代數式的演算。（如化簡、因式分解、解方程等）④賦值號“=”與數學中的等號意義不同。（5）對于一個變量可以多次賦值。注：①賦值號左邊只能是變量名字，而不能是表達式;右邊表達式49〖例3〗：給一個變量重復賦值。A=10A=A+10PRINT

AEND程序：在此程序的基礎上，設計一個程序，求A的輸出值是

多少？A=10A=A+15PRINT

AA=A+5PRINT

AEND〖例3〗：給一個變量重復賦值。A=10程序：在此程序的基礎上50〖例4〗：交換兩個變量A和B的值，并輸出交換前后的值。分析：引入一個中間變量X,將A的值賦予X,又將B的值賦予A，再將X的值賦予B，從而達到交換A，B的值。（比如交換裝滿水的兩個水桶里的水需要再找一個空桶）INPUT

AINPUT

BPRINT

A，BX=AA=BB=XPRINT

A，BEND程序：

〖例4〗：交換兩個變量A和B的值，并輸出交換前后的值。分析：51例1編寫程序，計算一個學生語文、數學、英語三門課程的總成績和平均成績，并輸出。開始輸入數學a輸入語文b輸入英語c總分s=a+b+c平均p=s/3輸出總分s輸出平均分p結束程序：INPUT“Maths=”;aINPUT“Chinese=”;bINPUT“Enghlish=”;cs=a+b+cp=s/3PRINT“sum=”;sPRINT“Theaverage=”;pEND程序框圖：INPUT“Maths,Chinese,English”;a,b,cS=a+b+cP=(a+b+c)/3PRINT“sum=”;sPRINT“Theaverage=”;pEND例1編寫程序，計算一個學生語文、數學、英語三門課程的總成52若三角形的三邊分別是a，b，c，借助三角型面積公式（海倫-秦九韶公式）編寫一個求三角形面積的程序。程序：INPUT“a,b,c=”;a,b,cp=(a+b+c)/2S=SQR(p*(p-a)*(p-b)*(p-c))PRINT“三角形面積S=”;SEND練習程序框圖：開始輸出s結束若三角形的三邊分別是a，b，c，借助三角型面積公式編寫一個求53〖練習〗：編寫一個程序，要求輸入一個圓的半徑，便能輸出該圓的周長和面積。（PI=3.14)INPUT“半徑為R=”；RC=2*3.14*RS=3.14*R^2PRINT“該圓的周長為：”；CPRINT“該圓的面積為：”；SEND分析：設圓的半徑為R，則圓的周長為，面積為可以利用順序結構中的INPUT語句，PRINT語句和賦值語句設計程序。

〖練習〗：編寫一個程序，要求輸入一個圓的半徑，便能輸出該圓的54INPUT“提示內容”;變量PRINT“提示內容”;表達式變量＝表達式可對程序中的變量賦值可輸出表達式的值，計算可對程序中的變量賦值，計算（1）提示內容和它后面的“;”可以省略（2）一個語句可以給多個變量賦值，中間用“,”分隔（3）無計算功能（1）表達式可以是變量，計算公式，或系統信息（2）一個語句可以輸入多個表達式，中間用“,”分隔（3）有計算功能（1）“=”的右側必須是表達式，左側必須是變量（2）一個語句只能給一個變量賦（3）有計算功能INPUT“提示內容”;變量PRINT“提示內容”;表達55【課堂小結】本節課介紹了輸入語句、輸出語句和賦值語句的結構特點及聯系。掌握并應用輸入語句，輸出語句，賦值語句編寫一些簡單的程序解決數學問題，特別是掌握賦值語句中“=”的作用及應用。編程一般的步驟：先寫出算法，再進行編程。我們要養成良好的習慣，也有助于數學邏輯思維的形成。【課堂小結】56課后作業1、設計一個解決以下問題的算法并畫出流程圖：輸入三角形的底和高，計算三角形面積。2、設計一算法：輸入圓的半徑,輸出圓的面積，并畫出流程圖3、鞏固今天所學內容，預習下一節課：條件結構，循環結構課后作業1、設計一個解決以下問題的算法并畫出流程圖：2、設計57算法算法58一.算法的基本概念1什么是算法算法（algorithm）一詞源于算術(algorism),算術方法的原義是一個由已知推求未知的運算過程。后來，人們把它推廣到一般,指算法是在有限步驟內求解某一問題所使用的一組定義明確的規則,甚至把把進行某一工作的方法和步驟也稱為算法。

一.算法的基本概念1什么是算法

59例如，人們在計算過程中，先乘除，后加減，從內到外去括號等規則，都是按部就班必須遵守的算法。人類最早關于算法的記錄存在于在兩河流域發現的公元前兩三千年的泥板書上，其中的一個典型例子就是計算利息何時能夠夠等于本金。算法早期發展中值得一提的另一個成果應歸功于古希臘的歐幾里得，他提出的計算最大公約數的輾轉相除法（又稱歐幾里得算法）至今仍在使用。例如，人們在計算過程中，先乘除，后加減，從內到外去括號等規則60歐幾里得是古代最有名望的學者之一，古希臘數學家，幾何學的鼻祖。公元前300年左右，他所著《幾何原本》13卷，是世界上最早公理化的數學著作。在《幾何原本》中他充分總結了前人的生產經驗和研究成果，從公理和公設出發，運用演繹法，經過邏輯推理和數學運算，創立了著名的歐幾里得（簡稱歐氏幾何）。在《幾何原本》中，歐幾里得還闡述了關于求兩個整數的最大公約數的過程，這就是著名的歐幾里得算法——輾轉相除法，其具體過程如下：歐幾里得是古代最有名望的學者之一，古希臘數學家，幾何學的鼻祖61設給定的兩個正整數為m和n，求它們的最大公約數的步驟為：（1）以m除以n，令所得的余數為r（r必小于n）；（2）若r＝0，則輸出結果n，算法結束；否則，繼續步驟（3)（3）令m=n，n=r,并返回步驟（1）繼續進行。設給定的兩個正整數為m和n，求它們的最大公約數的步驟為：（162中國古代數學研究中也有許多有關算法的成果。用我國傳統的開方術求高次方程的近似根，是算法上的一大成就。此外,在社會上得到廣泛使用的珠算口訣就可以看做是典型的算法,它把復雜的計算(例如除法)描述為一系列按口訣執行的簡單的算珠撥動操作。中國古代數學以算法為主要特征，其中最具代表性的就是《九章算術》。中國古代數學研究中也有許多有關算法的成果。用我國傳統的開方術63《九章算術》是戰國、秦、漢時期數學發展的總結，就其數學成就來說，堪稱是世界數學名著。其內容按類分章，以數學問題的形式出現，包括分數四則運算、開平方與開立方（包括二次方程數值解法）、盈不足術、各種面積和體積公式、線性方程組解法、正負數運算的加減法則、勾股形解法（特別是勾股定理和求勾股數的方法）等。其中方程組解法和正負數加減法則在世界數學發展上是遙遙領先的。就其特點來說，它形成了一個以籌算為中心，與古希臘數學完全不同的獨立體系。

《九章算術》是戰國、秦、漢時期數學發展的總結，就其數學成就來64在11~14世紀約300年期間著名的數學家的著作中，如賈憲的《黃帝九章算法細草》，劉益的《議古根源》，秦九昭的《數書九章》，李治的《測圓海鏡》和《益古演段》，楊輝的《詳解九章算法》、《日用算法》和《楊輝算法》中，算法的特點得到了進一步的強化和發展（其中包括發展了一套求高次方程近似根的方法。在11~14世紀約300年期間著名的數學家的著作中，如賈憲的652。算法的一般特征

算法實際上是一種抽象的解題方法，它具有動態性。因此，算法的行為非常重要。作為一個算法，應具有以下四個特征。1）能行性(effectiveness）算法的能行性包括兩個方面：一是算法中的每一個步驟必須是能實現的。例如，在算法中，不允許出現分母為零的情況；在實數范圍內不能求一個負數的平方根等。二是算法執行的結果要能達到預期的目的。通常，針對實際問題設計的算法，人們總是希望能夠得到滿意的結果。

2。算法的一般特征1）能行性(effectiveness）66（2）確定性(definiteness）算法的確定性，是指算法中的每一個步驟都必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。這一特征也反映了算法與數學公式的明顯差異。在解決實際問題時，可能會出現這樣的情況：針對某種特特殊問題，數學公式是正確的，但按此數學公式設計的計算過程可能會使計算機系統無所適從，這是因為，根據數學公式設計的計算過程只考慮了正常使用的情況，而當出現異常情況時，該計算過程就不能適應了。（2）確定性(definiteness）67例如，某計算工具規定：大于100的數認為是比1大很多，而小于10的數不能認為是比1大很多；且在正常情況下出現的數或是大于100,或是小于10.但指令“輸入一個X，若x比1大很多，則輸出數字1，否則輸出數字0”是不確定的。這是因為，在正常的輸入情況下，這一指令的執行可以得到正確的結果，但在異常情況下（輸入的x在10與100之間），這一指令執行的結果就不確定了．例如，某計算工具規定：大于100的數認為是比1大很多，而小于68例如，某計算工具具有七位有效數字（如FORTRAN中的單精度運算）,在計算下列三個量A＝，B＝1，C＝的和時，如果采用不同的運算順序，就會得到不同的結果，即A＋B＋C=＋1＋=0A＋C十B=＋＋1=1而在數學上，A+B+C與A+C+B是完全等價的。這可知，算法和計算公式是有差別的。例如，某計算工具具有七位有效數字（如FORTRAN中的單精度693）有窮性(finiteness）算法的有窮性是指算法必須能在有限的時間內執行完，即算法必須能在執行有限個步驟之后終止。數學中的無窮級數，在實際計算時只能取有限項，即計算無窮級數的過程只能是有窮的。因此，一個數的無窮級數的表示只是一種計算公式，而根據精度要求確定的計算過程才是有窮的算法。3）有窮性(finiteness）70算法的有窮性還應包括合理的執行時間的含義。如果一個算法的執行時間是有窮的，但卻需要執行千萬年．顯然這就失去了算法的實用價值。例如，克萊姆(Cramer)規則是求解線性代數方程組的一種數學方法，但不能以此為算法，這是因為，雖然總可以根據克萊姆規則設計出一個計算過程用于計算所有可能出現的行列式，但這樣的計算過程所需的時間實際上是不能容忍的。算法的有窮性還應包括合理的執行時間的含義。如果一個算法的執行71還例如，從理論上講，總可以寫出一個正確的弈棋程序，而且這也并不是一件很困難的工作。由于在一個棋盤上安排棋子的方式總是有限的，而且，根據一定的規則．在有限次移動棋子之后比賽一定結束。因此．弈棋程序可以考慮計算機每一次可能的移動，它的對手每一次可能的應答，以及計算機對這些移動的可能應答等等，直到每個可能的移動停止下來為止。此外，由于計算機可以知道每次移動的結果，因此總可以選擇一種最好的移動方式。但即使如此，這種弈棋程序還是不可能執行，因為所有這些可能移動的次數太多，所要花費的時間不能容忍。由上述兩個例子可以看出，雖然許多計算過程是有限的．但仍有可能無實用價值。還例如，從理論上講，總可以寫出一個正確的弈棋程序，而且這也并72（4）算法必須擁有足夠的情報一個算法是否有效，還取決于為算法的執行所提供的情報是否足夠。例如，對于指令“如果小明是學生，則輸出字母Y，否則輸出N”。當算法執行過程中提供了小明一定不是學生的某種信息時，執行的結果將輸出字母N；當提供的只是部分學生的名單，且小明恰在此名單之中，則執行的結果將輸出字母Y。但如果在提供的部分學生的名單中找不到小明的名字．則在執行該指令時無法確定小明是否是學生。（4）算法必須擁有足夠的情報73通常，算法中的各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態．這是算法執行的起點或是依據。因此，一個算法執行的結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。如果輸入不夠或輸入錯誤，則算法本身也就無法執行或執行有錯。一般來說，只有當算法擁有足夠的情報時，該算法才是有效的；而如果提供的情報不夠，則算法并不是有效的。通常，算法中的各種運算總是要施加到各個運算對象上，而這些運算74綜上所述，所謂算法，是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的且是明確的，此順序將在有限的次數下終止綜上所述，所謂算法，是一組嚴謹地定義運算順序的規則，并且每一751.1.2程序框圖1.1.2程序框圖76狹義而言,算法是專指用計算機解決某一問題的方法和步驟.著名計算機科學家D.E.Knuth在其《計算機程序設計技巧》一書中為算法所下的定義是：“一個算法,就是一個有窮規則的集合,其中之規則規定了一個解決某一特定類型問題的運算系列”.1.算法的概念復習回顧

是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的且是明確的，此順序將在有限的次數下終止。狹義而言,算法是專指用計算機解決某一問題77用自然語言表達問題容易理解，但往往不嚴格，易出現“歧義性”，即對于同一段文字，不同的人可能會有不同的理解。例如請同學們理解“這個人連老張也不認識。”這句話的含義。算法的描述：自然語言用自然語言表達問題容易理解，但往往不嚴格，易出現“歧義性”，78新課引入為了使算法的程序或步驟表達得更為直觀,且不容易出現歧異，我們更經常地用圖形方式來表達它.例如上一節“例1.任意給定一個大于1的整數n,試設計一個程序或步驟對n是否為質數做出判定”的算法可以用以下形式來表達.新課引入為了使算法的程序或步驟表達得更為直觀,且不容易出現歧79開始輸入ni=2i=i+1i≥n或r=0?n不是質數結束r=0?1否是求n除以i的余數1n是質數是否這樣的圖我們稱為程序框圖開始輸入ni=2i=i+1i≥n或r=0?n不是質數結束r=80i=i+1i≥n或r=0?否是求n除以i的余數輸入ni=2n不是質數r=0?n是質數是否盡管不同的算法千差萬別,但它們都是由三種基本的邏輯結構構成的,這三種邏輯結構就是順序結構、選擇結構、循環結構.下面分別介紹這三種結構．三種不同的邏輯結構.i=i+1i≥n或r=0?否是求n除以i輸入ni=2n不是質81程序框圖又稱流程圖,是一種用規定的圖形、指向線及文字說明來準確、直觀地表示算法的圖形.講授新課1.程序框圖的概念2.常見的程序框圖流程線連接循環框連結點連接循環框圖的兩部分一、程序框圖程序框圖又稱流程圖,是一種用規定的圖形、指向82終端框(起止框)輸入、輸出框處理框(執行框)判斷框表示一個算法的起始和結束表示一個算法輸入和輸出的信息賦值、計算判斷某一條件是否成立,成立時在出口處標明“是”或“Y”,不成立時標明“否”或“N”.終端框輸入、處理框判斷框表示一個算法的表示一個算法輸賦值、計83(1)起止框:框內填寫開始、結束,任何程序框圖中，起止框是必不可少的；(2)輸入、輸出框:框內填寫輸入、輸出的字母、符號等;(3)處理框(執行框):算法中需要的算式、公式、對變量進行賦值等要用執行框表示.(4)判斷框:當算法要求在不同的情況下執行不同的運算時，需要判斷框.框內填寫判斷條件.3.四種基本的框圖及其功能用法:(1)起止框:框內填寫開始、結束,任何程序框圖中，起止框是必84為了使大家彼此之間能夠讀懂各自畫出的框圖,必須遵守一些共同的規則,下面對一些常用的規則作一簡單的介紹.(1)使用標準的框圖符號.(2)框圖一般按從上到下、從左到右的方向畫.(3)除判斷框外，大多數程序框圖符號只有一個進入點和一個退出點，判斷框是具有超過一個退出點的唯一符號.(4)一類判斷框是“是”與“否”兩分支的判斷,而且有且僅有兩個結果;另一類是多分支判斷,有幾種不同的結果.4.畫流程圖的規則為了使大家彼此之間能夠讀懂各自畫出的框圖,必須遵守85(5)在圖形符號內描述的語言要非常簡練清楚.(7)一個程序框圖包括以下幾部分:表示相應操作的程序框;帶箭頭的流程線;程序框外必要的文字說明．(6)起始框只允許一條流出線,終止框只允許一條流入線,輸入框、輸出框、處理框只有一條流入線和一條流出線,判斷框有一條流入線和兩條流出線,但任何時候只有一條流出線起作用.(5)在圖形符號內描述的語言要非常簡練清楚.(7)一個程序框86二、順序結構及框圖表示1.順序結構:按照步驟依次執行的一個算法,稱為具有“順序結構”的算法,或者稱為算法的順序結構.語句A語句B2.順序結構的流程圖

順序結構是最簡單的算法結構,語句與語句之間,框與框之間是按從上到下的順序進行的.它是由若干個處理步驟組成的,這是任何一個算法都離不開的基本結構.二、順序結構及框圖表示1.順序結構:按照步驟依次執行的一個算873.畫順序結構程序框圖時注意事項左圖中,語句Ａ和語句Ｂ是依次執行的,只有在執行完語句Ａ指定的操作后,才能接著執行語句Ｂ所指定的操作．(1)在程序框圖中,開始框和結束框不可少；(2)在算法過程中，第一步輸入語句是必不可少的;(3)順序結構在程序框圖中的體現就是用流程線將程序框自上而下地連接起來,按順序執行算法步驟．3.畫順序結構程序框圖時注意事項左圖中,語句Ａ和語句Ｂ是依次88【例1】已知一個三角形的三邊邊長分別為2,3,4,利用海倫—秦九韶公式設計一個算法,求出它的面積,畫出算法的程序框圖.開始輸出S結束開始框處理框輸出框結束框【例1】已知一個三角形的三邊邊長分別為2,3,4,利用海倫—89【1】求兩個實數a,b的算術平均值aver.S1:輸入兩個實數a,b；S2：計算c=a+b；S3:計算aver=c/2；S4:輸出aver.輸出c開始輸入a,baver=c/2結束解：用自然語言【1】求兩個實數a,b的算術平均值aver.S1:90【2】“雞兔同籠”是我國隋朝時期的數學著作《孫子算經》中的一個有趣而具有深遠影響的題目:“今有雉兔同籠,上有三十五頭,下有九十四足,問雉兔各幾何.”請你設計一個這類問題的通用算法.并畫出算法的程序框圖.設有X只雞,Y只兔.則解:雞兔同籠,設雞兔總頭數為H,總腳數為F,求雞兔各有多少只.算法分析如下：

解方程組,得【2】“雞兔同籠”是我國隋朝時期的數學著作《孫子算經》中的一91第一步:輸入總頭數H,總腳數F；第二步:計算雞的個數x=(4H-F)/2；第三步:計算兔的個數y=(F-2H)/2；第四步:輸出x,y開始輸出X,Y結束X=(4H-F)/2Y=(F-2H)/2輸入H和F解：用自然語言程序框圖第一步:輸入總頭數H,開始輸出X,Y結束X=(4H-F)/92第四步:計算;【3】試描述求點(x0,y0)到直線Ax+By+C=0的距離的算法,并畫出算法的程序框圖.第一步:輸入x0,y0,A,B,C;第二步:計算Z1=Ax0+By0+C;第三步:計算Z2=A2+B2;第五步:輸出d.解：用自然語言第四步:計算;【3】試描述求點(93開始輸入x0,y0,A,B,CZ1=Ax0+By0+CZ2=A2+B2輸出d結束程序框圖開始輸入x0,y0,A,B,CZ1=Ax0+By0+CZ2=94課堂小結2.三種基本結構：順序條件循環結構現以證明,無論多么復雜的問題，其算法都可表示為這三種基本結構的組合.其結構清晰、易于理解、易于驗證其正確性，也易于查錯和排錯.1.算法的描述：(1)自然語言(2)程序框圖:由于圖形的描述方法既形象,又直觀,設計者的思路表達得清楚易懂，便于檢查修改,所以得到廣泛的應用.課堂小結2.三種基本結構：順序條件循環結構1951.2基本算法語句1.2.1輸入語句輸出語句賦值語句1.2基本算法語句1.2.1輸入語句96溫故而知新1.什么是程序框圖？2.算法的基本邏輯結構有哪些？

程序框圖是一中用規定的圖形、指向線及文字說明來準確、直觀的表示算法的圖形。

算法的基本結構有三種：順序結構、條件結構、循環結構，其中循環結構又分為當型結構和直到型結構兩種。溫故而知新1.什么是程序框圖？2.算法的基本邏輯結構有971.計算機能夠"理解"的語言與人的語言有什么區別？

計算機不同于人：人有大腦，可以思考問題，而計算機則不能.用自然語言和程序框圖描述的算法，計算機無法識別，必須轉化為其能理解的語言，即程序語言。2、基本的算法語句有哪些？各自對應怎樣的算法結構？

基本的算法語句有：輸入語句、輸出語句、賦值語句、條件語句、循環語句；輸入語句、輸出語句、賦值語句基本上是對應順序結構，條件語句對應條件結構、循環語句對應循環結構。1.計算機能夠"理解"的語言與人的語言有什么區別？98例１用描點法作函數y=x3+3x2-24x+30的圖象是時，需要求出自變量和函數的一組對應值。編寫程序，分別計算當x=-5,-4,-3,-2,-1,0,1,2,3,4,5時的函數值。程序：INPUT“x=“;xy=x^3+3*x^2-24*x+30PRINTxPRINTyEND算法：開始輸入x輸出x、y結束i=1i=i+1i>11否是例１用描點法作函數y=x3+3x2-24x+30的圖象是時，991、輸入語句的一般格式是：舉例：輸入語、數、英三門課成績或INPUT”Maths,Chinese,English”;a,b,cINPUT“maths”;aINPUT“Chinese”;bINPUT“English”;cINPUT“提示內容”；變量INPUT“提示內容1，提示內容2，提示內容3，…”；變量1，變量2，變量3，…2、輸入語句的作用是：實現算法的輸入信息功能（即對程序中的變量賦值）3、“提示內容”提示用戶輸入什么樣的信息

變量是指程序在運行時其值是可以變化的量；

（一）輸入語句：1、輸入語句的一般格式是：舉例：輸入語、數、英三門課成績或100INPUT“n=”;nINPUT“a,b,c”;a,b,c輸入框：INPUT“請輸入需判斷的整數n=”；n注：①“提示內容”與變量之間必須用分號“；”隔開。②各“提示內容”之間以及各變量之間必須用逗號“，”隔開。但最后的變量的后面不需要。③提示內容和它后面的“；”可省略

④由鍵盤輸入的數據必須是常量，不能是函數、變量或表達式,輸入多個時用“，”分隔，個數與變量個數要相同思考：能用輸入語句表達１．１．２中程序框圖中的輸入框的內容嗎？INPUT“n=”;nINPUT“a,b,c”;a,101輸出語句的一般格式PRINT“提示內容”；表達式輸出語句的作用是實現算法的輸出結果功能；“提示內容”提示用戶輸入什么樣的信息，表達式是指程序要輸出的數據；

輸出語句可以輸出常量、變量或表達式的值以及字符。

（二）輸出語句輸出語句的一般格式PRINT“提示內容”；表達式輸出語102TheFibonacciProgressionis：11235813213455…輸出框：PRINTn；“是質數。”輸出框：PRINTn；“不是質數。”PRINT

“TheFibonacciProgressionis：”；11235813213455“…”此時屏幕上顯示為：〖思考〗：在1.1.2中程序框圖中的輸出框的內容怎樣用輸出語句來表達？TheFibonacciProgressionis：1103例2：編寫程序，計算一個學生數學、語文、英語三門課的平均成績。程序算法開始輸入a,b,c結束輸出yINPUT“數學=”;aINPUT“語文