Java教程

欧几里得算法

本文主要是介绍欧几里得算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

拓展欧几里得算法:

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;
    }
}

这篇关于欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!