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

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