《(补充)程序设计基本方法》由会员分享，可在线阅读，更多相关《(补充)程序设计基本方法（28页珍藏版）》请在金锄头文库上搜索。
1、用程序解决问题的基本方法（一）,逼近法 迭代与递推 穷举法,0,y,x,a,b,f(x),例如：求曲线 在a-b之间的面积,逼近法,这种方法，将问题分成若干的类似的计算单元根据这些计算单元的值来逐渐逼近最终的结果。 程序实现的步骤： 找到可以逐渐逼近的每一个单元的表达方式 梯形公式 矩形公式 使用循环语句来构造整个计算框架 逐步逼近 在题目可以接受的条件下结束循环。,求值,利用“正多边形逼近”的方法来计算 祖冲之的算法 过程：利用圆内接正六边形边长等于半径的特点，将边数翻翻，作出12边形，求出边长。重复这个过程，就可以获得所需精度的近似值。 当边长为2b的时候，边数为i，边数加倍后新的正多边形
2、的边长为：,练习,写出 计算sinx 在（-/2，/2）所围成面积的主要代码片段。,例题,迭代相关（特点是变量的值在变化） /4 1-1/3+1/5-1/7+1/9- 递推相关（变量新值由旧值或其它值推出） 计算 N!,迭代与递推,迭代就是用不断变化的新值替代其旧值。例如，一笔存款每年自动转存，就形成利滚利的情况，本金每年不同，不断迭代。 递推是由一个变量的值推出另外的变量的值。例如若每代人之间的年龄相差25岁。则由一个人的年龄推出起父亲年龄、爷爷年龄的过程，就称为递推。 实际上，迭代与递推没有严格的区别。例如在上述存款问题中，将各年的本金用不同的变量表示，就成了递推问题。,程序的实现步骤,第
3、一步：找到一个可以方便地进行迭代或者递推的表达式 第二步：根据这个表达式，找到合适的循环变量，并确定其初值和终止条件 第三步：构造循环程序框架，实现迭代或者递推的表达式。,例子：猴子吃桃子,一天一只小猴子摘下一堆桃子，当即吃去一半，还觉得不过瘾，又多吃了一个。第二天接着吃了前一天剩下的一半，馋不忍罢又多吃了一个。以后每天如此。到第十天小猴子去吃时，只剩下一个桃子了。问小猴子共摘了多少桃子。,分析,设小猴子当初共摘了x个桃子。则根据题意，有： 第1天： 吃掉x/2 + 1个， 剩下x/2 1 = （x 2）/2个； 第2天： 吃掉（x 2）/2）/2 + 1个， 剩下（x 2）/2 （x 2）/
4、2 + 1） = （x 2）/2 -（x 2 + 22）/22 =（x 2 22）/22 个； 第i天： 剩下：（x 2 22 - - 2i）/2i个； 第9天： 剩下：（x 2 22 - - 29）/29 = 1 （第10天小猴子看到的那1个桃子）。,这种求解方法有如下缺点,1）人的干预太多，不适合计算机直接求解； 2）需要进行的计算比较复杂。假设，是到了第100天 才看到剩下的1个桃子，则要进行 299 + 299 + 298 + + 22 + 2的计算。,建立递推等式,用递推法，即从第10天看到的那个桃子开始往前推： 第9天的桃子数为 peach9 = (peach10 +1)*2； 第
5、8天的桃子数为 peach8 = (peach9 +1)*2； 第i天的桃子数为 peachi = (peachi+1 +1)*2； 于是，就建立起了递推式或迭带式。从初始值开始，迭代9次，就得到第1天的桃子数。,穷举法,有许多问题的解“隐藏”在多个可能之中。穷举就是对多种可能情形一一测试，从多种可能中找出符合条件的（一个或一组）解。当然，也可能得出无解的结论。 程序实现的步骤： 先为所有的情形，设计组合变量 找到“条件“的表达方式 使用多重循环来实现穷举,例题一、百钱买百鸡,公元五世纪末，我国古代数学家张丘建 在算经中提出了如下问题：鸡翁一值 钱五，鸡母一值钱三，鸡雏三值钱一。凡 百钱买百鸡
6、，问鸡翁、母、雏各几何？,分析,从0开始（例如：没有公鸡，没有母鸡，没有小鸡），列举三种鸡的全部组合。 将每一种组合的价格同最终条件进行比较，并确定满足要求的鸡的组合方式。,程序实现的步骤,1.为每一种鸡的数量定义一个变量 如： cocks、hens、chicks 2.找到最终的判断等式 等式一：5 * cocks + 3 * hens + chicks / 3.0 = 100 等式二： cocks + hens + chicks = 100 3.用多重循环（嵌套）来实现全部的组合,循环部分的实现,for(chicks = 0; chicks 100; chicks +) for(cocks
7、= 0; cocks 100; cocks +) for(hens = 0; hens 100; hens +) if(等式一成立&等式二成立） 输出此时鸡的数量； ,程序的优化（一）,cocks、hens、chicks的取值范围分别应为： cocks：020 (假如100元全买cocks，最多20只) hens：033(假如100元全买hens，最多33只) chicks：0100(假如全买chicks，最多100只) 因此可以将循环的范围缩小，加快计算速度。,for(cocks = 0; cocks = 20; cocks +) for(hens = 0; hens = 33; hens
8、+) for(chicks = 0; chicks = 100; chicks +) if(等式一成立） 输出此时鸡的数量； ,程序的优化（二）,使用等式二的条件，将循环减少为两层 cocks + hens + chicks = 100,for(cocks = 0; cocks = 20; cocks +) for(hens = 0; hens = 33; hens +) chicks = 100 hens cocks; if(等式一成立） 输出此时鸡的数量； ,#include void main() int cocks, hens, chicks; printf( “n公鸡数t母鸡数t小鸡
9、数“); for( cocks=0; cocks20; cocks+) /* 穷举cocks */ for( hens=0; hens33; hens+) chicks = 100 cocks - hens; if(5*cocks+3*hens+chicks/3.0=100) printf(“%dt%dt%dn”, cocks, hens, chicks); ,完整的程序,运行结果： 公鸡数 母鸡数 小鸡数 0 25 75 4 18 78 8 11 81 12 4 84,例题二：推断名次,某宿舍住有A、B、C、D、E共5人。期末考试结束，辅导员来到这个宿舍，告诉同学们：你们这个宿舍的同学本学期
10、囊括了本课全班成绩的前5名。同学们问，那我们5个人的名次，是怎么排的呀？老师说，你们猜吧。于是大家就推测起来： A说：E一定是第一； B说：我可能是第二； C说：A一定最不妙； D说：C肯定不会最好； E说：D会得第一。 老师说：我再告诉你们一下吧： （1）你们的推测中考第一和考第二的同学的推测是正确的； （2）E肯定不是第二名，也不是第三名。 下面请你们用C语言程序来验证你们的推测。,分析,列出A、B、C、D、E5人全部可能的名次组合 利用这个名次组合同，题目中给出的各种判断条件进行比较，找到满足条件的组合,程序实现步骤,第一步：为每一个人的名次定义一个变量 如： a b c d e 第二步
11、：找到最终的判断等式 等式一：由于是对A、B、C、D、E进行排队，所以a,b,c,d,e的值不会相同 等式二：由于“ E肯定不是第二名，也不是第三名”，所以有表达式 e != 2以及 e != 3 等式三：由于是前5名，所以有a + b + c + d + e = 1 + 2 + 3 + 4 + 5 = 15,其它条件,由于为“真”的推测的表达式的值应为“1”，为“假”的推测的表达式的值应为0，并且5位学生的推测中，只有“考第一和考第二的同学的推测是正确的”，即同学们的推测中只有两人的推测是对的，于是有表达式： (e=1) + (b=2) + (a=5) + (c!=1)+(d=1) = 2
12、,5位同学的推测： e = 1 （A的推测） b = 2 （B的推测） a = 5 （C的推测） c != 1 （D的推测） d = 1 （E的推测）,第三步：用多重循环实现全部的组合,for( a = 1; a = 5; a +) for( b = 1; b = 5; b +) for( c = 1; c = 5; c +) for( d = 1; d = 5; d +) for( e = 1; e = 5; e +) if(满足全部条件) 输出结果； ,关于优化：,五重循环可以改写成四重循环 将条件分散在循环中，也可以优化,练习,题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。,小结,这三种基本算法是最常见的程序设计方法 其它还有回溯、分治等等 更多的是要结合计算机可以进行快速计算的特点来完成。将一些逻辑或者社会问题转换成为计算机模拟的方式来进行。,
