计算机程序设计(递归).ppt

void hanoi(int n, int a, int b, int c) { if (n 1) { hanoi(n-1, a, c, b); move(n,a,b); hanoi(n-1, b, a, c); } else move(n,a,b); //结束条件 } 3.递归算法设计 棋子移动 问题描述：有2n个棋子排成一行，白子用0代表，黑子用1代表。n=5的状态为： 0000011111_ _ (右边至少两个空位) 移动规则： (1)每次必须移动相邻的两个棋子，这两个棋子不能互换位置 (2)移动的颜色不限，移动的方向不限 要求： 最后成为 _ _ 0101010101 的状态(中间无空格)。 3.递归算法设计 空格在任何地方都是可等价变换的 问题规模为n和为n-1有相似的地方吗？ 000……000111……111_ _ (问题的规模n) 000……0011……111_ _01 (问题的规模 n-1,?) 结论： (1)规模为n的问题可以通过两步的移动变成规模为n-1的问题! (2)初值（递归的结束条件n=?可以解） 3.递归算法设计 1.初值的判断： n=2, 0011_ _ → 0_ _ 101 →010_ _ 1 , 无解 n=3, 无解 n=4: 0 0 0 0 1 1 1 1 _ _ 0 0 0 _ _ 1 1 1 0 1 0 0 0 1 0 1 1 _ _ 1 0 _ _ 1 0 1 1 0 0 1 0 1 0 1 0 1 _ _ 0 1 _ _ 0 1 0 1 0 1 0 1 3.递归算法设计 2.递推关系式: 0 0 0 . . . 0 0 0 1 1 1 . . . 1 1 1 _ _ (n) 0 0 0 . . . 0 0 _ _ 1 1 . . . 1 1 1 0 1 0 0 0 . . . 0 0 1 1 1 1 . . . 1 _ _ 0 1 (n-1) 对n-1个棋子进行递归的移动直到n=4为止 3.递归算法设计 3.算法实现： (对棋子的位置进行编号，从1,2,2n,2n+1,2n+2) void chess(int n){ //n为移动的棋子数，n≥4 if( n == 4 ){ //递归出口 …… } else if( n4 ){ //进入递归 move_to(n,n+1, 2n+1,2n+2); move_to(2n-1,2n,n,n+1); chess(n-1); } } 3.递归算法设计 4.思考： 如果棋子的移动规则改为每次移动相邻的3个(4,5,…)棋子，其他条件不变，则如何解决此问题？ 递归关系式的推导 初值的判断(n=?有解) 算法的实现 3.递归算法设计 n个元素的全排列 N=1, 输出 1 N=2, 输出 1,2 2,1 N=3, 输出 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 解决： 递推关系式 初始值(递归的出口) 算法实现 3.递归算法设计 a[ ] = {1,2.3,4,…,n}; //对a[k] – a[n] 进行全排列 void Range(a,k,n){ if( k == n ) Print(a); //输出排列 else{ for(i=k;in;i++) { a[k] ? a[i]; //交换值 Range(a,k+1,n); //递归排列剩下的元素 a[i] ? a[k]; //交换值 } } } 初始调用： Range(a,0,n); 3.递归算法设计 4.递归关系式的计算 递归算法时间复杂度的分析(重点) 递归算法时间复杂度的计算(难点) 4.递归关系式计算 4.1递归算法时间复杂度分析 根据递归算法思想，可以得到递归算法的时间复杂度的递推关系式 求解递推关系式即可 例：GCD 4.递归关系式计算 T(a,b) = T(b,a%b) + C0, 其中C0为常数 最坏情况：T(a) = T(a/2) + C0 = O(logn) 例：一个楼有n个台阶，有一个人上楼有时一次跨一个台阶，有时跨2个台阶。问此人共有几种不同