第5章递归与广义表 第5章递归与广义表 5-1已知An]为整数数组,试写出实现下列运算的递归算法 (1)求数组A中的最大整数。 (2)求n个整数的和。 (3)求n个整数的平均值。 【解答】 #include <iostream h class recurvearra ∥数组类声明 private: nt Elements ∥数组指针 ∥数组尺寸 nt Currents ∥当前已有数组元素个数 public: RecurveArray( int Maxsize =10) Array Size( MaxSize ) Elements( new int[MaxSize] RecurveArray (i delete Elements;) yoid InputArrayo 输入数组的内容 int MaxKey( int n ) ∥求最大值 ∥求数组元素之和 ∥求数组元素的平均值 void Recurvearray:: nputArray(){输入数组的内容 cout<<"Input the number of Array: n for int i=0; i ArraySize; i++)cin > Elements[: int recurvearray:; MarKey(intn){∥递归求最大值 if(n==1)return Elements[O: if( Elements n-1> temp )return Elements[n-1; else return temp; int RecurveArray Sum( int n )i ∥递归求数组之和 if(n== D)return Elements[0; else return Elements[n-1]+ Sum(n-1);
第 5 章 递归与广义表 53 第 5 章 递归与广义表 5-1 已知 A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组 A 中的最大整数。 (2) 求 n 个整数的和。 (3) 求 n 个整数的平均值。 【解答】 #include <iostream.h> class RecurveArray { //数组类声明 private: int *Elements; //数组指针 int ArraySize; //数组尺寸 int CurrentSize; //当前已有数组元素个数 public : RecurveArray ( int MaxSize =10 ) : ArraySize ( MaxSize ), Elements ( new int[MaxSize] ){ } ~RecurveArray ( ) { delete [ ] Elements; } void InputArray(); //输入数组的内容 int MaxKey ( int n ); //求最大值 int Sum ( int n ); //求数组元素之和 float Average ( int n ); //求数组元素的平均值 }; void RecurveArray :: InputArray ( ){ //输入数组的内容 cout << "Input the number of Array: \n"; for ( int i = 0; i < ArraySize; i++ ) cin >> Elements[i]; } int RecurveArray :: MaxKey ( int n ) { //递归求最大值 if ( n == 1 ) return Elements[0]; int temp = MaxKey ( n - 1 ); if ( Elements[n-1] > temp ) return Elements[n-1]; else return temp; } int RecurveArray :: Sum ( int n ) { //递归求数组之和 if ( n == 1) return Elements[0]; else return Elements[n-1] + Sum (n-1); }
第5章递归与广义表 float RecurveArray∷ Average(intn){∥递归求数组的平均值 else return((float)Elements[n-1]+(n-1)* Average(n-1))/n int main( int arge, char argv [)i InputArrayo <<"nThe max is: "< ra MaxKey( ra MaxSize )< endl cout<<"nthe avr is: "<< ra. Average( ra MaxSize )<<endl; 5-2已知 Ackerman函数定义如下 当m=0时 akm(m,n)=akm(m-1,1) 当m≠0,n=0时 akmm-1,am(m,n-1)当m≠0n≠0时 (1)根据定义,写出它的递归求解算法 (2)利用栈,写出它的非递归求解算法 【解答】 (1)已知函数本身是递归定义的,所以可以用递归算法来解决 unsigned akm( unsigned m, unsigned n)i f(m==0) return n+l: else if(n==0)return akm( m-1, 1); ∥m>0,n=0 else return akm( m-l, akm( m, n-1)); ∥m>0.n>0 (2)为了将递归算法改成非递归算法,首先改写原来的递归算法,将递归语句从 结构中独立出来 unsigned akm( unsigned m, unsigned n )i f(m==0) return n+l: if (n==o)return akm( m-1, 1); ∥m>0,n==0 v= akm(m, n-1)); ∥m>0,n>0 return akm( m-l, v)
第 5 章 递归与广义表 54 float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float) Elements[0]; else return ( (float) Elements[n-1] + ( n - 1) * Average ( n - 1 ) ) / n; } int main ( int argc, char* argv [ ] ) { int size = -1; cout << "No. of the Elements : "; while ( size < 1 ) cin >> size; RecurveArray ra ( size ); ra.InputArray(); cout<< "\nThe max is: " << ra.MaxKey ( ra.MaxSize ) << endl; cout<< "\nThe sum is: " << ra.Sum ( ra.MaxSize ) << endl; cout<< "\nthe avr is: " << ra.Average ( ra.MaxSize ) << endl; return 0; } 5-2 已知 Ackerman 函数定义如下： akm m n n m akm m m n akm m akm m n m n ( , ) ( , ) , ( , ( , )) , = + = − = − − 1 0 1 1 0 0 1 1 0 0 当 时 当 时 当 时 (1) 根据定义，写出它的递归求解算法； (2) 利用栈，写出它的非递归求解算法。 【解答】 (1) 已知函数本身是递归定义的，所以可以用递归算法来解决： unsigned akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1; // m == 0 else if ( n == 0 ) return akm ( m-1, 1 ); // m > 0, n == 0 else return akm ( m-1, akm ( m, n-1 ) ); // m > 0, n > 0 } (2) 为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从 结构中独立出来： unsigned akm ( unsigned m, unsigned n ) { unsigned v; if ( m == 0 ) return n+1; // m == 0 if ( n == 0 ) return akm ( m-1, 1 ); // m > 0, n ==0 v = akm ( m, n-1 ) ); // m > 0, n > 0 return akm ( m-1, v );
第5章递归与广义表 计算akm(2,1)的递归调用树如图所示: =akm(2,0) a(3)am=5 akm(1 akm =3 =akm(1,2)|akm(0,4)=5 y=2 v=am(1,0)|am0,2)=3 用到一个栈记忆每次递归调用时的实参值,每个结点两个域{vm,Ⅶm。对以上实例,栈 的变化如下: V vn 1n vn 1 1 vn 改akm(m-1,1) 改akm(m-1,1)y=n+1=2改akmm-1,y)改akm(m-1,) 翻誧蚩 改akm(m-1,1)y=n+1=2改akmn(m-1,1)改akmm-1,y)改akm(m-1,)栈空,返回v=5 =n+1=3v=n+1=4v=n+1=5 相应算法如下 #include <iostream. h> include“ stack h #define max Size 3500; ed tack<node>st( maxSize ) node wvm=m; wvn=n; st Push(w); while( st GetTop().vm >0)t 川计算akm(m-1,akm(m,n-1))
第 5 章 递归与广义表 55 } 计算 akm(2, 1)的递归调用树如图所示： 用到一个栈记忆每次递归调用时的实参值，每个结点两个域{vm, vn}。对以上实例，栈 的变化如下： 相应算法如下 #include <iostream.h> #include “stack.h” #define maxSize 3500; unsigned akm ( unsigned m, unsigned n ) { struct node { unsigned vm, vn; } stack<node> st ( maxSize ); node w; unsigned v; w.vm = m; w.vn = n; st.Push (w); do { while ( st.GetTop( ).vm > 0 ) { //计算 akm(m-1, akm(m, n-1) ) akm(2, 1) v =akm(2, 0) akm(1, 1) v =akm(1, 0) akm(0, 1) = 2 akm(0, 2) = 3 akm(1, 3) v = akm(1, 2) v = akm(1, 1) v = akm(1, 0) akm(0, 1) = 2 akm(0, 2) = 3 akm(0, 3) = 4 akm(0, 4) = 5 v = 2 v = 2 v = 3 v = 4 v = 3 akm = 5 akm = 5 akm = 3 2 1 2 1 2 1 2 1 2 1 1 3 2 0 1 1 1 1 1 1 0 2 1 0 0 1 改 akm(m-1,1) 改 akm(m-1,1) v = n+1= 2 改 akm(m-1,v) 改 akm(m-1,v) v = n+1 = 3 vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn 1 3 1 3 1 3 1 3 0 4 1 2 1 2 1 2 0 3 1 1 1 1 0 2 1 0 0 1 改 akm(m-1,1) v = n+1 = 2 改 akm(m-1,v) 改 akm(m-1,v) 改 akm(m-1,v) 栈空, 返回 v = 5 v = n+1 = 3 v = n+1 = 4 v = n+1 = 5
第5章递归与广义表 川计算akm(m,n-1),直到akm(m,O) wvn--; st Push(w片;} 川计算akm(m-1,1) wvm;w vn=1; st Push(w); ∥直到akm(O,akm(1,*)) +;川计算v=akm( 如果栈不空,改栈项为(m-1,v) iw=st GetTop(: st Pop(: wvm wvn=v: st Push(w):) 5-3【背包问题】设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为 w[1],w2]…,wn。问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之 和正好为s。如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真):否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示:此 背包问题的递归定义如下:) Tes=0此时背包问题一定有解 False 总重量不能为负数 KNAP(s, n)= s>0且n<1物品件数不能为负数 KNAP(s,n-1)或>0且n≥1所选物品中不包括wn时 KNAP(s-wnl, n-1) 所选物品中包括{r时 【解答】根据递归定义,可以写出递归的算法。 enu boolean Knap( int s, int n )i if(s<0 s>0&&n<l)return False; if( Knap(s-winl, n-1)==True {cout≤<w[n< eturn True; 1 n Knap( s, n-1); 若设w={0,1,2,4,8,16,32},s=51,n=6。则递归执行过程如下 return True,完成 return True,打印16 p(3-8, 3) return False Knap(3, 3) return T return F Knap(3-4, 4) return False Knap(3, 2 return Tr return False Knap(3-2,1) return True,打印2 Knap(1-1,0) I return True,打印1 return True
第 5 章 递归与广义表 56 while ( st.GetTop( ).vn > 0 ) //计算 akm(m, n-1), 直到 akm(m, 0) { w.vn--; st.Push( w ); } w = st.GetTop( ); st.Pop( ); //计算 akm(m-1, 1) w.vm--; w.vn = 1; st.Push( w ); } //直到 akm( 0, akm( 1, * ) ) w = st.GetTop(); st.Pop( ); v = w.vn++; //计算 v = akm( 1, * )+1 if ( st.IsEmpty( ) == 0 ) //如果栈不空, 改栈顶为( m-1, v ) { w = st.GetTop(); st.Pop( ); w.vm--; w.vn = v; st.Push( w ); } } while ( st.IsEmpty( ) == 0 ); return v; } 5-3 【背包问题】设有一个背包可以放入的物品的重量为 s，现有 n 件物品，重量分别为 w[1], w[2], …, w[n]。问能否从这 n 件物品中选择若干件放入此背包中，使得放入的重量之 和正好为 s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此 背包问题的递归定义如下：） − − − = = ( [ ], 1) [ ] ( , 1) 0 1 [ ] False 0 1 False 0 True 0 ( , ) 所选物品中包括 时 或 且 所选物品中不包括 时 且 物品件数不能为负数 总重量不能为负数 此时背包问题一定有解 KNAP s w n n w n KNAP s n s n w n s n s s KNAP s n 【解答】根据递归定义，可以写出递归的算法。 enum boolean { False, True } boolean Knap( int s, int n ) { if ( s == 0 ) return True; if ( s < 0 || s > 0 && n < 1 ) return False; if ( Knap ( s – W[n], n-1 ) == True ) { cout << W[n] << ‘ , ’; return True; } return Knap( s, n-1 ); } 若设 w = { 0, 1, 2, 4, 8, 16, 32 }，s = 51, n = 6。则递归执行过程如下 递 归 Knap(51, 6) return True, 完成 Knap(51-32, 5) return True, 打印 32 Knap(19-16, 4) return True, 打印 16 Knap(3-8, 3) return False Knap(3, 3) return True, 无动作 s = -5 < 0 return False Knap(3-4, 4) return False Knap(3, 2) return True, 无动作 s = -1 < 0 return False Knap(3-2, 1) return True, 打印 2 Knap(1-1, 0) return True, 打印 1 s = 0 return True
第5章递归与广义表 5-4【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1行,第2行,…。第8行上布放棋子。在每一行中有8个可选择位置,但在任一时刻,棋 盘的合法布局都必须满足3个限制条件,即任何两个棋子不得放在棋盘上的同一行、或者 同一列、或者同一斜线上。试编写一个递归算法,求解并输出此问题的所有合法布局。(提 示:用回溯法。在第n行第j列安放一个棋子时,需要记录在行方向、列方向、正斜线方向 反斜线方向的安放状态,若当前布局合法,可向下一行递归求解,否则可移走这个棋子 恢复安放该棋子前的状态,试探本行的第j+1列。) 【解答】此为典型的回溯法问题 0#次对角线 1#次对角线 2#次对角线 3#次对角线 4#次对角线 5#次对角线 人厦 6#次对角线 0#主对角线 1#主对角线 2#主对角线 主对角线 4#主对角线 5#主对角线 6#主对角线 在解决8皇后时,采用回溯法。在安放第i行皇后时,需要在列的方向从1到n试 探(j=1,…,n):首先在第j列安放一个皇后,如果在列、主对角线、次对角线方向有其它 皇后,则出现攻击,撤消在第j列安放的皇后。如果没有出现攻击,在第j列安放的皇后 不动,递归安放第i+1行皇后 解题时设置4个数组 col[n]:col[标识第i列是否安放了皇后 md口2n-1]:mdk]标识第k条主对角线是否安放了皇后 sd[2n-1]:sdk]标识第k条次对角线是否安放了皇后 qn]:q[记录第i行皇后在第几列 利用行号i和列号j计算主对角线编号k的方法是k=n+i-j-1:计算次对角线编号k的 方法是k=计+j。n皇后问题解法如下: void Queen( int i)( for intj=0; j<n; j++)i i(col=0&&md[nijl=0&&sd=0){∥第i行第j列没有攻击 col0]=md[n+ij-1=sd[i+J=1; q0=j; ∥在第i行第j列安放皇后 出一个布局 for(j=0;j<n;j++)cout <<q0]<<', i
第 5 章 递归与广义表 57 5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1 行，第 2 行，…。第 8 行上布放棋子。在每一行中有 8 个可选择位置，但在任一时刻，棋 盘的合法布局都必须满足 3 个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者 同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提 示：用回溯法。在第 n 行第 j 列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、 反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子， 恢复安放该棋子前的状态，试探本行的第 j+1 列。) 【解答】此为典型的回溯法问题。 在解决 8 皇后时，采用回溯法。在安放第 i 行皇后时，需要在列的方向从 1 到 n 试 探( j = 1, …, n )：首先在第 j 列安放一个皇后，如果在列、主对角线、次对角线方向有其它 皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后 不动，递归安放第 i+1 行皇后。 解题时设置 4 个数组： col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] ：md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] ：sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] ：q[i] 记录第 i 行皇后在第几列 利用行号 i 和列号 j 计算主对角线编号 k 的方法是 k = n+i-j-1；计算次对角线编号 k 的 方法是 k = i+j。n 皇后问题解法如下： void Queen( int i ) { for ( int j = 0; j < n; j++ ) { if ( col[j] == 0 && md[n+i-j-1] == 0 && sd[i+j] == 0 ) { //第 i 行第 j 列没有攻击 col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; //在第 i 行第 j 列安放皇后 if ( i == n ) { //输出一个布局 for ( j = 0; j < n; j++ ) cout << q[j] << ‘,’; cout << endl; } 0# 主对角线 1# 主对角线 2# 主对角线 3# 主对角线 4# 主对角线 5# 主对角线 6# 主对角线 6# 次对角线 5# 次对角线 4# 次对角线 3# 次对角线 2# 次对角线 0# 次对角线 1# 次对角线 0 1 2 3 0 1 2 3