第一講 算法與程序設(shè)計(jì)

1、算法與程序設(shè)計(jì),一、算法及其描述方法,第一節(jié) 算法與程序,計(jì)算機(jī)系統(tǒng),硬件系統(tǒng),軟件系統(tǒng),系統(tǒng)軟件,應(yīng)用軟件,軟件的重要組成部分是：程序 想一想：什么是程序？,什么是程序,計(jì)算機(jī)的任何動作都是在執(zhí)行人給它的指令。人們針對某一需要而為計(jì)算機(jī)編制的指令序列稱為程序 。 程序指示計(jì)算機(jī)如何去解決問題或完成任務(wù)的一組可執(zhí)行的指令。,那么，什么是算法呢？,討論：,用沒有刻度的3毫升量杯和5毫升量杯如何量出1毫升的水？請寫出自己的解決步驟。,參考算法二,參考算法一,算法是在有限步驟內(nèi)求解某一問題所使用的具有精確定義的一系列操作規(guī)則。簡而言之，算法是指解決問題的具體方法和步驟。,說明：算法不是唯一的，針對同

2、一問題的算法可以有多種。,一個完整的算法有三個部分：輸入、處理、輸出。,算法與程序的關(guān)系是什么呢？ 算法是程序的靈魂，是解決問題的步驟。程序代碼只是實(shí)現(xiàn)的手段。,例題： 某學(xué)校要進(jìn)行學(xué)生電腦編程競賽，競賽將評出10名獲獎?wù)?，分為一、二、三等獎。獎?xiàng)設(shè)置一等獎獲得人數(shù)要少于二等獎人數(shù)，二等獎人數(shù)要少于三等獎人數(shù)。問一二三等獎人數(shù)各為多少？,分析：1.已知競賽將評出10名獲獎?wù)摺?2.一等獎獲得人數(shù)要少于二等獎人數(shù)，二等獎人數(shù)要少于三等獎人數(shù) 設(shè)計(jì)算法： 1.X+y+z=10 Xyz 2.10以內(nèi)的整數(shù)，逐個拿來試一試。滿足條件的n組數(shù)， 即結(jié)果,3.編寫程序。 4.調(diào)試程序。,使用電腦解決問題的

3、一般過程 分析問題 設(shè)計(jì)算法（設(shè)計(jì)出解決某一問題的有限個求解步驟 ） 編寫程序 運(yùn)行程序,算法的特征,有窮性：一個算法必須保證執(zhí)行有限步驟之后結(jié)束。 確定性：算法的每一步驟必須有確切的含義。 可行性：算法的每一步驟都能有效地執(zhí)行，并得到確定 的結(jié)果。 輸入：有0個或多個輸入。 輸出：有1個或多個輸出，沒有輸出的算法毫無意義。,下一頁,例1：判斷下列算法是否符合算法的特征, s=1 將s的值增加1 重復(fù)步驟,解答：該算法的步驟將被重復(fù)執(zhí)行無窮次，不符合 有窮性,返回,例2：判斷下列算法是否符合算法的特征,L=10 輸出L/自然數(shù),解答：自然數(shù)沒有具體指明是哪個數(shù)，不符合算法的 確定性,返回,例3

4、：判斷下列算法是否符合算法的特征,x= -2 計(jì)算x的平方根,解答：x是負(fù)數(shù)，沒有平方根，該算法不可行，不符合 算法的可行性。,返回,例4：寫出算法：計(jì)算半徑為2的圓的面積,解答： R=2 S=3.14*R*R 輸出面積S,說明：該算法中在執(zhí)行時(shí)已包含計(jì)算所需的初始數(shù)據(jù)，不必另 外提供數(shù)據(jù)，因此沒有輸入，即有0個輸入。,返回,例5：寫出算法：從鍵盤輸入圓的半徑，計(jì)算其面積,解答： 輸入圓的半徑R S=3.14*R*R 輸出面積S,說明：該算法中計(jì)算面積所需的初始數(shù)據(jù)半徑R待 定，需要在算法執(zhí)行時(shí)從鍵盤輸入。,返回,請畫出例6的流程圖,解答： 輸入圓的半徑R S=3.14*R*R C=2*3.1

5、4*R 輸出面積S，周長C,例6：求從鍵盤輸入的任意半徑的圓的面積和周長,開始,結(jié)束,S=3.14*R*R,輸入R,輸出面積S、周長C,C=2*3.14*R,例6：求從鍵盤輸入的任意半徑的圓的面積和周長,解答： 輸入圓的半徑R S=3.14*R*R C=2*3.14*R 輸出面積S，周長C,說明：通過前兩個例子可以知道，算法可能有1個或多 個輸出。,返回,參考算法一：,將3毫升的量杯裝滿 將3毫升量杯中的水注入5毫升量杯 將3毫升的量杯裝滿 將3毫升量杯中的水注入5毫升量杯，注滿后3毫升量杯中剩余1毫升水。,返回,參考算法二：,將5毫升的量杯裝滿 將5毫升量杯中的水注入3毫升量杯，注滿后5毫升

6、量杯中剩余2毫升水 將3毫升量杯倒空 將5毫升量杯中剩余的2毫升注入3毫升量杯 將5毫升量杯裝滿 將5毫升量杯中的水注入3毫升量杯，注滿后5毫升量杯中剩余4毫升水 將3毫升量杯倒空 將5毫升量杯中的水注入3毫升量杯，注滿后5毫升量杯中剩余1毫升水,返回,二、算法的描述,1、用自然語言描述算法,例題：雞兔同籠問題 一個籠子里有雞和兔，現(xiàn)在只知道里面一共有a個頭，b個腳，雞和兔各有多少只？試設(shè)計(jì)一個求解的算法，并用自然語言描述出來。,1、用自然語言描述算法,1）分析問題 設(shè)所求的雞數(shù)是x，兔數(shù)是y，已知籠子里的頭數(shù)是a,腳數(shù)是b，依題意得到如下的方程組：,解方程組得：x=2a-b/2 y=b/2-

7、a,1、用自然語言描述算法,2)設(shè)計(jì)算法 輸入a和b的值； 求x=2a-b/2； 求y=b/2-a； 輸出x和y的值； 結(jié)束。,雞兔同籠流程圖,開始,輸入a,b的值,求x=2a-b/2,求y=b/2-a,輸出x,y的值,結(jié)束,3、用程序代碼描述算法,Input a,b,輸入a和b的值；,雞兔同籠,求x=2a-b/2；,求y=b/2-a；,輸出x和y的值；,結(jié)束。,x=2a-b/2,y=b/2-a,print x,y,算法描述語言有： 1、自然語言 2、流程圖 3、偽代碼,二、算法的描述,算法的表示方法優(yōu)缺點(diǎn)：,自然語言（通過文字來描述解決問題的過程） 優(yōu)點(diǎn)：容易理解。 缺點(diǎn)：書寫煩瑣，具有不確

8、切性，容易引起歧義，造成誤解； 對較復(fù)雜的問題，用自然語言難以表達(dá)準(zhǔn)確； 計(jì)算機(jī)不能直接識別和執(zhí)行。 流程圖（用圖形符號來描述算法） 必須要有一組統(tǒng)一規(guī)定、含義確定的專用符號； 優(yōu)點(diǎn)：用流程圖表示算法比較直觀、形象； 缺點(diǎn)：計(jì)算機(jī)不能識別和執(zhí)行。 程序代碼使用程序設(shè)計(jì)語言描述算法。,下一頁,流程圖中的符號的用途,返回,例7：請畫出例5的流程圖,解答： 輸入圓的半徑R S=3.14*R*R 輸出面積S,例5：寫出算法：從鍵盤輸入圓的半徑，計(jì)算其面積,開始,結(jié)束,S=3.14*R*R,輸入R,輸出S,課堂練習(xí)1： 物理老師想編寫一個描述小球做平拋的運(yùn)動軌跡程序（小球運(yùn)動時(shí)間限定在（1-100秒），你能否幫助先用流程圖描述一下解體的方法？ 描課堂練習(xí)