第一章算法初步

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

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

在11~14世紀約300年期間著名的數(shù)學(xué)家的著作中，如賈憲的《黃帝九章算法細草》，劉益的《議古根源》，秦九昭的《數(shù)書九章》，李治的《測圓海鏡》和《益古演段》，楊輝的《詳解九章算法》、《日用算法》和《楊輝算法》中，算法的特點得到了進一步的強化和發(fā)展（其中包括發(fā)展了一套求高次方程近似根的方法。2。算法的一般特征

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

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

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

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

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

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

算法的基本結(jié)構(gòu)有三種：順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，其中循環(huán)結(jié)構(gòu)又分為當(dāng)型結(jié)構(gòu)和直到型結(jié)構(gòu)兩種。1.計算機能夠"理解"的語言與人的語言有什么區(qū)別？

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

基本的算法語句有：輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句；輸入語句、輸出語句、賦值語句基本上是對應(yīng)順序結(jié)構(gòu)，條件語句對應(yīng)條件結(jié)構(gòu)、循環(huán)語句對應(yīng)循環(huán)結(jié)構(gòu)。例１用描點法作函數(shù)y=x3+3x2-24x+30的圖象是時，需要求出自變量和函數(shù)的一組對應(yīng)值。編寫程序，分別計算當(dāng)x=-5,-4,-3,-2,-1,0,1,2,3,4,5時的函數(shù)值。程序：INPUT“x=“;xy=x^3+3*x^2-24*x+30PRINTxPRINTyEND算法：開始輸入x輸出x、y結(jié)束i=1i=i+1i>11否是1、輸入語句的一般格式是：舉例：輸入語、數(shù)、英三門課成績或INPUT”Maths,Chinese,English”;a,b,cINPUT“maths”;aINPUT“Chinese”;bINPUT“English”;cINPUT“提示內(nèi)容”；變量INPUT“提示內(nèi)容1，提示內(nèi)容2，提示內(nèi)容3，…”；變量1，變量2，變量3，…2、輸入語句的作用是：實現(xiàn)算法的輸入信息功能（即對程序中的變量賦值）3、“提示內(nèi)容”提示用戶輸入什么樣的信息

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

（一）輸入語句：INPUT“n=”;nINPUT“a,b,c”;a,b,c輸入框：INPUT“請輸入需判斷的整數(shù)n=”；n注：①“提示內(nèi)容”與變量之間必須用分號“；”隔開。②各“提示內(nèi)容”之間以及各變量之間必須用逗號“，”隔開。但最后的變量的后面不需要。③提示內(nèi)容和它后面的“；”可省略

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

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

（二）輸出語句TheFibonacciProgressionis：11235813213455…輸出框：PRINTn；“是質(zhì)數(shù)。”輸出框：PRINTn；“不是質(zhì)數(shù)?！盤RINT

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

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

END（三）賦值語句：用來表明賦給某一個變量一個具體的確定值的語句。

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

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

AEND程序：在此程序的基礎(chǔ)上，設(shè)計一個程序，求A的輸出值是

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

AA=A+5PRINT

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

AINPUT

BPRINT

A，BX=AA=BB=XPRINT

A，BEND程序：

例1編寫程序，計算一個學(xué)生語文、數(shù)學(xué)、英語三門課程的總成績和平均成績，并輸出。開始輸入數(shù)學(xué)a輸入語文b輸入英語c總分s=a+b+c平均p=s/3輸出總分s輸出平均分p結(jié)束程序：INPUT“Maths=”;aINPUT“Chinese=”;bINPUT“Enghlish=”;cs=a+b+cp=s/3PRINT“sum=”;sPRINT“Theaverage=”;pEND程序框圖：INPUT“Maths,Chinese,Eng