《程序设计方法与案例分析 教学课件 ppt 作者 林志英 魏雪英 第4章》由会员分享，可在线阅读，更多相关《程序设计方法与案例分析 教学课件 ppt 作者 林志英 魏雪英 第4章（33页珍藏版）》请在金锄头文库上搜索。
1、第4章 常 用 算 法,4.1 穷 举 算 法 4.2 递 推 算 法 4.3 递 归 算 法 4.4 算 法 实 例,本章主要介绍几个常用算法：穷举算法、递推算法和递归算法。 归纳法首先考察一些特殊的事例，分析它们共同具有的特征，然后做出一般的结论，这种由特殊推导到一般的推理方法，称为归纳推理或者归纳法。,4.1 穷 举 算 法,【例4.1】有一个人有3个小孩，已知3个孩子的年龄之积是36，年龄之和是13，第2个孩子和第3个孩子年龄相同。问3个孩子的年龄分别是多少？ 首先根据第一个条件“3个小孩的年龄之积是36”，可以得出以下8种情况，如表4-1所示。,第二步，将这8种情况的年龄之和计算出来
2、，得出表4-2。再根据第2个条件“3个小孩的年龄之和是13”，可以将范围缩小到两种情况：9岁、2岁、2岁和6岁、6岁、1岁。,再根据第3个条件“第2个孩子和第3个孩子年龄相同”可以得出，3个小孩的年龄分别是9岁、2岁和2岁。,【例4.2】打印由1，2，3这三个数字组成的所有可能的三位数（允许三位数的各位数字取相同的数，如111，222，333），请给出算法。 根据题意可得出，百位上的数字可以有1，2，3三种取值，十位上的数字可以有1，2，3三种取值，个位上的数字可以有1，2，3三种取值， 可以画出穷举图，如图4.2所示。,图4.2 例4.2的穷举图,根据穷举图，用h表示百位数，用t表示十位数，
3、用d表示个位数。知道每一位上的数字，可用公式h*100+t*10+d计算出该数，算法的NS图如图4.3所示。,图4.3 例4.2的算法N-S图,4.2 递 推 算 法,【例4.4】输出Fibonacci数列的前20项。 Fibonacci数列的第1项值为1，第2项值为1，从第三项开始，每一项的值是前两项的和。,1，1，2，3，5，8，13，21，34，55，89， 根据该数列的变化规律，可以得出下列公式： 算法如图4.5所示。,当n=1 当n=2 当n2,通过这个问题可以发现，如果未知项与已知项之间存在着某种关系，可以借助于已知项一项一项地推出未知项，这种方法称为递推。,4.3 递 归 算 法
4、,一个对象部分地由自己组成或按它自己定义的则称为递归。C语言中，在调用一个函数的过程中可以直接或间接地调用该函数本身，称为函数的递归调用。,在程序设计中使用递归的3个条件。 （1）可以把要解的问题转化为一个新的问题，而这个新的问题的解法仍与原来的解法相同，只是所处理的对象有规律地递增或递减。 （2）可以应用这个转化过程使问题得到解决。 （3）必定要有一个明确的结束递归的条件。,【例4.6】用递归的方法求n！。 n！可用以下数学关系表示。,当n=0时 当n0时,当n = 0时，求n！的问题可以转化为求n（n1）！的新问题，而求（n1）！的解法与原来求n！的解法相同，只是运算对象由n变成了n1；而
5、求n（n1）！的问题又可以转化为求n（n1）（n2）！的新问题，每次转化为新问题时，运算对象就递减1，直到运算对象的值递减至0时，阶乘的值为1，递归不应当再进行下去，这就是求n！递归算法的结束条件。,阶乘函数如下： float factorial (int n) float s; if(n = 0) return 1; else s = n * factorial (n-1); return s; ,假设在主函数中要求计算3！。图4.7给出递归调用和返回过程的示意图。,图4.7 递归调用示意图,【例4.7】计算Fibonacci数列的第n项。 程序如下： int fib (int n) int
6、 y; if(n=1) y=1; else if(n=2) y=1; else y=fib(n1)+fib(n2); return(y); 图4.8描述了当n=4时的递归调用过程。,图4.8 Fibonacci数列递归调用示意图,4.4 算 法 实 例,【例4.9】有一数列： 计算这个数列的前20项之和。,这个数列的特点是：第1项的分母为1，分子为2。从第2项开始，第i项的分母是第i1项的分子，第i项的分子是第i1项的分子分母之和。根据这个特点，可以写出相应的递推算法，其NS图如图4.10所示。算法中n表示分子，d表示分母。,图4.10 例4.9的算法NS图,【例4.10】猴子吃桃：有一天，小
7、猴子摘下一堆桃子，当即吃了一半，还觉得不过瘾，又多吃了一个。第二天接着吃了剩下桃子的一半，仍不过瘾，又多吃了一个到第10天早上小猴子再去吃桃子时，发现只剩下一个了。问小猴子那天共摘下了多少个桃子？,这个问题也是一个递推问题，第10天只剩下一个桃子，第9天吃了桃子的一半并还多吃了一个，即第9天的桃子数是4个，第8天的桃子数为10个，依次类推，可以得出第1天的桃子数。,程序如下： #include “stdio.h“ main() int i,n1,n2; n2=1; for(i=1;i=9;i+) n1=(n2+1)*2; n2=n1; ,printf(“The peaches of the f
8、irst day is %d.n“,n1); 运行结果为： The peaches of the first day is 1534.,【例4.11】4个人排队（4个人分别用A，B，C，D来表示），其中A和B两个人不能排在队头，问共有几种排法。 穷举图如图4.11所示。,图4.11 例4.11的穷举图,【例4.12】用递归算法实现：将一个整数n转换为一个字符串。例如输入278，应输出字符串“278”。n可以是任意位数的整数。 在每次输出之前首先调用自己以解决前一位数字，然后去输出后面的数字，递归的结束条件是商数为0， 程序如下：,#include stdio.h void number (int n) if(n 0) /*处理负数*/ putchar (); n = n ; if (n / 10) number (n / 10); putchar(n % 10 +0); ,
