数据结构练习 - 第三章 - 栈和队列

}∥算法结束

使用栈，消除递归的非递归算法如下： 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