数据结构考研分类复习真题 第三章 答案[27]

int MaxValue (int a[]int n)//设整数序列存于数组a中共有n个本算法求解其最大值

{if (n==) max=a[];

else if a[n]>MaxValue(an) max=a[n];

else max=MaxValue(an);

return(max);

}

本题与上题类似只是这里是同时求n个数中的最大值和最小值的递归算法

int MinMaxValue(int A[]int nint *maxint *min)//一维数组A中存放有n个整型数本算法递归的求出其中的最小数

{if (n>)

{if(*max<A[n]) *max=A[n];

if(*min>A[n]) *min=A[n];

MinMaxValue(Anmaxmin);

}//算法结束

[算法讨论]调用本算法的格式是MinMaxValue(arrn&max&min);其中arr是具有n个整数的一维数组max=是最大数的初值min=是最小数的初值

[题目分析] 求两个正整数m和n的最大公因子本题叙述的运算方法叫辗转相除法也称欧几里德定理其函数定义为

gcd(mn)=

int gcd (int mn)//求正整数m和n的最大公因子的递归算法

{if(m<n) return(gcd(nm))//若m<n则m和n互换

if(n==) return(m); else return(gcd(nm%n));

}//算法结束

使用栈消除递归的非递归算法如下

int gcd(int mn)

{int s[max][];//s是栈容量max足够大

top=; s[top][]=m; s[top][]=n;

while (s[top][]!=)

if (s[top][]<s[top][])//若m<n则交换两数

{t=s[top][]; s[top][]=s[top][]; s[top][]=t;}

else{t=s[top][]%s[top][]; top++; s[top][]=s[top][]; s[top][]=t; }

return(s[top][]);

}//算法结束

由于是尾递归可以不使用栈其非递归算法如下

int gcd (int mn)

//求正整数m和n的最大公因子

{if (m<n){t=m;m=n;n=t;}// 若m<n则m和n互换

while (n!=) {t=m; m=n; n=t%n;}

return(m);

} //算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []