发布时间 : 星期三 文章数据结构练习 - 第三章 - 栈和队列更新完毕开始阅读
}∥算法结束
使用栈，消除递归的非递归算法如下： 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 10. 设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 【合肥工业大学 2000 五.5（8分）】 [题目分析]从集合（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); } }∥算法结束 11. 对于任意的无符号的十进制整数m,写出将其转换为十六进制整数的算法（转换仅要求能够输出正确的十六进制的整数即可。）【兰州大学2000九(10分)】 [题目分析]十进制整数m转换为十六进制整数，进行如下操作：将m被16除，余数是一位十六进制数，将m被16除的商做新的m,继续以上运算，直至商等于0为止。应注意整数10至15，在十六进制中是A至F。 void convert(unsigned int m) ∥本算法将无符号十进制整数m转换为十六进制整数 {while(m/16) {n=m; 21 switch(n) {case 0:case 1: case 2:case 3: case 4:case 5: case 6:case 7: case 8:case 9: printf(“%c”,n+48); break; case 10: case 11: case 12:case 13: case 14:case 15: printf(“%c”,n+55); }; m=m/16; }; printf(“\\n”); } 本算法的递归描述如下： void convert(unsigned int m) ∥本算法将无符号十进制整数m转换为十六进制整数 {if(m) {n=m; switch(n) {case 0:case 1: case 2:case 3: case 4:case 5: case 6:case 7: case 8:case 9: printf(“%c”,n+48); break; case 10: case 11: case 12:case 13: case 14:case 15: printf(“%c”,n+55); } convert(m/16); }//if }//end 12. 已知递归函数F(m)（其中DIV为整除）； (1) 写出求F(m)递归算法； (2) 写出求F(m)的非递归算法。【北京师范大学2003五.3(15分)】 递归算法如下： void recurse(int m, int &s) {if(m<0) return ERROR; if(m==0) s=1; else {f_recurse(m/2,r); s=m*r; } } 非递归算法如下： void nonrecure(int m,int &s) {if(m<0) return ERROR; if(m==0) s=1; else{StackInit(sa); while(m!=0){a=m;b=m/2; push(sa,{a,b}); m=b; } s=1; while(!StackEmpty(sa)){pop(sa,t); s=s*t.a; } }//else }//结束 13. 已知有n个元素存放在向量S[1..n]中，其值各不相同，请写一递归算法，生成并输出n个元素的全排列。【中国科学技术大学1992十三(20分)】 【苏州大学2005五(15分)】 [题目分析]n个元素的全排列有n!种。因n!=n*(n-1)! ，而 22 (n-1)!=(n-1)*(n-2)!，故对n个元素，可放到n 个不同位置上，让第一个位置依次取每一个元素，共n种取法，对其后的n-1个位置上的n-1个元素共有(n-1)!种不同排列，??，以此类推，直至第n个位置，将最后一个元素放在此位置上。 利用数组S[n]保存1—n之间的n个自然数，对于i=0到i=n-1，每次使S[0]同S[i]交换(i=0,1,2,?,n-1)后,对S[1]—S[n-1]中的n-1个元素进行全排列，然后再交换其值，使它恢复为此次排列前的状态。 Void Permute(int S[], int j,int n) ∥对S[j]――S[n-1]中的n-j个元素进行全排列，j的初值为0 {int I,temp; if(j==n-1) {for(i=0;i for(i=j;i {temp=S[j]; S[j]=S[i]; S[i]=temp; Permute(S,j+1,n); temp=S[j]; S[j]=S[i]; S[i]=temp;} } 23