2015春编程课件-c基础07解决问题的方法学47

7-解决问题的方法学

有效的解决计算机编程问题2015

Spring,Xi'an本章内容解决问题理解需求分析问题头脑风暴使用笔和纸检查你的想法解决问题

从混乱到方法学的途径如何解决问题阅读和分析问题使用一些纸和笔打草稿思考、创造和尝试你的想法将问题划为子问题检查你的想法选择合适的数据结构思考效率一步步实现你的算法认真的测试你的解答理解需求阅读和分析问题假定你在传统的计算机编程考试或竞赛你有6个小时来解决5个问题首先仔细阅读所有的问题，并试着评估每个问题的复杂程度阅读需求，不要编造需求！开始先解决大部分简单问题最后留下复杂问题着手下一个问题，当前一个问题完全解决并良好的测试后分析问题示例：我们给定了如下3个问题：数字集合对当前数字集合中的数，进行计数学生读入一组学生，打印有最高分的学生的姓名二进制表达找出数集在二进制形式下，所有0的个数和1的个数分析问题仔细阅读问题，一点点想从最简单的问题做到最难的问题数字集合，无论何时找到这个数，计数变量加一学生暂时的最高分数学生二进制表达如果我们知道1的数量，就能找到0的数量。使用纸和笔

形象化和草稿化你的想法使用草稿本和笔在没有草稿本和笔之前，绝不开始解题你必须将想法变为草稿纸和笔是最好的形象化工具允许头脑有效率的思考用纸比键盘/屏幕工作更快其他形象化工具也能很好的工作纸和笔思考“二进制表达”问题我们能以打草稿的方式开始思考一些想法立刻来了，如除以2并检查余数右移位，检查最右位左移位，检查最左位只数0只数1同时数0和1创造想法

思考，创造想法和检查它们思考，创造和试验想法首先举一个问题的示例草稿纸上画出来下来试着创造一些能够操作示例的想法检查是否想法将操作其他案例试着找到案例打破你的想法试着挑战不寻常的案例如果你发现想法不正确，试着去修正或者创造新的想法创造和试验想法-示例考虑“二进制表达”问题想法#1：除以2，并检查余数需要这么做多少次？哪里检查？想法#2：右移位，检查最右位左移还是右移？要重复多少次？足够快么？检查你的想法

在检查之前不要前进检查想法用示例检查想法对于找到问题，这是在想法实现之前更好的方法这当代码写出来时，彻底的改变想法将花去许多时间和精力仔细选择检查示例示例应该足够简单，能一分钟内手算检查示例应该足够复杂，能覆盖大部分案例，而不是独立的案例如果需要，创造新想法当你发现想法无法适用于所有的案例，要做什么？试着修改想法有时候小的改动能够修复问题创造新想法并且仔细的检查迭代（重复）常见于第一个想法并不完美创造新想法，检查之，试更多的案例，找到问题，修改，创造新想法，等效率和性能

你的算法足够快么？效率思考思考效率在写下第一行代码前估计预期运行的时间（如渐进复杂性）检查需求你的算法能足够快，并且保持下去么别想着实现算法，并在测试时找到哪儿慢了这是在浪费时间并不总是需要效率最佳方案有时不是必须的仔细阅读你的问题语句有时候古怪的方案能够满足你的需求并且消耗更少的时间示例：如果你需要排序n个数，任何算法都能运行，当n在[0…500]内仅仅当需要的时候，再实现复杂算法实现

编码并且逐步测试开始编码：检查清单在你找到满足需求的正确想法之前，不要编码在你创造出正确的解决问题想法之前，你能写什么？编码前，检查下列清单：确保你良好的理解了需求确保你有好的思路确保正确思路确保你知道应当使用什么数据结构确保充足的性能代码检查清单-示例开始编码之前的检查清单：确保你良好的理解了需求是的，对每一位的值进行记录确保正确思路是的，想法看上去正确，并通过了测试确保充足的性能线性运行时间->好性能逐步实现算法“逐步”方法总是比“做完再测”要好实现一段代码就测试它接着实现另一段代码并测试它最后将所有的代码段放一起，并测试小增量（步）能很早的显示错误“大爆炸”式的集成需要更多时间步骤#1-检查第一位的值现在我们有了第一位的值数字发生了什么？我们还需要第一位么？通过右移删除它intnumber=10;intfirstBit=number&1;intnumber=10;intfirstBit=number&1;number>>=1;步骤#1-测试测试是否得到了正确的第一位尽早的得到反馈：预期的结果：intnumber=10;intfirstBit=number&1;number>>=1;Console.WriteLine(firstBit);Console.WriteLine(number);0//第一位5//没有第一位之后步骤2-得到这个数的所有位我们想要检查多少位？这个数的所有但是他们是多少示例：数字1010(10)=8

+

2

=1010(2)

–>4bits怎样找出何时停止检查？当右移得到越来越多的0在某点这个数即将成为0步骤#2-得到这个数的所有位直到这个数等于0检查位的值右移这个数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-检查当前位值迄今为止：我们能获取数中所有位的值对0和1的数量计数while(number!=0){intfirstBit=number&1;number>>=1;if(firstBit==1){ oneCount++;}else{ zeroCount++;}}步骤#3-测试测试数111(1101111(2))结果正确测试数1234(10011010010(2))结果正确ones:6zeros:1ones:5zeros:6步骤#4-全部集合计数遍历所有数字对位计数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-全部集合计数结果惊人的不正确：结果惊人的不正确：0和1的计数发生了所有数堆积的情况我们定义的计数器在循环的迭代外部将计数器放到内部Input:

12345Output:

ones:1;zeros:0ones:2;zeros:1ones:4;zeros:1ones:5;zeros:3ones:7;zeros:4步骤#4-修复bug现在正确了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);}测试

认真测试你的方案认真测试你的方案聪明的软件工程师这样说：创造好的想法并实现，是方案的一半测试是方案的另一半总是认真测试你的方案投入测试一个100%解决的问题，好过2或3个部分解决的问题测试已有问题比泛泛的解决另一个问题花费更少的时间如何测试测试并不能证明没有缺陷只能降低缺陷率良好的测试方案更容易正确以良好的有代表性的主要案例开始测试不要用小型孤立案例大型复杂案例，但小型能够容易检查如何测试测试边界案例如：如果n∈[0..500]->

试验n=0,n=1,n=2,n=499,n=500如果bug找到了，在修复它之后重复所有的测试以避免又出现其他bug运行负载load测试如何确认算法足够快并满足需求？使用复制粘贴来创建大量测试数据阅读问题语句仔细阅读问题语句你的方案准确的写出所期望的？你的输出遵循所要求的格式？你移除了调试输出？确认解决了要求的问题，不要只是想着满足了问题示例：“写一段代码，打印n个元素组合的个数”意味着打印一个数，不是组合集合！测试-示例用10个数集来测试发现一系列错误->更换算法更改算法计数器不要再重置到0测试是否新算法可运行测试1个数测试2个数测试没有数52000个数的复杂测试测试10000个数-示例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个数-示例结果很完美111(10)=1101111(2)->ones:6;zeros:1…10110(10)=10011101111110(2)->ones:10;zeros:4测试要点指明二项式表达的任务程序从控制台读入整数N和BN个整数当打印和测试程序时不要从控制台读取数据先将数字硬编码之后完成当你确定可运行时硬编码输入-示例//硬编码输入数据–为测试作准备intn=5;intnum1=11;intnum2=127;intnum3=0;intnum4=255;intnum5=24;//从客户端读取输入//