c语言程序设计8第八讲(第四章中)-1.ppt

树立个目标，越早越好！ 高级语言程序设计 主讲教师：贾彩燕 计算机与信息技术学院 计算机科学与技术系 cyjia@bjtu.edu.cn 第四章基本程序设计技术 主要内容：基本程序设计技术 循环程序设计 循环与递归 基本输入输出 控制结构和控制语句 程序设计实例 程序测试和排错 4.2 循环与递归 计算整数阶乘的递推函数 函数的嵌套与递归调用 嵌套调用 C规定：函数定义不可嵌套，但可以嵌套调用函数 构成递归需具备的条件 子问题须与原始问题为同样的事，且更为简单； 不能无限制地调用本身，必须有个出口，化简为非递归状况处理。 例1 阅读源程序,写出运行结果。 例2 下列程序执行时,键盘输入3,则程序的输出结果是? void fib1(int n) { long f1, f2, f; int i; f2 = f1 = 1; printf(%ld %ld , f1, f2); for(i = 3; i = n; i++) { f = f1 + f2; f1 = f2; f2 = f; printf(%ld , f); if( i % 5 == 0 ) printf( \n ); } } Fibonacci数列的递归及非递归算法 Fibonacci数列的递归及非递归算法运行时间对比 思考题1 有一头母牛，在她四岁时生下一头小牛，也是母的，自此以后，她每年都生一头母牛，假设牛不会死亡，小牛生育和老牛一样，问老牛五十岁时，她有多少个后代?？ 试试用递归和递推分别解决 思考题2 对比求最大公约数辗转相除法递归方法和递推方法的差异 写程序统计两种方法的执行时间 递推调用 一般情况下,大多数递归问题都可以转化为递推求解,递归调用使用选择结构,而递推调用使用循环结构. 递归与递推 递归调用是通过不断简化原始问题,最终达到基本实例时终止。 递推调用是通过不断修改循环变量的值,达到循环条件为假时结束循环。 使用递归的目的是简化程序,便于阅读,但会占用CPU大量的时间和过多的内存。而非递归具有效率高,但编程难度较大,可读性较差的特点。 当递归函数清晰的优点可以补偿它的效率开销时，就可以使用这个工具 汉诺塔(Tower of Hanoi)问题的解题思路： 递归算法： 　如果 n = 1，则将这一个盘子直接从 a 柱移到 b柱上。否则，执行以下三步： 用 b 柱做过渡，将 a 柱上的 (n-1) 个盘子移到 c 柱上； 将 a 柱上最后一个盘子直接移到 b 柱上； 用 a 柱做过渡，将 c 柱上的 (n-1) 个盘子移到 b 柱上。 思考题3 为henoi塔程序不同数目的盘子记时 算法运行时间随着盘子数的增多指数级增长 作业 P129页 14题 补充题：用递归的方法求N阶勒让德多项式的值，递归公式为： 思考题选做 解法2：求GCD有著名的欧几里德算法（欧氏算法，辗转相除法）。最大公约数的递归定义： 函数定义（递归）：求最大公约数 假设第二个参数非0，且参数都不小于0。 long gcd1 (long m, long n) { return m % n == 0 ? n : gcd1(n, m % n); } 求最大公约数的完整程序： #includestdio.h int main() { int m, n, d; m = 12; n = 8; d = gcd(m, n); return 1; } long gcd(long m, long n) { if(m 0)m=-m; if(n 0)n=-n; return n == 0 ? m : gcd1(m, n); } long gcd1(long m, long n) { return m % n == 0 ? n : gcd1(n, m % n); } 函数定义（循环）：求最大公约数 辗转相除就是反复求余数，可用循环结构实现。 循环可写为： for (r = m % n; r != 0; r = m % n) { m = n; n = r; } 出发点m和n； 循环判断m%n是否为0，若是则n为结果； 否则更新变量：令m取n的原值，n取m%n的原值。 为正确更新需用辅助变量r，正确的更新序列： r = m % n; m = n; n = r; 循环语句实现求最大公约数 long gcd2 (long m, long n) { long r; if (n == 0) return m; for (r = m % n; r != 0; r = m % n) { m