算法和算法的描述

1、上課須知之上課須知之1.1.課程介紹課程介紹模塊模塊主要內(nèi)容主要內(nèi)容考核比例考核比例必修部分必修部分信息與信息的數(shù)字化信息與信息的數(shù)字化計(jì)算機(jī)軟硬件系統(tǒng)計(jì)算機(jī)軟硬件系統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)安全計(jì)算機(jī)安全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è)計(jì)算法與程序設(shè)計(jì)上課上課須知之須知之2.2.課堂常規(guī)課堂常規(guī)（

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

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

4、處分（8）不得擅自調(diào)換座位）不得擅自調(diào)換座位例例1:有一個(gè)有一個(gè)3毫升的量杯和一毫升的量杯和一個(gè)個(gè)5毫升的量杯，杯上沒(méi)有刻毫升的量杯，杯上沒(méi)有刻度，你能想辦法用它們量出度，你能想辦法用它們量出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毫升水毫升水為解決某一問(wèn)題而設(shè)計(jì)的確定的有限的步驟就稱(chēng)為算法為解決某一問(wèn)

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

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

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

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

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

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

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

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

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

15、盤(pán)輸入圓的半徑，計(jì)算其面積開(kāi)始開(kāi)始輸入輸入RS=3.14*R*R結(jié)束結(jié)束輸出輸出S解答：解答：輸入圓的半徑輸入圓的半徑RS=3.14*R*R輸出面積輸出面積S例例8：用流程圖表示：用流程圖表示：求從鍵盤(pán)輸入的任意半徑的圓的面積和周長(zhǎng)求從鍵盤(pán)輸入的任意半徑的圓的面積和周長(zhǎng) 開(kāi)始開(kāi)始輸入輸入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，周長(zhǎng)，周長(zhǎng)C C 回家作業(yè)：回家作業(yè)：1、下列算法違背了算法的哪個(gè)特征、下列算法違背了算法的哪個(gè)特征 L=10 輸出輸出L/正整數(shù)正整數(shù)2、下列算法違背了算法的哪個(gè)特征、下列算法違背了算法的哪個(gè)特