欧几里得算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1181字，纯文字阅读大概需要2分钟。

内容图文

拓展欧几里得算法：

1. 概述：

不仅能求出两个正整数m和n的最大公因数d，还能求出两个整数x和y(不一定为正)使得mx+ny=d

2. 分析：

这个其实挺简单的步骤如下:

• 我们假设m是d的a倍；n是d的b倍，而a和b我们是可以通过求最大公因数d来求出来的
• 原式可以化为：ax+by=1;
• 这就是一个简单的一次方程了，我们可以得到方程的无穷多种解；
• 对于给定的x。y=（1-ax）/ b。
• 这种情况给出的是一般解，我们要给出整个方程的通解
• 这个一个非齐次方程，通解等于对应齐次方程的通解+自身的一个特解

最后得

x=x0+b*t

y=y0- a*t

3. Java实现如下：

GCF gcf = new GCF();
public String findResult(int a,int b){
    int g = gcf.FindGCF(a,b);
    int k1,k2;
    k1=a/g;
    k2=b/g;
    return "y=(1 - "+k1+"x) / "+k2;
}

• 这里只对一般解进行求值。具体求通解。并不难，自己实现~

GCF类的代码

public class GCF {

    /**
     * @Mehtods:递归方法实现找最大公因数
     * */
    public int reFindGCD(int a,int b){
        if(b==0){
            return a;
        }else{
            return reFindGCD(b,a%b);
        }
    }

    /**
     * @Methods:非递归找最大公因数，辗转相除法
     * */
    public int FindGCF(int a,int b){
        int min=Math.min(a,b);
        int max=Math.max(a,b);
        while(max%min!=0){
            int temp=max%min;
            max=min;
            min=temp;
        }
        return min;
    }
    /**
     * @Methods:找最小公倍数，辗转相除法
     * */
    public int FindLCM(int a,int b){
        int gcf=FindGCF(a,b);
        int k=1;
        while((gcf*k)%a!=0||(gcf*k)%b!=0){
            k++;
        }
        return gcf*k;
    }
}

内容总结

以上是互联网集市为您收集整理的欧几里得算法全部内容，希望文章能够帮你解决欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---