數據結構考研分類復習真題 第三章 答案[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);
　　} //算法結束

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22695.html