// n个循环队列共享数组v[0..m-1]和保存各循环队列首尾指针的q[n]已经定义为全局变量，数组元素为elemtp类型，本过程将第i个循环队列出队。若出队成功，打印出队列元素，并返回1表示成功；若该循环队列为空，返回0表示出队失败。 {if (<1||>n) {printf(“队列号错误\\n”);exit(0);}
if (q[i].r==q[i].f) {printf(“队空\\n”); return(0);} q[i].f=(q[i].f+1)%L+(i-1)*L;
printf(“出队元素”,q[i].f); return(1); }
（4）讨论，上述算法假定最后一个循环队列的长度也是L，否则要对最后一个循环队列作特殊处理。另外，未讨论一个循环队列满而相邻循环队列不满时，需修改个循环队列首尾指针的情况（即各循环队列长度不等）。
n个循环队列共享数组v[0..m-1]的示意图如下：
0 L-1 2L-1 3L-1 (n-1)L-1 ? 第i个循环队列从下标 (i-1)L 开始，到iL-1为止。设每个循环队列均用牺牲一个单元的办法来判断队满，即为（q[i].r+1）%L+(i-1)*L=q[i].f时，判定为队满。
16. 设整数序列a1,a2,?,an，给出求解最大值的递归程序。【南京航空航天大学 2000 六】 16、int MaxValue (int a[],int n)
//设整数序列存于数组a中，共有n个，本算法求解其最大值。 {if (n==1) max=a[1];
else if a[n]>MaxValue(a,n-1) max=a[n]; else max=MaxValue(a,n-1); return(max); }
17．线性表中元素存放在向量A（1,?,n）中，元素是整型数。试写出递归算法求出A中的最大和最小元素。【北京邮电大学 1994 八 （10分）】
17、本题与上题类似，只是这里是同时求n个数中的最大值和最小值的递归算法。
int MinMaxValue(int A[],int n,int *max,int *min)
//一维数组A中存放有n个整型数，本算法递归的求出其中的最小数。 {if (n>0)
{if(*maxA[n]) *min=A[n]; MinMaxValue(A,n-1,max,min); }//算法结束
[算法讨论]调用本算法的格式是MinMaxValue(arr,n,&max,&min);其中，arr是具有n个整数的一维数组，max=-32768是最大数的初值,min=32767是最小数的初值。
18. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。
（1）将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。 （2）写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五（15分）】
18、[题目分析] 求两个正整数m和n的最大公因子，本题叙述的运算方法叫辗转相除法，也称欧几里德定理。其函数定义为：
gcd(m,n)=
int gcd (int m,n)
//求正整数m和n的最大公因子的递归算法
{if(m 使用栈，消除递归的非递归算法如下： int gcd(int m,n) {int s[max][2]; //s是栈，容量max足够大 top=1; s[top][0]=m; s[top][1]=n; while (s[top][1]!=0) if (s[top][0] {t=s[top][0]; s[top][0]=s[top][1]; s[top][1]=t;} else{t=s[top][0]%s[top][1]; top++; s[top][0]=s[top-1][1]; s[top][1]=t; } return(s[top][0]); }//算法结束 由于是尾递归，可以不使用栈，其非递归算法如下 int gcd (int m,n) //求正整数m和n的最大公因子 {if (m 19. 写出和下列递归过程等价的非递归过程。 PROCEDURE test(VAR sum:integer); VAR a:integer, BEGIN read(a); IF a=0 THEN sum:=1 ELSE BEGIN test(sum); sum:=sum*a；END; write(sum)； END; 【清华大学 1996 二】 19、[题目分析]这是以读入数据的顺序为相反顺序进行累乘问题，可将读入数据放入栈中，到输入结束，将栈中数据退出进行累乘。累乘的初值为1。 PROC test; CONST maxsize=32; VAR s:ARRAY[1..maxsize] OF integer, top,sum,a:integer; [top:=0; sum:=1;// read(a); WHILE a<>0 DO [top:=top+1; s[top]:=a; read(a); ] write(sum:5); WHILE top>0 DO [sum:=sum*s[top]; top:=top-1; write(sum:5);] ENDP; 20. 试将下列递归过程改写为非递归过程。 void test(int &sum) { int x； scanf(x)； if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)； } 【北京轻工业学院 2000 三 （15分）】 20、[题目分析] 本题与第19题基本相同，不同之处就是求和，另外用C描述。 int test; {int x,sum=0,top=0,s[]; scanf(“%d”,&x) while (x<>0) {s[++top]:=a; scanf(“%d”,&x); } printf(sum:5); while (top) {sum+=s[top--]; printf(sum:5); } }; 21. 已知Ackermann函数定义如下: （1） 写出Ack(2,1)的计算过程。 （2） 写出计算Ack(m,n)的非递归算法。 【北京航空航天大学 1999 六 （15分）】 21、int Ack(int m,n) {if (m==0) return(n+1); else if(m!=0&&n==0) return(Ack(m-1,1)); else return(Ack(m-1,Ack(m,m-1)); }//算法结束 （1）Ack(2,1)的计算过程 Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得 =Ack(1,Ack(1,1)) //因m<>0,n=0而得 =Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得 =Ack(1,Ack(0,2)) // 因m=0而得 =Ack(1,3) // 因m=0而得 =Ack(0,Ack(1,2)) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得 = Ack(0,Ack(0,Ack(0,2))) //因m=0而得 = Ack(0,Ack(0,3)) //因m=0而得 = Ack(0,4) //因n=0而得 =5 //因n=0而得 （2）int Ackerman( int m, int n) {int akm[M][N];int i,j; for(j=0;j {akm[i][0]=akm[i-1][1]; for(j=1;j akm[i][j]=akm[i-1][akm[i][j-1]]; } return(akm[m][n]); }//算法结束 22．设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 【合肥工业大学 2000 五、5（8分）】 22、[题目分析]从集合（1..n）中选出k(本题中k=2)个元素，为了避免重复和漏选，可分别求出包括1和不包括1的所有组合。即包括1时，求出集合（2..n）中取出k-1个元素的所有组合；不包括1 时，求出集合（2..n）中取出k个元素的所有组合。，将这两种情况合到一起，就是题目的解。 int A[],n; //设集合已存于数组A中。 void comb(int P[],int i,int k) //从集合（1..n）中选取k（k<=n）个元素的所有组合 {if (k==0) printf(P); else if(k<=n) {P[i]=A[i]; comb(P,i+1,k-1); comb(P,i+1,k); } }//算法结束