1、算法初步教學實踐講義東莞群英學校 梁斌玉說明：新課標理念先進，內容新穎，尤其是算法與編程的引入，適應了時代的發展，對我國的軟件事業的發展將產生重大的影響。但是算法和編程對學生來說是很陌生的事物，而但是現行教材，講解比較抽象，學生難懂。為此我根據自己的教學實踐對算法初步進行了改編。力求做到了如下幾點：1.例子豐富翔實貼切；2.循序漸進，由淺入深，將較難得問題分解為幾個小塊，逐步深入。3.符合學生的認知規律，在編排順序上改變較大。由于水平有限經驗不足，會存在不少缺點，還存在令人不滿意的地方，在此拋磚引玉，望不吝賜教。本文共一萬兩千余字，打印共37頁。求高手告知那里可以發表這類文章，謝謝。1.1算法

2、與程序框圖本節課用大量的例子來強化“算法”的概念。這些例子由淺入深，由現實生活出發，逐步向數學和計算機中的算法靠近，使算法概念得以深化。例1是現實生活中的例子，意在使學生形成“步驟”的概念。例2人鬼過河（網上有相應的flash動畫），是一個經典的智力題，可以激發學生的興趣，學生當堂不一定能完成，可以讓學生思考以后，用flash按步演示，目的是加深對“步驟”的認識。例3例4由現實生活中的例子過渡到數學中的例子，并和計算機結合，使算法的概念得到升華。例5，用篩選法求質數，對剛剛接觸算法的學生來說，比較難懂，對此，采取了由特殊到一般，由淺入深的策略，使學生突破難點。 計算機的問世可謂20世紀最偉大的

3、發明，它把人類社會帶進了信息技術的時代，而算法是計算機科學的重要基礎，就像使用算盤一樣，人們要給計算機編制“口訣”算法，才能讓它工作。要想了解計算機的工作原理，算法的學習是一個開始。做任何事情都有一定的步驟。例如，你想考大學首先要填報名志愿表，拿到準考證，參加考試，得到錄取通知書，到大學報名注冊等。這些步驟都是按一定順序進行的，缺一不可。現實生活中，我們很多事情都是這樣一步一步的完成的。 可見算法并不是一個全新的概念，它融入在我們的現實生活中。在我國古代，“算法”取得了輝煌的成就。例1.燒水泡茶請看一下燒水泡茶的過程解：燒水泡茶可分下面4步完成。Step1：洗好開水壺；Step2：灌上涼水，放

4、在火上，等待水開；Step3：洗茶杯，茶杯里放好茶葉；Step4：水開后再沖水泡茶。 例2.人鬼過河 現在河的岸邊有三個人和三個鬼，河上只有一條小船，船上最多能坐兩個“人”，在河的任何一邊，當鬼的個數比人多時，鬼就會吃掉人。請問如何才能使人和鬼都平安的到達對岸。解： 要想使人鬼都安全過河，需要下面11步。 Step1：Step2：Step3：Step4：Step5：Step6：Step7：Step8：Step9：Step10：Step11：例3.已知，求解： 要求需要下面4步。Step1：Step2：Step3：Step4：從事各種工作和活動，都必須事先想好工作的步驟，然后按部就班的進行，才能

5、避免產生錯誤。定義：我們把用來解決問題的一系列步驟叫做算法（algorithm）。算法一詞源于算術(algorism)，即算術方法，是指一個由已知推求未知的運算過程。隨著計算機的出現，人們常把這些“步驟”編寫為“程序”由計算機來解決。算法必須符合以下條件：1.算法的每一步要做什么必須是明確的，不能含糊不清，模棱兩可；例如，要把全班同學分成兩隊，“高個子的同學站出來”這個步驟就是不確定的，含糊的，哪些同學算高，哪些同學算矮？個子中等的同學就會不知所措。2.算法的每一步都應當能有效的執行，并得到確定的結果。例如若是無效的，不能執行的。3.算法必須在有限步內完成，如果需要無限步完成，就失去了實際意義

6、。算法的有限性往往指“在合理的范圍之內”。如果讓計算機執行一個歷時1000年才結束的算法，雖然是有限的，但超過了合理的限度，人們也不把它視作有效算法。究竟什么算“合理限度”并無嚴格標準，由人們的常識和需要而定。例4給計算機編寫一個算法，輸入一個自變量的值，求分段函數的函數值.解：Step1：輸入x的值；Step2：進行判斷，如果，則， 否則。Step3： 輸出結果。說明：1.輸入x的值就是把自變量x的值由鍵盤輸入計算機，例如要計算x=2時的函數值，就輸入2。 2.根據相應的x的值計算相應的函數值，比如輸入3，則 ；如果輸入-4，則。 3.輸出結果就是把計算結果顯示在計算機屏幕上。以上算法可以通

7、過輸給計算機一系列“命令”來實現，這些命令叫做計算機語言。例5.篩選法求質數質數亦叫作素數，是大于1的自然數，并且除了該數本身和1以外沒有其它的數能整除它，如2，3，5，7，11，13，質數有無窮多個。 （1）判斷143是否為質數。解：Step1：1432不為整數；Step2：1433不為整數；Step3：1434不為整數；Step4：1435不為整數；Step5：1436不為整數；Step6：1437不為整數；Step7：1438不為整數；Step8：1439不為整數；Step9：14310不為整數；Step10：14311=13，143能被11整除；Step11：結論：143不是質數。（2

8、）判斷17是否為質數。解：Step1：172不為整數；Step2：173不為整數；Step3：174不為整數；Step4：175不為整數；Step5：176不為整數；Step6：177不為整數；Step7：178不為整數；Step8：179不為整數；Step9：1710不為整數；Step10：1711不為整數；Step11：1712不為整數；Step12：1713不為整數；Step13：1714不為整數；Step14：1715不為整數；Step15：1716不為整數；Step16：結論：17是質數。 （3）判斷216091是不是質數該題的計算量非常大，我們可以把算法編為程序，由計算機幫我們計算

9、。（4）設計一個算法，輸入大于2的整數n，由計算機判斷它是不是質數。解Step1：輸入整數n；Step2：依次檢驗2(n-1)是不是n的因數，若有這樣的數，則n不是質數，否則，n為質數。Step3：輸出結果。說明：其中第3步在計算機中可以通過一個循環來實現，今后會學到。2001年12月5日拿大大學生邁克卡梅倫發現又發現一個最大質數，它被記作2134669171，而它的完整表示式中含有4053946個數字。他是GreatInternetMersennePrimeSearch(Gimps)計劃的參加者，該計劃在致力于解決這一問題時同時動用了全球13萬臺個人計算機。有意思的是，為了完整地寫出這個最大

10、質數，邁克卡梅倫花去了整整三周時間。為了發現這個最大質數，他利用自己的800兆赫計算機工作了45天。 研究結果可以在數論中找到應用，也可以幫助研究更可靠安全的譯碼方法。目前，Gimps計劃正在抓緊尋找由幾千萬個數字組成的質數，如誰的計算機能尋找到這隱藏的更大質數，則可以獲得10萬美元獎金。 思考 你能舉出跟多算法的例子嗎？于一般的解決問題的過程比較，你認為算法最重要的特征是什么？ 練習：1.任意給定一個正數，設計一個算法，求以這個數為半徑的圓的面積。2.設計一個算法，求的值。3.牛虎過河。一個人帶三只老虎和三頭牛過河。只有一條船，可以容一個人和兩只動物。沒有人在的時候，如果老虎的數量不少于牛的

11、數量就會吃掉牛。設計安全渡河的算法。4.任意給定一個大于1 的正整數n，設計一個算法，求出n的所有因數。算法對學生來說是陌生的內容，根據“建構主義理論”應由最簡單的開始，逐步構建出“程序框圖”的知識。課本上先給出了一個包含三種基本結構的復雜框圖，然后把它進行分解來認識它，違背了認知規律，學生不易理解，且易使學生產生畏懼心理。這種方法適合于學生比較熟悉的事物。據此，本節通過淺顯的例子（這些例子多數是第一節中研究過的），依次引出順序結構，選擇結構和循環結構，并及時歸納總結，是學生在不知不覺中加深對三種結構的理解。算法可以用自然語言來表示，但為了使算法的步驟表達得更為直觀，我們更經常地用圖形方式來表

12、達，這就是 程 序框圖。 程序有三種基本邏輯結構，順序結構、選擇結構和循環結構。復雜的程序都是由這三種結構組成。一、順序結構例1燒水泡茶 請敘述一下燒水泡茶的過程解：該算法用自然語言表述為Step1：洗好開水壺；Step2：灌上涼水，放在火上，等待水開；Step3：洗茶杯，茶杯里放好茶葉；Step4：水開后再沖水泡茶。 可以用程序框圖表示為： 開始洗水壺燒水泡茶洗茶杯，放茶葉結束 例2. 給計算機編寫一個算法，輸入一個自變量的值，求的函數值.解：該算法用自然語言表述為Step1：輸入x的值Step2：Step3：Step4：Step5：Step6：輸出y。可以用程序框圖表示為：開始輸入x輸出y

13、結束 程序框圖符號和它們所表示的功能：圖形符號名稱功能 起止框（終端框）表示一個算法的起始和結束輸入輸出框表示一個算法輸入和輸出的信息處理框（執行框）賦值、計算流程線連接程序框 順序結構由若干個依次執行的處理步驟組成。這是任何一個算法都離不開的基本結構。二、選擇結構例3給計算機編寫一個算法，輸入一個自變量的值，求分段函數的函數值.解：該算法用自然語言表述為Step1：輸入x的值；Step2：進行判斷，如果，則， 否則。Step3： 輸出結果。可以用程序框圖表示為：開始輸入x輸出y結束其中被虛線框起來的是選擇結構，它的一般形式為：步驟2步驟1 選擇結構由一個判斷框和兩個分支組成。當條件框內的條件

14、成立時，程序沿著分支1進行；否則程序沿分支2進行。圖形符號名稱功能判斷框判斷某一條件是否成立，它有兩個出口：“是”或“否”。條件成立時，程序沿著“是”這個分支走下去；當條件不成立時，程序沿著“否”這個分支進行。 流程線連接程序框連接點當一個程序框圖很大，一頁寫不下時，連接程序框圖的兩部分。一般在連接處標上相同的數字序號。例4.判斷一元二次函數是否有根。分析：，當時，方程有根；當時，方程無根。解：程序框圖表示為開始輸入a,b,c結束輸出：方程有實根輸出：方程無實根一般情況下，選擇結構有兩個分支，分別說明條件“成立”時怎樣做，件“不成立”時怎樣做。但也有特殊情況，當條件不成立時什么也不做（或者條件

15、成立時什么也不做），這時只有一個分支。例5.電視上有很多智力競賽的題目，主持人提問，選手回答，若回答正確，加10分，如果錯誤，不加分。試用程序框圖來描述這一情況。解：回答正確？開始結束選手回答主持人提問加10分 一個分支的條件結構的一般形式為：步驟 選擇結構的嵌套例6.函數，編寫一個算法，輸入x的值，輸出y的值解：該算法的程序框圖為開始輸入x輸出y結束（1） 虛線框起來的部分為嵌套選擇結構；（2） 當x0時程序沿著“Yes”分支進行；（3） 當時程序沿著“No”分支進行（4） “No”分支中又包含了一個條件結構。三、循環結構例5.上例中，智力競賽的真實過程要復雜很多，主持人提問，選手回答，若回

16、答正確，加10分，如果錯誤，不加分，然后主持人繼續提問，選手繼續回答，如此循環下去，直到提問結束。（當然這也只是簡化過程。）用程序框圖來描述這一情況。解：由于過程中出現了循環，需要用循環結構果來表示。 開始結束分數=0選手回答主持人提問回答正確？分數=分數+ 10分還要提問？（1） 程序按箭頭所指方向進行；（2） 虛線框起來的部分稱為循環結構；（3） 每次進入循環前都要判斷是否“還要提問”，若還要提問，則進入循環（繼續提問），若提問結束，則不再進入循環，算法結束。（4） 其中“主持人提問”、“選手回答”、“判斷是否加分”等步驟是每次循環所重復的內容，叫做循環體。（5） “分數=分數+ 10分”

17、是一個賦值語句，其含義是：“后來的分數=原分數+10分”循環結構的一般形式為：循環體滿足條件？ 例5 寫出求1+2+3+4+5+6的一個算法。解： Step1：計算1+2得到3；Step2：將第一步中的運算結果3與3相加得到6；Step3：將第二步中的運算結果6與4相加得到10；Step4：將第三步中的運算結果10與5相加得到15；Step5：將第四步中的運算結果15與6相加得到21。例6設計一個計算的算法解：如果按例5的方法，計算量很大。我們可以設想有一個空儲物箱，第1次放入1個球，第2次放入2個球第100次放入100個球。這樣重復100次后，儲物箱里的總球數就是個。每放一次球我們可以看作一

18、次循環，總共循環了100次。 為了求從1 到100 的和，我們可以設一個變量S，它就像一個儲物箱，一開始S=0，相當于儲物箱是空的。另設一個變量i，用它來記錄循環（即累加）的次數，i的初始值為1，每循環一次，i增加1，當i=100時，剛好循環了100次，當i=101時，i100,就退出循環。開始結束 輸出S （1）程序按箭頭所指方向進行， 在判斷框處 ，如果，則按yes所指方向進行循環，否則按No所指方向進行。（2）i叫做計數變量，用于記錄循環次數，同時它的取值還可以用來判斷循環是否中止。循環第一圈時i的值為1，第二圈時i的值為2第100圈時，i的值為100。這種變化是通過語句i=i+1來實現

19、的。其含義是“后來的i值=原i值+1”每循環一圈，i=i+1被執行一遍，的值就增加了。（3）S叫做累加變量，用于記錄累加結果。循環第1圈在S上加1；循環第2圈在S上加2；循環第3圈在S上加3；循環第i圈在S上加i；循環第100圈在S上加100；“循環第i圈在S上加i”用語句S=S+i表示，把這時i的值加到S上。當循環到100圈時，S的值就是的和。例7下面是一個計算的算法，請補充完整。分析：先考慮清楚下面兩個問題。1. 從2到100的偶數共有多少個？_2. 兩個相鄰偶數的間隔是多少？_解：開始結束 輸出S為了理解該程序，填寫下表圈數i100s直到型循環結構絕大多數情況下可以有當行循環結構代替，對

20、開發學生智力并無多大幫助，反而會使學生產生迷惑，何必增加這些內容呢？練習1. 設計一個求任意數的絕對值得算法，并劃出程序框圖。2. 任意給定3個正實數，設計一個算法，判斷分別以這3個數為邊長的三角形是否存在。畫出這個算法的程序框圖。3. 某居民區的物業部門每月向居民收取衛生費，計費方法是：3人和三人以下的住戶，每人收取5元；超過3人的住戶，每超出一人，加收1.2元。寫出一人數x為自變量，以衛生費y為函數值的分段函數。設計一個算法，根據輸入的人數，計算應收取的衛生費，畫出程序框圖。4. 設計一個求解一元二次方程的算法，畫出程序框圖。5. 設計一個計算的算法，畫出程序框圖。6. 設計一個算法，求的

21、值.，畫出程序框圖。1.2基本算法語句計算機完成任何一項任務都需要算法。但是，我們用自然語言或程序框圖描述的算法，計算機是無法“理解”的。因此還需要把算法翻譯成計算機能理解的“計算機程序設計語言”（Progamming Language），編制成計算機程序。我們前面學過，算法有三種基本結構：順序結構、條件結構和循環結構。為了實現算法中三種基本的邏輯結構，各種程序設計語言都包括下列算法語句：輸入語句、輸出語句、賦值語句、條件語句和循環語句。程序設計語言有很多種，如BASIC，Foxbase，C語言，C+，J+，VB等。它們的基本原理是相同的。本章中，我們學習的程序設計語言是“QuickBASIC

22、”語言，它是一種類BASIC語言。BASIC是Beginner Allpurpose Symbolic Instruction Code(初學者通用符號指令代碼)的英文縮寫，與1964年由美國的兩位教授設計，具有簡單、易學的特點。 輸入語句、輸出語句、和賦值語句基本上對應于算法中的順序結構。計算機從上而下按照語句排列的順序執行這些語句。一、輸入語句例1.編制一個程序，在電腦屏幕上顯示“Hello，evryone！”。解：運行QuickBASIC軟件，在編輯窗口內輸入下面程序。PRINT “Hello,everyone!”ENDHello,everyone! 編輯程序 運行結果 其中的PRINT

23、是一個命令，它的作用是輸出它后面引號中的內容。運行該程序，會在電腦屏幕上顯示：Hello,everyone!例2 設變量x=123，編制一個程序，在屏幕上顯示出x的值。解：“運行QuickBASIC軟件，在編輯窗口內輸入下面程序。x=123PRINT xEND123 編輯程序 運行結果思考 PRINT語句后的輸出內容中，加引號和不加引號的區別？ _上面幾個例子中“PRINT”語句就是輸出語句，對應于程序框圖中的輸出語句。其一般格式為：PRINT “提示內容”；變量想一想下面語句會輸出什么結果？X=123+321PRINT “x=” ; xENDx=444 編輯程序 運行結果例3.當x=234時

24、求函數的值。解：“運行QuickBASIC軟件，在編輯窗口內輸入下面程序。X=123y=x3+3*x2-24*x+30PRINT “y=” ; yENDx=19033323 編輯程序 運行結果程序中的運算符，和我們平常用的有所不同，具體如下：數學運算加減乘除程序符號+-*/xnsqr(a)abs(a)二、輸出語句例4.編寫一個程序，輸入x的值求函數的值。解：“運行QuickBASIC軟件，在編輯窗口內輸入下面程序。INPUT “x=” : xy=x3+3*x2-24*x+30PRINT “y=” ; yEND編輯程序這個程序中，第一行的INPUT語句就是輸出語句，其后的x是一個變量。該語句的作

25、用是從鍵盤輸入x的值。例如要計算x=100時的函數值，就輸入100。輸出語句對應于程序框圖中的輸出框，其一般格式為：INPUT “提示內容”；變量 輸出語句可以在計算機屏幕上輸出常量、變量和提示信息。運行程序后會出現如下提示窗口：x=？運行后程序提示輸入x的值x=？111x=111y=1401960輸入x的值111后程序自動計算出y=1401960三、賦值語句賦值語句前面已經見過，請再在看一下例3 ：x=123y=x3+3*x2-24*x+30PRINT “y=” ; yEND.第一行和第二行叫做賦值語句，顧名思義，賦值語句就是將表達式所帶表的值賦給變量。賦值語句中的“=”叫做賦值號，它和數學

26、中的等號不完全一樣。計算機執行賦值語句時，先計算“=”右邊的表達式式的值，然后把這個值賦給左邊的變量。例如第一行中，就把左邊的123賦給右邊的變量x（即讓x等于123）；第二行，先計算出左邊的表達式的值為1401960，然后把1401960賦給變量y。賦值語句的一般格式為：變量 = 表達式可以把變量看作一個存放數據的盒子，而且最多只能存放一個數據的盒子。當一個新數據放進去時，原來的數就被“擠”了出去。請說出下面程序輸出的結果a=10a=a+20PRINT “a=”;aEND第一行：把等號右邊的數值10賦給左邊的變量a；10 a第二行：先計算等號右邊的值a+20=10+20=30，然后把數據30

27、存入變量a，a中原來的10被沖掉。 30 a 輸出結果：a =20 例5.編寫程序，計算一個學生數學、語文、英語三門課的平均成績。解：程序為：INPUT “Maths=”;a INPUT “ Chines=”;b INPUT “ English=”;c x=(a+b+c)/3 PRINT “ The average is”;x END思考請把下面的程序框圖翻譯為程序，并說出那些框圖對應輸出語句，那些框圖對應輸入語句，那些框圖對應賦值語句。開始輸入x輸出y結束例6.已知，交換的值。分析：請看下面的程序 a=2b=5a=bb=aPRINT a,bEND 輸出結果為：5 5.請思考為什么？第一行：a

28、的值為2；第四行：b的值為5； 第三行: 把b的值賦給a，這時b的值為5，所以a=5;(注意：這時a中原來存儲的數值2 已經被沖掉了。) 第四行：把a的值賦給b，而這時a的值為5，所以b的值還是5； 第五行：因為a，b的值均為5，所以輸出結果為5 5。 沒有達到交換的目的。 為了加深理解，請大家請分析一下每行中a、b的值，并填表。 a b 第1行：第2行：第3行： 第4行：第5行：解：（空桶法）交換裝滿水的兩個水桶里的水需要再找一個空桶，交換兩個變量正確的方法是設置一個中間變量t。 a=2b=5t=aa=bb=tPRINT a,bEND 第三行t=a的作用：把a的值2保存在變量x中，這樣當執行

29、a=b時，a中的值仍可以在t中找到。 請分析一下每行中a、b、t的值，并填表。 a b t 第1行：第2行：第3行： 第4行：第5行：第6行： 練習1. 已知華氏溫度和攝氏溫度的轉化公式為： 編寫一個程序，輸入一個華氏溫度，輸出其相應的攝氏溫度。2. 編寫一個程序，輸入兩個非零實數，輸出他們加、減、乘、除的結果。3. 已知一個三角形的三邊長分別是，它的面積可用海倫秦九韶公式計算。 ，其中 設計一個算法，輸入三角形的三條邊長，輸出三角形的面積S。寫出程序框圖和相應的程序。4. 春節到了，糖果店的售貨員忙極了。已知水果糖每千克10.4元，奶糖每千克15.6元，果仁巧克力每千克25.2元，那么依次購

30、買這三種果糖千克，應收取多少錢？請你設計一個程序，幫售貨員算賬。5. 編寫一個程序，輸入梯形的上底、下底和高的值，計算并輸出其面積。6. 編寫一個程序，交換兩個變量a 、b的值，并輸出交換前后的值。算法中的條件結構由條件語句來表達。一、基本條件語句（1）兩個分支的條件結構IF 條件 THEN語句體1ELSE語句體2ENF IF步驟2步驟1 條件結構框圖 條件語句當計算機執行上述語句時，首先對IF后的條件進行判斷，如果條件成立，就執行THEN之后的語句體，否則執行ELSE之后的語句體。例1. 給計算機編寫一個程序，輸入一個自變量的值，輸出分段函數的函數值.解： 用程序框圖表示為：開始輸入x輸出y

31、結束用QuickBASIC 語言可寫為INPUT “x=”;x IF x=0 THEN y = x + 2 ELSE y = x2 END IF PRINT “y =” ; y END數學運算等于不等于大于小于大于等于小于等于程序符號=0 THEN外層IF語句 y = 1內層IF語句 ELSE IF x=0 THEN y = 0 ELSE y = -1 END IF END IF PRINT “ y=”; y END該程序中有兩個IF語句，大IF語句中嵌套了一個小IF語句。思考 請將程序框圖和相應的語句對應起來。例3 編寫一個程序，求一元二次方程的根.分析：，當時方程有兩個不相等的實根；當時，

32、方程有兩個相等的實根；當時，方程沒有實根。解：程序框圖為 開始輸入a,b,c結束輸出:沒有實根 輸出x輸出:沒有實根將程序框圖改寫為QuickBASIC 程序INPUT a,b,cD=b2-4*a*cIF D=0 THEN IF D0 THEN x1=(-b+sqr(D)/2*a x1=(-b-sqr(D)/2*a PRINT “x1=”;x1,”x2=”;x2 ELSE x=-b/2*a PRINT “x=”;x END IFELSE PRINT “No root.”END IFEND例4 排序編寫一個程序，使得任意輸入的3個整數按從大到小的順序輸出。算法分析：我們用a,b,c表示輸入的三個

33、整數，比較三個整數，把最大的整數存入變量a中，次大的整數存入b中，最小的整數存入c中。Step1：輸入三個整數a,b,c；Step2：將a與b比較，如果ab,交換它們的值；Step3：將a與c比較，如果ac,交換它們的值； (第2步和第3步后，a中存儲的已經是最大的整數)Step4：將b與c比較，如果ba THEN t=a a=b b=t END IF IF ca THEN t=a a=c c=t END IFIF cb THEN t=b b=c c=t END IF PRINT a,b,c END練習1.讀程序，說出該程序的功能。 INPUT “Please input an inter:”;x IF 9x AND x100 THEN a=x10 b=x MOD 10 PRINT a,b END IFEND數學運算且或的商的余數程序符號ANDORa MOD b注：1.在程序中用“AND”表示“且”，用“OR”表示“或”。 2.用“a/b”