算法和算法的描述

1、上課須知之上課須知之1.1.課程介紹課程介紹模塊模塊主要內(nèi)容主要內(nèi)容考核比例考核比例必修部分必修部分信息與信息的數(shù)字化信息與信息的數(shù)字化計算機軟硬件系統(tǒng)計算機軟硬件系統(tǒng)計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)計算機安全計算機安全75/12075/120選修部分選修部分算法基本概念算法基本概念算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)基本算法：基本算法：解析、枚舉、排序、查找解析、枚舉、排序、查找45/12045/120（1）課程重要性（學(xué)業(yè)考）課程重要性（學(xué)業(yè)考）（2）課程內(nèi)容及考核比例）課程內(nèi)容及考核比例（3）本學(xué)期教學(xué)任務(wù)：）本學(xué)期教學(xué)任務(wù)：算法與程序設(shè)計算法與程序設(shè)計上課上課須知之須知之2.2.課堂常規(guī)課堂常規(guī)（

2、1）每位同學(xué)準(zhǔn)備）每位同學(xué)準(zhǔn)備一一本練習(xí)本，用于：本練習(xí)本，用于： 記筆記；書面作業(yè)記筆記；書面作業(yè)（2）上課時將教材和筆記本備好）上課時將教材和筆記本備好（3）授課教師信箱）授課教師信箱用于授課教師和學(xué)生的交流，布置和上交作業(yè)用于授課教師和學(xué)生的交流，布置和上交作業(yè) 星期四之前（截止星期三星期四之前（截止星期三9月月4日晚日晚24:00）每位同學(xué)發(fā)送郵件至上述信箱，郵件的主題為：每位同學(xué)發(fā)送郵件至上述信箱，郵件的主題為：學(xué)號學(xué)號+姓名姓名例如：例如：1號同學(xué)號同學(xué)XX（1號同學(xué)的姓名）的郵件主題號同學(xué)的姓名）的郵件主題應(yīng)為：應(yīng)為： 01XX上課上課須知之須知之3. 3. 機房機房規(guī)則規(guī)則（1

3、）上課正式鈴響之前須在自己的座位上坐好）上課正式鈴響之前須在自己的座位上坐好（2）上課時除本學(xué)科教材和筆記本外不準(zhǔn)攜帶其）上課時除本學(xué)科教材和筆記本外不準(zhǔn)攜帶其他科目作業(yè)等材料，一經(jīng)發(fā)現(xiàn)即予沒收他科目作業(yè)等材料，一經(jīng)發(fā)現(xiàn)即予沒收（3）不得擅自使用）不得擅自使用u盤等存儲設(shè)備盤等存儲設(shè)備（4）不準(zhǔn)玩游戲）不準(zhǔn)玩游戲，一經(jīng)發(fā)現(xiàn)報學(xué)生發(fā)展部處理一經(jīng)發(fā)現(xiàn)報學(xué)生發(fā)展部處理（5）自覺維護機房衛(wèi)生，零食和飲料不得帶入）自覺維護機房衛(wèi)生，零食和飲料不得帶入 機房。機房。（6）不得在機房打鬧、跑動）不得在機房打鬧、跑動（7）不得故意損壞機器設(shè)備，否則照價賠償并）不得故意損壞機器設(shè)備，否則照價賠償并 通報處分通報

4、處分（8）不得擅自調(diào)換座位）不得擅自調(diào)換座位例例1:有一個有一個3毫升的量杯和一毫升的量杯和一個個5毫升的量杯，杯上沒有刻毫升的量杯，杯上沒有刻度，你能想辦法用它們量出度，你能想辦法用它們量出1毫升的水嗎？毫升的水嗎？方法一：方法一：1、將、將3毫升的量杯裝滿毫升的量杯裝滿2、將、將3毫升量杯中的水全部注入毫升量杯中的水全部注入5毫升的毫升的量杯量杯3、將、將3毫升的量杯裝滿毫升的量杯裝滿4、利用、利用3毫升量杯中的水將毫升量杯中的水將5毫升量杯倒毫升量杯倒?jié)M，滿，3毫升量杯中剩余毫升量杯中剩余1毫升水。毫升水。方法二：方法二：1、將、將5毫升的量杯裝滿毫升的量杯裝滿2、將、將5毫升量杯中的水

5、注入毫升量杯中的水注入3毫升量杯，注滿后毫升量杯，注滿后5毫升量杯中毫升量杯中剩余剩余2毫升水毫升水3、將、將3毫升量杯倒空毫升量杯倒空4、將、將5毫升量杯中剩余的毫升量杯中剩余的2毫升注入毫升注入3毫升量杯毫升量杯5、將、將5毫升量杯裝滿毫升量杯裝滿6、將、將5毫升量杯中的水注入毫升量杯中的水注入3毫升量杯，注滿后毫升量杯，注滿后5毫升量杯中毫升量杯中剩余剩余4毫升水毫升水7、將、將3毫升量杯倒空毫升量杯倒空8、將、將5毫升量杯中的水注入毫升量杯中的水注入3毫升量杯，注滿后毫升量杯，注滿后5毫升量杯中毫升量杯中剩余剩余1毫升水毫升水為解決某一問題而設(shè)計的確定的有限的步驟就稱為算法為解決某一問

6、題而設(shè)計的確定的有限的步驟就稱為算法 說明：算法不是唯一的，針對同一問題的算法可以說明：算法不是唯一的，針對同一問題的算法可以 有多種。有多種。廣義地說，廣義地說，“有窮性有窮性”一般指一般指操作操作步驟的數(shù)量有限步驟的數(shù)量有限或或能在合理的時間范能在合理的時間范圍內(nèi)完成全部操作圍內(nèi)完成全部操作。算法可以有重復(fù)。算法可以有重復(fù)執(zhí)行的步驟，只要這些步驟的執(zhí)行能執(zhí)行的步驟，只要這些步驟的執(zhí)行能夠終止。有些算法雖然是有窮的，但夠終止。有些算法雖然是有窮的，但它所花費的時間如果超出了合理的限它所花費的時間如果超出了合理的限度，如天氣預(yù)報采用的算法若要幾個度，如天氣預(yù)報采用的算法若要幾個月后才能計算出來

7、，那就不能算是有月后才能計算出來，那就不能算是有效地算法。效地算法。例例1：判斷下列算法是否符合算法的特征：判斷下列算法是否符合算法的特征：給給s賦值為賦值為1將將s的值增加的值增加1重復(fù)步驟重復(fù)步驟解答：該算法的步驟將被重復(fù)執(zhí)行無窮次，解答：該算法的步驟將被重復(fù)執(zhí)行無窮次， 不符合算法的有窮性不符合算法的有窮性 返回算法中的每個步驟必須有確切的算法中的每個步驟必須有確切的含義，而不應(yīng)當(dāng)是含糊的、模棱兩可含義，而不應(yīng)當(dāng)是含糊的、模棱兩可的。的。例例2：判斷下列算法是否符合算法的特征：判斷下列算法是否符合算法的特征L=10輸出輸出L/自然數(shù)自然數(shù)解答：正整數(shù)沒有具體指明是哪個數(shù)，解答：正整數(shù)沒有

8、具體指明是哪個數(shù)， 不符合算法的確定性不符合算法的確定性返回 算法中每一個步驟都是要能夠?qū)嵥惴ㄖ忻恳粋€步驟都是要能夠?qū)嶋H做到的，而且是在有限的時間內(nèi)完際做到的，而且是在有限的時間內(nèi)完成。成。例例3：判斷下列算法是否符合算法的特征：判斷下列算法是否符合算法的特征x= -2計算計算x的平方根的平方根解答：解答：x是負(fù)數(shù)，沒有平方根，該算法不可行，是負(fù)數(shù)，沒有平方根，該算法不可行， 不符合算法的可行性不符合算法的可行性 返回 所謂輸入就是只算法在執(zhí)行時要所謂輸入就是只算法在執(zhí)行時要從外界獲得數(shù)據(jù)，其目的是為算法建從外界獲得數(shù)據(jù)，其目的是為算法建立某些初始狀態(tài)。如果建立初始狀態(tài)立某些初始狀態(tài)。如果建立

9、初始狀態(tài)所需的數(shù)據(jù)已經(jīng)包含在算法中了，那所需的數(shù)據(jù)已經(jīng)包含在算法中了，那就不需要輸入。如果所需的數(shù)據(jù)沒有就不需要輸入。如果所需的數(shù)據(jù)沒有包含在算法中，則需要在運行時動態(tài)包含在算法中，則需要在運行時動態(tài)輸入所需數(shù)據(jù)。輸入所需數(shù)據(jù)。例例4：寫出算法：計算半徑為：寫出算法：計算半徑為2的圓的面積的圓的面積解答：解答：R=2S=3.14*R*R輸出面積輸出面積S說明：該算法中已包含計算所需的初始數(shù)據(jù)，說明：該算法中已包含計算所需的初始數(shù)據(jù)， 因此沒有輸入因此沒有輸入說明：該算法中計算面積所需的初始數(shù)據(jù)半說明：該算法中計算面積所需的初始數(shù)據(jù)半徑徑R待定，要在程序運行后從鍵盤輸入。待定，要在程序運行后從鍵

10、盤輸入。而算法是解決一類問題的，往往所需的初始而算法是解決一類問題的，往往所需的初始數(shù)據(jù)不止數(shù)據(jù)不止1個，可能會有多個。通過前兩個例子個，可能會有多個。通過前兩個例子可以知道，可以知道，算法可能有算法可能有0個或多個輸入。個或多個輸入。解答：解答：輸入圓的半徑輸入圓的半徑RS=3.14*R*R輸出面積輸出面積S例例5：寫出算法：從鍵盤輸入圓的半徑，計算其面積：寫出算法：從鍵盤輸入圓的半徑，計算其面積返回 設(shè)計算法的目的是讓計算機解決設(shè)計算法的目的是讓計算機解決某個問題，計算機處理該問題的結(jié)果某個問題，計算機處理該問題的結(jié)果必須以人能接受的方式輸出來，該算必須以人能接受的方式輸出來，該算法才會是

11、有效的。法才會是有效的。說明：說明：算法可能有算法可能有1個或多個輸出個或多個輸出。例例6：求從鍵盤輸入的任意半徑的圓的面積和周長：求從鍵盤輸入的任意半徑的圓的面積和周長解答：解答：輸入圓的半徑輸入圓的半徑RS=3.14*R*RC=2*3.14*R輸出面積輸出面積S，周長，周長C 返回3 3、計算機算法的描述方法、計算機算法的描述方法 自然語言描述法自然語言描述法流程圖描述法流程圖描述法l用圖形符號表示算法必須要有一組統(tǒng)一規(guī)定、含義確定的專用符號；l用流程圖表示算法就較直觀、形象；l計算機不能識別和執(zhí)行。偽代碼或程序設(shè)計語言描述法偽代碼或程序設(shè)計語言描述法l只有用計算機能理解和執(zhí)行的程序設(shè)計語

12、言把算法表示出來，輸入計算機執(zhí)行，計算機才能按照預(yù)定的算法去解決問題；l不同類型的計算機能夠識別的指令和語言不盡相同，即使對同一種計算機語言，不同類型的計算機對該語言的翻譯程序也有差異。3 3、計算機算法的描述方法、計算機算法的描述方法 自然語言描述法自然語言描述法l用自然語言表示算法，人比較容易理解，但書寫較煩瑣，具有不確切性，容易引起歧義，造成誤解；l對較復(fù)雜的問題，用自然語言難以表達(dá)準(zhǔn)確；l計算機不能識別和執(zhí)行。流程圖描述法流程圖描述法l用圖形符號表示算法必須要有一組統(tǒng)一規(guī)定、含義確定的專用符號；l用流程圖表示算法就較直觀、形象；l計算機不能識別和執(zhí)行。偽代碼或程序設(shè)計語言描述法偽代碼或

13、程序設(shè)計語言描述法l只有用計算機能理解和執(zhí)行的程序設(shè)計語言把算法表示出來，輸入計算機執(zhí)行，計算機才能按照預(yù)定的算法去解決問題；l不同類型的計算機能夠識別的指令和語言不盡相同，即使對同一種計算機語言，不同類型的計算機對該語言的翻譯程序也有差異。輸入x,求分段函數(shù)值y： y= x2 x3 2x+1 x3結(jié)束結(jié)束y=x*xy=2*x+1輸出輸出 y y流程圖描述算法圖形符號符號名稱說明流線起始、終止框表示算法的開始或結(jié)束開始框：一流出線結(jié)束框：一流入線輸入、輸出框框中標(biāo)明輸入輸出的內(nèi)容只有一流入線和一流出線處理框框中標(biāo)明進(jìn)行什么處理只有一流入線和一流出線判斷框框中標(biāo)明判定條件并在框外標(biāo)明判定后的兩種

14、結(jié)果的流向一流入線兩流出線(T和F)流線表示從某一框到另一框的程序運行流向連接圈表示算法流向出口或入口連接點一條流線算法的流程圖表示起止框起止框表示一個算法的開始或結(jié)束算法的流程圖表示輸入、輸出框輸入、輸出框框內(nèi)標(biāo)明輸入、輸出的內(nèi)容算法的流程圖表示處理框處理框框內(nèi)標(biāo)明所進(jìn)行的處理算法的流程圖表示判別框判別框框內(nèi)標(biāo)明條件，并在框外標(biāo)明判定后的兩種結(jié)果的流向。算法的流程圖表示流程線流程線表示從某一框到另一框的流向算法的流程圖表示連接圈連接圈表示算法流向出口或入口連接點同一出口入口點的連接圈內(nèi)，必須標(biāo)以相同的符號。算法的流程圖表示例例7：用流程圖表示：用流程圖表示：從鍵盤輸入圓的半徑，計算其面積從鍵

15、盤輸入圓的半徑，計算其面積開始開始輸入輸入RS=3.14*R*R結(jié)束結(jié)束輸出輸出S解答：解答：輸入圓的半徑輸入圓的半徑RS=3.14*R*R輸出面積輸出面積S例例8：用流程圖表示：用流程圖表示：求從鍵盤輸入的任意半徑的圓的面積和周長求從鍵盤輸入的任意半徑的圓的面積和周長 開始開始輸入輸入RS=3.14*R*R結(jié)束結(jié)束輸出輸出S，CC=2*3.14*R解答：解答：輸入圓的半徑輸入圓的半徑R RS=3.14S=3.14* *R R* *R RC=2C=2* *3.143.14* *R R輸出面積輸出面積S S，周長，周長C C 回家作業(yè)：回家作業(yè)：1、下列算法違背了算法的哪個特征、下列算法違背了算法的哪個特征 L=10 輸出輸出L/正整數(shù)正整數(shù)2、下列算法違背了算法的哪個特征、下列算法違背了算法的哪個特