第二章递归的算法.pptVIP

3.递归算法设计 可用递归解决的问题P 问题P具有规模 不同规模的问题P，具有相同性质；并且大规模的问题由小规模的问题构成 小规模的问题是可解的 关键： 找到递归的递推关系 找到结束递归的条件 3.递归算法设计 递归求解的伪代码 procedure P(参数表) begin if 满足递归出口 then 简单操作 else begin 简单操作; CALL P; 简单操作; end; end endp 3.递归算法设计 简单的0/1背包问题 设一个背包容纳的物品最大质量为m,现有n件物品，质量为m1,m2,… ,mn,均为正整数。要求从中挑选若干件，使背包质量之和正好为m. （在此问题中，第i件物品要么取，要么不取，不能取一部分，故问题可能有解，可能无解） 设用knap(m,n)来表示此问题。有解为true,否则为false 3.递归算法设计 先考虑将物品mn放入背包的情况： knap(m,n) = 若mn = m , 则knap(m,n) ← true 若mn m,则knap(m,n) ← knap(m,n-1) 否则mn m， 则 knap(m,n) ← knap(m,n-1) ＋knap(m-mn,n-1) 3.递归算法设计 bool knap(m,n) { if( n == 1 ) { //出口条件 if( m[1] == m ) return true; else return false; } if( m[n] == m ) return true; if( m[n] m ) return knap(m,n-1); if( knap( m-m[n],n-1 )) return true; return knap(m,n-1); } 3.递归算法设计 Hanoi塔问题 汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。游戏的装置如图所示（图上以3个金片例），底座上有三根金的针，第一根针上放着从大到小64个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能移动一个金片，并且大的金片不能压在小的金片上面。该游戏的结束就标志着“世界末日”的到来。 3.递归算法设计 A B C 三个金片的Hanoi游戏的装置 分析： ◆游戏中金片移动是一个很繁琐的过程。通过计算，对于64个金片至少需要移动 264 – 1 = 1.6×1019 次 。 ■不妨用A表示被移动金片所在的针（源），C表示目的针，B表示过渡针。对于把n（n1）个金片从第一根针A上移到第三根针C的问题可以分解成如下步骤： （1）将n-1个金片从A经过C移动到B。 （2）将第n个金片移动到C。 （3）再将n-1个金片从B经过A移动到C。 这样就把移动n个金片的问题转化为移动n-1个金片的问题，即移动n个金片的问题可用移动n-1个金片的问题递归描述，以此类推，可转化为移动一个金片的问题。显然，一个金片就可以直接移动。 3.递归算法设计 A B C 三个金片的Hanoi游戏的装置 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