2015春編程課件-c基礎(chǔ)07解決問題的方法學(xué)47

7-解決問題的方法學(xué)

有效的解決計(jì)算機(jī)編程問題2015

Spring,Xi'an本章內(nèi)容解決問題理解需求分析問題頭腦風(fēng)暴使用筆和紙檢查你的想法解決問題

從混亂到方法學(xué)的途徑如何解決問題閱讀和分析問題使用一些紙和筆打草稿思考、創(chuàng)造和嘗試你的想法將問題劃為子問題檢查你的想法選擇合適的數(shù)據(jù)結(jié)構(gòu)思考效率一步步實(shí)現(xiàn)你的算法認(rèn)真的測(cè)試你的解答理解需求閱讀和分析問題假定你在傳統(tǒng)的計(jì)算機(jī)編程考試或競賽你有6個(gè)小時(shí)來解決5個(gè)問題首先仔細(xì)閱讀所有的問題，并試著評(píng)估每個(gè)問題的復(fù)雜程度閱讀需求，不要編造需求！開始先解決大部分簡單問題最后留下復(fù)雜問題著手下一個(gè)問題，當(dāng)前一個(gè)問題完全解決并良好的測(cè)試后分析問題示例：我們給定了如下3個(gè)問題：數(shù)字集合對(duì)當(dāng)前數(shù)字集合中的數(shù)，進(jìn)行計(jì)數(shù)學(xué)生讀入一組學(xué)生，打印有最高分的學(xué)生的姓名二進(jìn)制表達(dá)找出數(shù)集在二進(jìn)制形式下，所有0的個(gè)數(shù)和1的個(gè)數(shù)分析問題仔細(xì)閱讀問題，一點(diǎn)點(diǎn)想從最簡單的問題做到最難的問題數(shù)字集合，無論何時(shí)找到這個(gè)數(shù)，計(jì)數(shù)變量加一學(xué)生暫時(shí)的最高分?jǐn)?shù)學(xué)生二進(jìn)制表達(dá)如果我們知道1的數(shù)量，就能找到0的數(shù)量。使用紙和筆

形象化和草稿化你的想法使用草稿本和筆在沒有草稿本和筆之前，絕不開始解題你必須將想法變?yōu)椴莞寮埡凸P是最好的形象化工具允許頭腦有效率的思考用紙比鍵盤/屏幕工作更快其他形象化工具也能很好的工作紙和筆思考“二進(jìn)制表達(dá)”問題我們能以打草稿的方式開始思考一些想法立刻來了，如除以2并檢查余數(shù)右移位，檢查最右位左移位，檢查最左位只數(shù)0只數(shù)1同時(shí)數(shù)0和1創(chuàng)造想法

思考，創(chuàng)造想法和檢查它們思考，創(chuàng)造和試驗(yàn)想法首先舉一個(gè)問題的示例草稿紙上畫出來下來試著創(chuàng)造一些能夠操作示例的想法檢查是否想法將操作其他案例試著找到案例打破你的想法試著挑戰(zhàn)不尋常的案例如果你發(fā)現(xiàn)想法不正確，試著去修正或者創(chuàng)造新的想法創(chuàng)造和試驗(yàn)想法-示例考慮“二進(jìn)制表達(dá)”問題想法#1：除以2，并檢查余數(shù)需要這么做多少次？哪里檢查？想法#2：右移位，檢查最右位左移還是右移？要重復(fù)多少次？足夠快么？檢查你的想法

在檢查之前不要前進(jìn)檢查想法用示例檢查想法對(duì)于找到問題，這是在想法實(shí)現(xiàn)之前更好的方法這當(dāng)代碼寫出來時(shí)，徹底的改變想法將花去許多時(shí)間和精力仔細(xì)選擇檢查示例示例應(yīng)該足夠簡單，能一分鐘內(nèi)手算檢查示例應(yīng)該足夠復(fù)雜，能覆蓋大部分案例，而不是獨(dú)立的案例如果需要，創(chuàng)造新想法當(dāng)你發(fā)現(xiàn)想法無法適用于所有的案例，要做什么？試著修改想法有時(shí)候小的改動(dòng)能夠修復(fù)問題創(chuàng)造新想法并且仔細(xì)的檢查迭代（重復(fù)）常見于第一個(gè)想法并不完美創(chuàng)造新想法，檢查之，試更多的案例，找到問題，修改，創(chuàng)造新想法，等效率和性能

你的算法足夠快么？效率思考思考效率在寫下第一行代碼前估計(jì)預(yù)期運(yùn)行的時(shí)間（如漸進(jìn)復(fù)雜性）檢查需求你的算法能足夠快，并且保持下去么別想著實(shí)現(xiàn)算法，并在測(cè)試時(shí)找到哪兒慢了這是在浪費(fèi)時(shí)間并不總是需要效率最佳方案有時(shí)不是必須的仔細(xì)閱讀你的問題語句有時(shí)候古怪的方案能夠滿足你的需求并且消耗更少的時(shí)間示例：如果你需要排序n個(gè)數(shù)，任何算法都能運(yùn)行，當(dāng)n在[0…500]內(nèi)僅僅當(dāng)需要的時(shí)候，再實(shí)現(xiàn)復(fù)雜算法實(shí)現(xiàn)

編碼并且逐步測(cè)試開始編碼：檢查清單在你找到滿足需求的正確想法之前，不要編碼在你創(chuàng)造出正確的解決問題想法之前，你能寫什么？編碼前，檢查下列清單：確保你良好的理解了需求確保你有好的思路確保正確思路確保你知道應(yīng)當(dāng)使用什么數(shù)據(jù)結(jié)構(gòu)確保充足的性能代碼檢查清單-示例開始編碼之前的檢查清單：確保你良好的理解了需求是的，對(duì)每一位的值進(jìn)行記錄確保正確思路是的，想法看上去正確，并通過了測(cè)試確保充足的性能線性運(yùn)行時(shí)間->好性能逐步實(shí)現(xiàn)算法“逐步”方法總是比“做完再測(cè)”要好實(shí)現(xiàn)一段代碼就測(cè)試它接著實(shí)現(xiàn)另一段代碼并測(cè)試它最后將所有的代碼段放一起，并測(cè)試小增量（步）能很早的顯示錯(cuò)誤“大爆炸”式的集成需要更多時(shí)間步驟#1-檢查第一位的值現(xiàn)在我們有了第一位的值數(shù)字發(fā)生了什么？我們還需要第一位么？通過右移刪除它intnumber=10;intfirstBit=number&1;intnumber=10;intfirstBit=number&1;number>>=1;步驟#1-測(cè)試測(cè)試是否得到了正確的第一位盡早的得到反饋：預(yù)期的結(jié)果：intnumber=10;intfirstBit=number&1;number>>=1;Console.WriteLine(firstBit);Console.WriteLine(number);0//第一位5//沒有第一位之后步驟2-得到這個(gè)數(shù)的所有位我們想要檢查多少位？這個(gè)數(shù)的所有但是他們是多少示例：數(shù)字1010(10)=8

+

2

=1010(2)

–>4bits怎樣找出何時(shí)停止檢查？當(dāng)右移得到越來越多的0在某點(diǎn)這個(gè)數(shù)即將成為0步驟#2-得到這個(gè)數(shù)的所有位直到這個(gè)數(shù)等于0檢查位的值右移這個(gè)數(shù)while(number!=0){intfirstBit=number&1;number>>=1;Console.Write("{0}",firstBit);}步驟#2-測(cè)試測(cè)試10測(cè)試1111看上去正確0101111010100011111=1024+64+16+4+2+1=210+26+24+22 +21+20步驟#3-檢查當(dāng)前位值迄今為止：我們能獲取數(shù)中所有位的值對(duì)0和1的數(shù)量計(jì)數(shù)while(number!=0){intfirstBit=number&1;number>>=1;if(firstBit==1){ oneCount++;}else{ zeroCount++;}}步驟#3-測(cè)試測(cè)試數(shù)111(1101111(2))結(jié)果正確測(cè)試數(shù)1234(10011010010(2))結(jié)果正確ones:6zeros:1ones:5zeros:6步驟#4-全部集合計(jì)數(shù)遍歷所有數(shù)字對(duì)位計(jì)數(shù)intzeroCount=0,oneCount=0,n=5;for(inti=0;i<n;i++){intnumber=int.Parse(Console.ReadLine());while(number!=0){intfirstBit=number&1;number>>=1;if(firstBit==1){oneCount++;}else{zeroCount++;}}Console.WriteLine("ones:{0};zeros:{1}",oneCount,zeroCount);}步驟#4-全部集合計(jì)數(shù)結(jié)果驚人的不正確：結(jié)果驚人的不正確：0和1的計(jì)數(shù)發(fā)生了所有數(shù)堆積的情況我們定義的計(jì)數(shù)器在循環(huán)的迭代外部將計(jì)數(shù)器放到內(nèi)部Input:

12345Output:

ones:1;zeros:0ones:2;zeros:1ones:4;zeros:1ones:5;zeros:3ones:7;zeros:4步驟#4-修復(fù)bug現(xiàn)在正確了intn=5;for(inti=0;i<n;i++){intzeroCount=0,oneCount=0;intnumber=int.Parse(Console.ReadLine());while(number!=0){intfirstBit=number&1;number>>=1;if(firstBit==1){oneCount++;}else{zeroCount++;}}Console.WriteLine("ones:{0};zeros:{1}",

oneCount,zeroCount);}測(cè)試

認(rèn)真測(cè)試你的方案認(rèn)真測(cè)試你的方案聰明的軟件工程師這樣說：創(chuàng)造好的想法并實(shí)現(xiàn)，是方案的一半測(cè)試是方案的另一半總是認(rèn)真測(cè)試你的方案投入測(cè)試一個(gè)100%解決的問題，好過2或3個(gè)部分解決的問題測(cè)試已有問題比泛泛的解決另一個(gè)問題花費(fèi)更少的時(shí)間如何測(cè)試測(cè)試并不能證明沒有缺陷只能降低缺陷率良好的測(cè)試方案更容易正確以良好的有代表性的主要案例開始測(cè)試不要用小型孤立案例大型復(fù)雜案例，但小型能夠容易檢查如何測(cè)試測(cè)試邊界案例如：如果n∈[0..500]->

試驗(yàn)n=0,n=1,n=2,n=499,n=500如果bug找到了，在修復(fù)它之后重復(fù)所有的測(cè)試以避免又出現(xiàn)其他bug運(yùn)行負(fù)載load測(cè)試如何確認(rèn)算法足夠快并滿足需求？使用復(fù)制粘貼來創(chuàng)建大量測(cè)試數(shù)據(jù)閱讀問題語句仔細(xì)閱讀問題語句你的方案準(zhǔn)確的寫出所期望的？你的輸出遵循所要求的格式？你移除了調(diào)試輸出？確認(rèn)解決了要求的問題，不要只是想著滿足了問題示例：“寫一段代碼，打印n個(gè)元素組合的個(gè)數(shù)”意味著打印一個(gè)數(shù)，不是組合集合！測(cè)試-示例用10個(gè)數(shù)集來測(cè)試發(fā)現(xiàn)一系列錯(cuò)誤->更換算法更改算法計(jì)數(shù)器不要再重置到0測(cè)試是否新算法可運(yùn)行測(cè)試1個(gè)數(shù)測(cè)試2個(gè)數(shù)測(cè)試沒有數(shù)52000個(gè)數(shù)的復(fù)雜測(cè)試測(cè)試10000個(gè)數(shù)-示例intn=10000,startNumber=111;for(inti=startNumber;i<startNumber+n;i++){intzeroCount=0;intoneCount=0;//intnumber=int.Parse(Console.ReadLine());intnumber=i;intoriginalNumber=number;while(number!=0){intfirstBit=number&1;number>>=1;if(firstBit==1){oneCount++;}else{zeroCount++;}}}用簡單的類型檢查替換從控制臺(tái)讀入測(cè)試10000個(gè)數(shù)-示例結(jié)果很完美111(10)=1101111(2)->ones:6;zeros:1…10110(10)=10011101111110(2)->ones:10;zeros:4測(cè)試要點(diǎn)指明二項(xiàng)式表達(dá)的任務(wù)程序從控制臺(tái)讀入整數(shù)N和BN個(gè)整數(shù)當(dāng)打印和測(cè)試程序時(shí)不要從控制臺(tái)讀取數(shù)據(jù)先將數(shù)字硬編碼之后完成當(dāng)你確定可運(yùn)行時(shí)硬編碼輸入-示例//硬編碼輸入數(shù)據(jù)–為測(cè)試作準(zhǔn)備intn=5;intnum1=11;intnum2=127;intnum3=0;intnum4=255;intnum5=24;//從客戶端讀取輸入//