5-1已知A为整数数组,试写出实现下列运算的递归算法 (1)求数组A中的最大整数 (2)求n个整数的和 (3)求n个整数的平均值 【解答】 class RecureArray i ∥数组类声明 int· Elements; ∥数组指针 ∥数组尺寸 ∥当前已有数组元素个数 public Recurve Array( int MaxSize =10) Array Sie( MaxSize ) Elements( new int[MaxSie]) cRecurveArray (i delete Elements: j 输入数组的内容 int n ); 求最大值 int Sum(intn片; 求数组元素之和 noat Average( int n ) ∥求数组元素的平均值 void RecurveArray: Inputarray(){/输入数组的内容 cout<<"Input the number of Array: ln"; for( int i=0; i <Array ie: i++)cin > Elements[j; int RecurveArray : Markey( intn)t ∥递归求最大值 f(n== l)return Elements[OI if( Elementsn-1>temp)return Elements[n-1; int Recurve Array : Sum( int n)i ∥递弟归求数组之和 if(n==1) else return Elements[n-1]+ Sum(r1); float RecurveArray {∥递归求数组的平均值
1 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); } float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float) Elements[0];
else return((float)Elements[n-1]+(n-D)*Average(n-1))/n; int main( int arg, char"argv[)t cout <<"No of the elements cout<<"\nThe max is: "<<ra. Markey( ra Maxsize )<<endI cout<<"nthe avr is: "<<ra. Average( ra MaxSize )< endl 5-2已知 Ackerman函数定义如下: 当m≠0,n=0时 akmm-1,am(m,n-1)当m≠0n≠0时 (1)根据定义,写出它的递归求解算法 (2)利用栈,写出它的非递归求解算法 【解答】(1)已知函数本身是递归定义的,所以可以用递归算法来解决 unsigned akm( unsigned m, unsigned n)i if ( m=0)return n+1; ∥m=0 else if(n==0)return akm(m-1, 1); else return akm( m-1, akm(m, 1)); (2)为了将递归算法改成非递归算法,首先改写原来的递归算法,将递归语句从 结构中独立出来: unsigned akm( unsigned m, unsigned n)i if ( m=0)return n+1; f(n==o)return akm( m-1, 1); ∥m>0.n=0 v=akm(m, 1)); ∥m>0.n>0 return akm(m-1, v); 计算akm(2,1)的递归调用树如图所示:
2 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 ); } 计算 akm(2, 1)的递归调用树如图所示：
akm(1, 3) akm=5 akm(1 akm =3 =akm(1,2) akmn(0,4)=5 y=2 akm(1,0) 用到一个栈记忆每次递归调用时的实参值,每个结点两个域{m,m}。对以上实例,栈 的变化如下: V vn 1n vn 1 1 vN 改akm(m-1,1) 改akm(m-1,1) 改akn(m-1)改abmn(m-1,y) 0 改akm(m-1,1)v=n+1=2改aAm(m-1,)改akm(m-1,)改aAm(m-1,)栈空,返回y=5 v=n+1=3v=n+1=4y=n+1=5 相应算法如下 #include <iostream. h> #define maxie 3500 unsigned akm( unsigned m, unsigned n)i stack<node> st( maxSize ) node w; unsigned v; while( stGetTop(). vm>0) 川计算akn(m-1,antm,m1)) while( st GetTop().I7>0) 川计算akm(m,m1),直到akm(m,0) w=st. GerTop(: st Pop(): 川计算akm(m-1,1) 1; St Push(w);
3 用到一个栈记忆每次递归调用时的实参值，每个结点两个域{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) ) 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(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
∥直到akm(0,akm(1,*)) w= st.GerTopo; st Pop();v=ww++;计算v=akm(1,*)+1 if( st IsEmpty(==0) ∥如果栈不空,改栈顶为(m-1,y) iw=st GetTopO: st Pop(): wvm wn=v: stPush( w):) I while(st. IsEmpro==0); 5-3【背包问题】设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为 v[1]lw(2]…,w[m。问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之 和正好为s。如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真):否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示:此 背包问题的递归定义如下:) 此时背包问题一定有解 False 总重量不能为负数 KNAP(s, n)= s>0且n<1物品件数不能为负数 KNAP(s,n-1)或>0且n≥1所选物品中不包括wn时 KNAP(s-wnl, n-1) 所选物品中包括n时 【解答】根据递归定义,可以写出递归的算法, enu boolean Knap( int s, int n)i if(s<0s>0&&n<1)return False; if( Knap(s-wIn] l)==True {cou≤<Wn]<‘,’; return True; return Knap(s, 1); 若设w={0,1,2,4,8,16,32},s=51,n=6。则递归执行过程如下 eturn True,完成 Kma(51-32,5) return True,打印3 nap(19-16,4 return True,打印16 nap(3-8, 3) return False Knap(3,3) return T return F Knap(3-4, 4) return False Knap(3, 2) return Tr s=-1<0 return False Knape3-2, 1)return True,打印2 Knap(1-1,0) I return True,打印1 return True 5-4【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1行,第2行,…。第8行上布放棋子。在每一行中有8个可选择位置,但在任一时刻,棋 盘的合法布局都必须满足3个限制条件,即任何两个棋子不得放在棋盘上的同一行、或者
4 } //直到 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-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1 行，第 2 行，…。第 8 行上布放棋子。在每一行中有 8 个可选择位置，但在任一时刻，棋 盘的合法布局都必须满足 3 个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者
同一列、或者同一斜线上。试编写一个递归算法,求解并输出此问题的所有合法布局。(提 示:用回溯法。在第n行第j列安放一个棋子时,需要记录在行方向、列方向、正斜线方向 反斜线方向的安放状态,若当前布局合法,可向下一行递归求解,否则可移走这个棋子 恢复安放该棋子前的状态,试探本行的第+1列。) 【解答】此为典型的回溯法问题 次对角线 1#次对角线 2#次对角线 3#次对角线 4#次对角线 5#次对角线 6#次对角线 0#主对角线 #主对角线 2#主对角线 主对角线 4#主对角线 5#主对角线 6#主对角线 在解决8皇后时,采用回溯法。在安放第i行皇后时,需要在列的方向从1到n试 探(j=1,…,n):首先在第j列安放一个皇后,如果在列、主对角线、次对角线方向有其它 皇后,则出现攻击,撤消在第j列安放的皇后。如果没有出现攻击,在第j列安放的皇后 不动,递归安放第计1行皇后 解题时设置4个数组 coln]:coll标识第i列是否安放了皇后 md2n-1]:muk]标识第k条主对角线是否安放了皇后 sd2n-1]:sak]标识第k条次对角线是否安放了皇后 q]:q[记录第i行皇后在第几列 利用行号和列号j计算主对角线编号k的方法是k=n+i-1;计算次对角线编号k的 方法是k=计j。n皇后问题解法如下 void Queen( int i)i for intj=1; j i(co=0&&md叶r1=0&&sd==0){∥第i行第j列没有攻击 col=m+r1=s汁=l;q= ∥在第i行第j列安放皇后 出一个布局 forG=0;j<=n;+)cout≤<q<∵,; cout << endl else Queen(i+1); ∥在第计1行安放皇后 co]=md叶+广1=sd=0;q[=0; ∥撤消第i行第j列的皇后
5 同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提 示：用回溯法。在第 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 = 1; 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; } else Queen ( i+1 ); //在第 i+1 行安放皇后 } col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; //撤消第 i 行第 j 列的皇后 } } 0# 主对角线 1# 主对角线 2# 主对角线 3# 主对角线 4# 主对角线 5# 主对角线 6# 主对角线 6# 次对角线 5# 次对角线 4# 次对角线 3# 次对角线 2# 次对角线 0# 次对角线 1# 次对角线 0 1 2 3 0 1 2 3