递归程序设计.pptVIP

特殊情况处理 一些特殊情况需要处理 1）m和n都为0需特殊处理。令函数返回值0； 2）若m和n中一个为0，gcd是另一个数。函数的返回值正确。也可直接判断处理； 3）m、n为负时函数返回1，可能不对。 应在循环前加语句 if (m == 0 n == 0) return 0; if (m == 0) return n; if (n == 0) return m; if (m 0) m = -m; if (n 0) n = -n; 可能方式2 换个思路 令k从某个恰当的大数开始递减，找到的第一个公约数就是最大公约数。 k初值可取m和n中小的一个。 结束条件 k值达到1或找到了公约数。1总是公约数。 程序主要部分可写为： for (k = (m n ? n : m); //把k设为n的较小者 m % k != 0 || n % k != 0; k--) ; /* 空循环体 */ return k; /*循环结束时k是最大公约数 */ 过程示例 m n k m % k != 0 || n % k != 0 d 20 8 8 是 ？ 7 是 ？ 6 是 ？ 5 是 ？ 4 否 4 两种方式比较 本方法比前一方法简单一些。 两种方法的共同点是重复测试。 这类方法的缺点是效率较低，参数大时循环次数很多。 解法2 辗转相除法 求GCD有著名的欧几里德算法（欧氏算法，辗转相除法）。最大公约数的递归定义： 例 例1 gcd1(70, 30) m = 70, n = 30 m % n ? 10 gcd(30, 10) m = 30, n = 10 m % n ? 0 例2 gcd1(65, 15) m = 65, n = 15 m % n ? 5 gcd1(15, 5) m = 15, n = 5 m % n ? 0 递归程序解决 函数定义与数学定义直接对应 long gcd (long m, long n) { return m % n == 0 ? n : gcd(n, m % n); } 假设第二个参数非0，且参数都不小于0。 对欧氏算法的研究保证了本函数能结束，对较大的数计算速度也很快，远远优于顺序检查。 加入特殊情况处理 long gcd(long m, long n) { if (m 0) m = -m; if (n 0) n = -n; return n == 0 ? m : gcd(m, n); } 循环方法 辗转相除就是反复求余数，也是重复性工作，可可用循环结构实现。 出发点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 = n; n = r; } return n; } 参数是局部变量，可在函数体里使用和修改。 河内塔（梵塔问题） 河内塔（ hanoi塔，梵塔）问题 问题出自古印度（一说西藏） 某神庙有三根细柱，64个大小不等、中心有孔的金盘套在柱上，构成梵塔。 僧侣日夜不息地将圆盘从一柱移到另一柱。 规则 每次只移一个盘，大盘不能放到小盘上。 开始时圆盘从大到小套在一根柱上，据说所有圆盘都搬到另一根柱时世界就要毁灭。 图示 要求 要求写程序模拟搬圆盘过程，打印出搬动指令序列。 为方便，分别将三根圆柱命名为a、b和c，假定开始时所有圆盘都在a上，要求最终搬到b。 问题分析 初看问题似乎没规律。求解的关键在于看到问题的“递归性质”。 搬64个盘的问题可归结为两次搬63个盘。 搬n个圆盘的问题可以归结为搬n-1个圆盘，把n个盘从柱A搬到柱B的工作可以如下完成 从柱A借助柱B将n-1个圆盘搬到柱C； 将最大圆盘从柱A搬到柱B； 从柱3借助柱A将n-1个圆盘搬到柱B； 从柱A借助柱B将3个圆盘搬到柱C A B C A B C A B C A C B 从柱A将最大的圆盘移动B柱 从柱C借助柱A将3个圆盘搬到柱B void moveone (char from, char to) { printf(%c - %c\n, from, to); } ? void henoi(int n,char from,char to,char by)