我的歐幾里得算法運行速度很慢

Question

這段代碼編譯得很好，但是當我運行它時，它會按照預期請求我的兩個數字，然後就坐在那裏，根本什麼都不做。我搜索了互聯網，並且整天都在做這件事。我終於放下心來，尋求幫助。

是不是自動循環備份的問題？在此之後的10個小時，我什麼也沒找到。

import java.util.Scanner; 

public class EA 
{ 
    public static void main (String[] args) 
    { 
     // get first integer from user 
     Scanner input = new Scanner(System.in); 
     System.out.println("Please enter the larger integer: "); 
     int I; 
     I = input.nextInt(); 

     // get second integer from user 
     System.out.println("Please enter the smaller integer: "); 
     int J; 
     J = input.nextInt(); 

     //resolve the issue of zero 
     while(J<1) 
     { 
      System.out.println("Can not divide by zero!"); 
      System.out.println("Please enter new smaller integer: "); 
      J = input.nextInt(); 

      //do the calculations 
      while(J>0) 
      { 
       int Remainder; 
       Remainder = I % J; 

       while(Remainder>0) 
       { 
        I = J; 
        J = Remainder; 

        return; 

       } 
       System.out.println("GCD is" + J); 
      } 
     } 
    } 
} 

Answer 1

有超過1個錯誤：在同時迴歸，算法和也先的支架。

1）當你解決零的問題，而支架必須被突然關閉後，您重新分配變量J.

while (J < 1) { 
    System.out.println("Can not divide by zero!"); 
    System.out.println("Please enter new smaller integer: "); 
    J = input.nextInt(); 
} 

2）算法的價值計算GCD如下：

function gcd(a, b) 
    while b ≠ 0 
     t := b 
     b := a mod t 
     a := t 
    return a 

這裏是你的代碼的正確版本：

public static void main(final String[] args) { 
    // get first integer from user 
    final Scanner input = new Scanner(System.in); 
    System.out.println("Please enter the larger integer: "); 
    int I; 
    I = input.nextInt(); 

    // get second integer from user 
    System.out.println("Please enter the smaller integer: "); 
    int J; 
    J = input.nextInt(); 

    // resolve the issue of zero 
    while (J < 1) { 
     System.out.println("Can not divide by zero!"); 
     System.out.println("Please enter new smaller integer: "); 
     J = input.nextInt(); 
    } 
    // do the calculations 
    while (J != 0) { 
     int Remainder; 
     Remainder = I % J; 
     I = J; 
     J = Remainder; 
    } 
    System.out.println("GCD is" + I); 

} 

Answer 2

在循環中間的return將結束執行。

這一個

while(Remainder>0) 
{ 
    I = J; 
    J = Remainder; 

    return; <------- THIS IS THE RETURN THAT BREAKS ALL 

} 

所以它不會給System.out.println。

更新：此外，你input.nextInt()兩次爲J。可能從您的描述中，它一直在等待您輸入第三個整數。

Answer 3

SJuan提的是，迴歸打破了循環，這是真實的，但即使它固定在那裏有一些其他問題：

• 內，而永遠不會結束（無限循環）
• 結果將儲存在J - 不在I
• System.out.println("GCD is " + I);應該印在外面的同時！

該程序的「心臟」應該這樣做：

// we get here with valid values stored in I,J 
    int Remainder = I % J; 
    //do the calculations 
    while(Remainder>0) 
    { 
     I = J; 
     J = Remainder; 
     Remainder = I % J; 
    } 
    System.out.println("GCD is " + J); 

Answer 4

其中OT她已經提到的事情，你很困惑while與if。您已將算法邏輯放入僅在第一個輸入錯誤時才運行的while循環中。

// get first integer from user 
Scanner input = new Scanner(System.in); 
System.out.println("Please enter the larger integer: "); 
int I; 
I = input.nextInt(); 

// get second integer from user 
System.out.println("Please enter the smaller integer: "); 
int J; 
J = input.nextInt(); 

//resolve the issue of zero 
while(J<1) 
{ 
    // You never reach here under ordinary conditions 
} 

Answer 5

歐幾里得的算法有一個缺點，因爲兩個輸入都應該是非零來計算最大公約數。但是，如果您想在輸入爲零（'0'）時找出GCD，則稍微調整一下邏輯。當其中一個輸入爲零時，GCD爲1，'a'應該大於'b'來計算GCD。檢查下面的代碼段：

if (a < b) { 
     int temp = a; 
     a = b; 
     b = temp; 
    } 
    if (b == 0) { 
     System.out.println("1"); 
    } else { 
     while (b != 0) { 
      r = a % b; 
      a = b; 
      b = r; 
     }