如何在Java中明确写出扩展欧几里得算法代码？ [英] How to write Extended Euclidean Algorithm code wise in Java?

问题描述

我有一个问题实际上需要一点了解欧几里得算法。问题很简单intFirst和intSecond数字由用户通过Scanner给出。
比我们需要找到他们最大的公约数。这个过程如下所述：

现在假设第一个数字是：42，第二个是：30 - 他们由用户给出。 -

int x，y;

（x * First）+（y * Second）= gcd（First，Second）; // X ？ y？

要查找GCD，可以使用：gcd（First，Second）;代码如下：

  public static int gcd（int a，int b）
 {
 if a == 0 || b == 0）return a + b; // base case 
 return gcd（b，a％b）; 
} 
  

示例输入：第一：24秒：48，输出应为x：（ -3）和y：2

样品输入：第一：42秒：30，输出应为x：（-2）和y：3

样品输入：第一：35第二：05和输出应为x：（0）和y：1

 （x * First）+（y * Second ）= gcd（第一，第二）; //我们如何找到x和y？ 
  

如果您可以在java中显示解决方案代码，感谢您的检查！

解决方案

感谢帮助我出来ajb，我解答了你的答案。所以对于那些希望看到代码的人来说：

  public class Main 
 {
 public static void main（String args []）
 {
 @SuppressWarnings（resource）
 System.out.println（你想尝试多少次？）
扫描仪读取=新扫描仪（System.in）; 
 int len = read.nextInt（）; 
 
（int w = 0; w  {
 System.out.print（请给空格分隔的数字）
 read.nextLine（）; 
 long tmp = read.nextLong（）; 
 long m = read.nextLong（）; 
 long n; 
 if（m  n = m; 
 m = tmp; 
} 
 else {
 n = tmp; 
} 
 
 long [] l1 = {m，1，0}; 
 long [] l2 = {n，0，1}; 
 long [] l3 = new long [3]; 
 
 while（l1 [0] -l2 [0] *（l1 [0] / l2 [0]）> 0）{
 for（int j = 0; j < ; j ++）l3 [j] = l2 [j]; 
 long q = l1 [0] / l2 [0]; （int i = 0; i <3; i ++）{
 l2 [i] =（l1 [i] -l2 [i] * q） （int k = 0; k <3; k ++）l1 [k] = 13 [k]; 
} 
 
 
} 
 
 System.out.printf（％d％d％d，l2 [1]，l2 [2]，l2 [0]）; // first two Bezouts identity Last one gcd 
} 
} 
} 
  

I have a question which is actually requires a bit of understanding Euclidian Algorithm. Problem is simple. An int "First" and int "Second" numbers are given by the user via Scanner. Than we need to find greatest common divisor of them. Than the process goes like explained below:

Now Assume that the First number is: 42 and the Second is: 30 - they've given by the user. -

int x, y;

(x * First) + (y * Second) = gcd(First, Second); // x ? y ?

To Find GCD you may use: gcd(First, Second); Code is below:

public static int gcd(int a, int b)    
    {    
        if(a == 0 || b == 0) return a+b; // base case   
        return gcd(b,a%b);    
    }    

Sample Input: First: 24 Second: 48 and Output should be x: (-3) and y: 2
Sample Input: First: 42 Second: 30 and Output should be x: (-2) and y: 3
Sample Input: First: 35 Second: 05 and Output should be x: (0) and y: 1

 (x * First) + (y * Second) = gcd(First, Second); // How can we find x and y ? 

I would very appreciate it if you could show a solution code wise in java thanks for checking!

解决方案

Thank's for helping me out ajb I solved it after digging your answer. So for the people who would like to see code wise:

public class Main    
{    
public static void main (String args[])   
{   
    @SuppressWarnings("resource")    
    System.out.println("How many times you would like to try ?")
    Scanner read = new Scanner(System.in);    
    int len = read.nextInt();    

    for(int w = 0; w < len; w++)    
    {
        System.out.print("Please give the numbers seperated by space: ")
        read.nextLine();
        long tmp = read.nextLong();
        long m = read.nextLong();
        long n;
        if (m < tmp) {      
            n = m;
            m = tmp;
        }
        else {
            n = tmp;
        }

        long[] l1 = {m, 1, 0};
        long[] l2 = {n, 0, 1};
        long[] l3 = new long[3]; 

        while (l1[0]-l2[0]*(l1[0]/l2[0]) > 0) {
            for (int j=0;j<3;j++) l3[j] = l2[j]; 
            long q = l1[0]/l2[0];        
            for (int i = 0; i < 3; i++) {
            l2[i] = (l1[i]-l2[i]*q);
            }

            for (int k=0;k<3;k++) l1[k] = l3[k];
        }

        System.out.printf("%d %d %d",l2[1],l2[2],l2[0]); // first two Bezouts identity Last One gcd
    }
}
}    

这篇关于如何在Java中明确写出扩展欧几里得算法代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！