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

7-解決問題的方法學

有效的解決計算機編程問題2015

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

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

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

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

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

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

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

+

2

=1010(2)

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

12345Output:

ones:1;zeros:0ones:2;zeros:1ones:4;zeros:1ones:5;zeros:3ones:7;zeros:4步驟#4-修復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);}測試

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

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