算法初步-高級語言程序設(shè)計-課件-北京工業(yè)大學(xué).ppt

《算法初步-高級語言程序設(shè)計-課件-北京工業(yè)大學(xué).ppt》由會員分享，可在線閱讀，更多相關(guān)《算法初步-高級語言程序設(shè)計-課件-北京工業(yè)大學(xué).ppt（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第3講算法初步,一、解題方法二、算法舉例---窮舉法三、算法舉例---遞推與迭代法四、良好的編程風(fēng)格,一、解題方法,分析問題，想出策略；自頂向下，逐步求精。例如，編寫一個通訊錄程序通訊錄需要存儲什么數(shù)據(jù)？存在什么地方？程序的功能輸入一個新名字刪除一個名字顯示整個通訊錄搜索一個名字進(jìn)入、退出程序等……。具體到每一項功能菜單，將這些功能分類別設(shè)計,用計算機(jī)解決問題的步驟,分析問題選擇解決方案編寫程序調(diào)試程序測試程序,,數(shù)據(jù)結(jié)構(gòu)設(shè)計算法設(shè)計,程序=數(shù)據(jù)結(jié)構(gòu)+算法,如何組織數(shù)據(jù)C語言提供了豐富的手段,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)對象：分析所研究問題，提煉出性質(zhì)相同的數(shù)據(jù)元素。對象之間的關(guān)系通訊錄數(shù)據(jù)用于管理的數(shù)據(jù)在此基礎(chǔ)上，想出處理的方法---算法,算法,算法是指用計算機(jī)解決問題的程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成。算法的特征：確定性邏輯性有窮性,用程序流程圖描述算法,描述算法的方法有很多程序流程圖：圖形化的描述程序執(zhí)行過程（圖是工程師的語言）使得思想集中于算法設(shè)計，不受語言細(xì)節(jié)干擾再依據(jù)算法，用語言編寫程序程序流程圖的圖形符號：P60,開始,結(jié)束,顯示菜單,獲取用戶選擇,處理用戶選擇,用戶選擇了結(jié)束,,,,,,,,,N,Y,,再繼續(xù)細(xì)化，畫子流程圖,主程序,輸入新名字,刪除名字,顯示整個通訊錄,搜索一個名字,進(jìn)入程序,……,,,,,,,,,……,例：求一元二次方程ax2+bx+c=0的解,,,#include#includemain(){inta,b,c,t;printf("Inputa,b,c：");scanf("%d%d%d",}},二、算法舉例---窮舉法,列出所有可能情況，逐個排查，從中找出符合條件的解。關(guān)鍵是明確問題所有可能性，注意可能情況是有限的。用什么基本控制結(jié)構(gòu)？優(yōu)點？缺點？,循環(huán),時間效率可能不高,問題分析利用素數(shù)的定義來判別。對于給定整數(shù)x，用2~x-1之間的每個整數(shù)試除，若都不能整除則是素數(shù)，否則不是素數(shù)。一次試除成功（不能整除），并不能說明x是素數(shù)，只有所有試除都成功，才能斷定x是素數(shù)；但一次試除失?。苷瑒t可斷定x不是素數(shù),例：判斷給定整數(shù)是否是素數(shù),解決方案數(shù)據(jù)結(jié)構(gòu)設(shè)計整型變量存儲素數(shù)：intx;算法設(shè)計窮舉的范圍---循環(huán)開始和結(jié)束：2~x-1數(shù)據(jù)元素的關(guān)系---循環(huán)的步進(jìn)：1逐個排查的過程---循環(huán)的內(nèi)容：試除,例：判斷給定整數(shù)是否是素數(shù),,#includemain(){intx,t;printf("Enteraninteger:");scanf("%d",},問題描述某人有錢百枚，希望買一百只雞；公雞5枚錢一只，母雞3枚錢一只，而小雞3只1枚錢。試問：如果用百枚錢買百只雞，可以包含幾只公雞、幾只母雞和幾只小雞問題分析公雞、母雞和小雞的數(shù)量之和為100。采用窮舉法，將100只雞中的所有公雞、母雞和小雞的組合枚舉一遍，找出價錢正好是100的組合。,例：百錢買百雞,解決方案數(shù)據(jù)結(jié)構(gòu)設(shè):x——公雞的個數(shù)y——母雞的個數(shù)z——小雞的個數(shù)算法遍歷x、y、z，三層循環(huán)嵌套循環(huán)起止：x：0~100/5；y：0~100/3；z：0~100步進(jìn)：1循環(huán)內(nèi)容：排查條件：5x+3y+z/3=100 x+y+z=100,,15x+9y+z=300,#includemain(){intx,y,z;/*公雞、母雞、小雞的個數(shù)*/for(x=0;x<=100/5;x++)for(y=0;y<=100/3;y++)for(z=0;z<=100;z++){if(x+y+z==100}},三、算法舉例---遞推與迭代法,遞推與迭代的基本策略是將復(fù)雜的運算劃分為可以重復(fù)操作的分步遞增方式進(jìn)行求解的解題方法。關(guān)鍵在于：遞推公式：據(jù)前項計算后項的重復(fù)計算公式邊界條件：計算的初值如：遞推公式：n!=n*(n-1)!---循環(huán)體邊界條件：0!=1---初始,P67,例3-4:等比數(shù)列前n項求和,Sn=a1+a2+a3+a4+…+an,,循環(huán)體：,初始值：,變量：比率用變量ratio,變量：item,和：sum,累加,,main(){inti;longitem,ratio,sum,n;printf("\nEnterthefirstitemandratio:");scanf("%ld%ld",},例：按位分解整數(shù),問題分析利用整除求余運算實現(xiàn)將整數(shù)分解例如，73267326/1000可得到最高位7；7326%1000可得到余數(shù)326；按此規(guī)律繼續(xù)---遞推公式。到個位時結(jié)束---邊界條件。,#includemain(){longx,y,m;printf("Enteraninteger:");scanf("%ld",},四、良好的編程風(fēng)格,依據(jù)規(guī)約，編寫正確的程序完全按要求實現(xiàn)功能格式一行一語句。太長的語句可占多行，使其不溢出畫面。括號嵌套縮進(jìn)對應(yīng)，不要齊頭并進(jìn)適當(dāng)留空格、空行等，增加可讀性…下面是一段微軟的代碼：,intWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,LPSTRlpCmdLine,intnCmdShow){MSGmsg;HACCELhAccelTable;//InitializeglobalstringsLoadString(hInstance,IDS_APP_TITLE,szTitle,MAX_LOADSTRING);LoadString(hInstance,IDC_A,szWindowClass,MAX_LOADSTRING);MyRegisterClass(hInstance);//Performapplicationinitialization:if(!InitInstance(hInstance,nCmdShow)){returnFALSE;}hAccelTable=LoadAccelerators(hInstance,(LPCTSTR)IDC_A);//Mainmessageloop:while(GetMessage(},不好的例子,#includeintmain(){printf("Hello,World.\n");return0;},main(){inti,x,max=0;for(i=0;imax){max=x;}}},//與本書P47對比,每個變量有明確的角色注釋（反映你的文字水平）文件注釋函數(shù)注釋程序片斷關(guān)鍵點注釋關(guān)鍵數(shù)據(jù)結(jié)構(gòu)注釋通常沒必要每句話寫注釋程序員友好你的程序是給人看的，不要寫的晦澀難懂。,正確性可懂度時間復(fù)雜度空間復(fù)雜度健壯性可擴(kuò)展性可移植性…,