黑马程序员技术交流社区

标题: 给大家一个超难的题，会做的，我给你加分 [打印本页]

---

作者: 廉伟    时间: 2012-10-2 13:46
标题: 给大家一个超难的题，会做的，我给你加分


题目：输入两个正整数m和n，求其最大公约数和最小公倍数。
<求最大公约数>
算法（1）设计：
E0.[确保m n] 若m n，则m n。
E1.[求余数] 以n除m并令r为所得余数。（我们将有0 r n。）
E2.[余数为0?] 若r为0，算法结束，n即为所求答案。
E3.[减少] 置m n，n r，并返回步骤E1。
数学证明：
(1)        若m%n=0，则n为所求最大公因子
(2)        若m%n 0，则只需证明下面命题成立
如果某数是n与m%n的最大公因子，则这个数也是m和n的最大公因子。(上面算法可化为这句话)
证明：
假设a是n和m%n的最大公因子，则有：

因有(m%n)%a=0，故可设m%n=k*a，k为正整数。又n%a=0，故可设n=p*a，p也为正整数。
可得数学表达式：m=t*n+m%n，其中t为不小于0的整数。
因此有：m=t*p*a+k*a=(t*p+k)*a，因此可得m%a=0
因此有如下两个表达式：

a为m和n的公因子已经证毕。
如何确定a为m和n的最大公因子？（可用反证法证明）
证明：
假设m和n存在公因子b，且有b>a。
则有:

可以仿照上面的推导过程得出：

则b也是n和m%n的公因子，又b>a，与a是n和m%n的最大公因子矛盾。
综上，如果某数是n与m%n的最大公因子，则这个数也是m和n的最大公因子。
(3)        证毕。
对步骤E0的分析：
若m<n，则m%n=m。当进行E0后，m为较大者，m%n n。
算法（2）设计：
F1.[余数m/n] 以n除m，并令m为余数。
F2.[它是0?] 如果m=0，则此算法以n为答案而终止。
F3.[余数n/m] 以m除n，并令n是余数。
F4.[它是0?] 如果n=0，则算法以答案m而终止，否则返回步骤F1。
算法（2）可仿照算法（1）进行证明
<求最大公倍数>
算法设计：
F1：求出m和n的较大者，令较大者为m，较小者为n。
F2：判断m能否被n整除，若能则m为两者最小公倍数。
F2：将n分解因式。
F3：将m依次乘以n的因子，判断乘积能否被n整除，若能则乘积为两者最小公倍数。
根据上面的算法，程序如下：
import java.io.*;
import java.util.*;
public class Text6 {
        public static void fenJie(Vector<Integer> m,int n)
        {
                for(int i=2;i<=n;i++)
                {
                        if(n==i)
                        {  
                                m.addElement(i);
                                return;
                        }        
                        if(n>i&&(n%i==0))
                        {
                                n=n/i;
                                m.addElement(i);
                                fenJie(m,n);
                                break;
                        }        
                }
        }
        public static int gongBeiShu(Vector<Integer> m,int a,int b)
        {
                int chengji=1;
                if(a%b==0)
                        return a;
                for(int i=0;i<m.size();i++)
                {
                        chengji=chengji*m.elementAt(i);
                        if((a*chengji)%b==0)
                        {
                                return a*chengji;
                        }
                }
                return a*b;
        }
        public static int bigYinZi(int a,int b)
        {
                int r=a%b;
                int m=0;
                if(r==0)
                        return b;
                else
                {
                        a=b;
                        b=r;
                        m=bigYinZi(a,b);
                        return m;
                }
        }
        public static void main(String[] args) throws IOException
        {
                Integer shu1=0;Integer shu2=0;int t=0;
                Vector<Integer> pool=new Vector<Integer>();
                BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
                System.out.print("请输入第一个正整数：");
                shu1=(new Integer(stdin.readLine()));
                System.out.print("请输入第二个正整数：");
                shu2=(new Integer(stdin.readLine()));
                if(shu1<shu2)
                {
     

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2