时间戳

首页 > 解决方案 > 用Java展示GCD的全过程

java - 用Java展示GCD的全过程

问题描述

我对 Java 并不陌生（几年前学习过，但由于工作原因停止了 5-6 年），我正试图再次与它取得联系。我的一个朋友给了我可以练习的练习题，但这对我来说很难。它基本上显示了使用欧几里得算法找到 GCD 的步骤。我做了所有事情，但是一旦我输入了一个大数字，GCD 所需的最后一个细节就丢失了。

这是我到目前为止所做的代码：

import java.util.Scanner;

class mpONE {
   public static void main (String[] args) 
   {
      System.out.println("Finding GCD Using Euclid's Algorithm");
      Scanner num = new Scanner(System.in);
      System.out.println("Enter your first (higher) number: ");
      int n1 = num.nextInt();
      System.out.println("Enter your second (lower) number: ");
      int n2 = num.nextInt();
      System.out.println("Numbers for finding GCD are: " + n1 + " " + n2);
      System.out.println("Computing for GCD... ");

      for (int i = 0; i <= n2; i++)
      {
         int g = n1/n2;
         int f = (g * n2);
         int h = n1 - f;
         System.out.print(n1 + " = " + "(" + n2 + " * " + g + ") + " + h);
         n1 = n2;
         n2 = h;
         System.out.println();
         if (h == 0)
         {
            break;
         }
     }

     for (int i = 1; i <= n1 && i <= n2; ++i) {
         if (n1 % i == 0 && n2 % i == 0)
         {
            int ans = i;
            System.out.println("Your GCD is " + ans);
         }
      }   
    } 
 }

对于较小的数字，它确实有效（“+ h”应该为 0），但对于大数字，它会在显示 0 余数之前停止。谢谢你的帮助！

标签： java

解决方案

只需更改if(h==0)块的位置：

import java.util.Scanner;

class mpONE {
   public static void main (String[] args) 
   {
      System.out.println("Finding GCD Using Euclid's Algorithm");
      Scanner num = new Scanner(System.in);
      System.out.println("Enter your first (higher) number: ");
      int n1 = num.nextInt();
      System.out.println("Enter your second (lower) number: ");
      int n2 = num.nextInt();
      System.out.println("Numbers for finding GCD are: " + n1 + " " + n2);
      System.out.println("Computing for GCD... ");

      for (int i = 0; i <= n2; i++)
      {
         int g = n1/n2;
         int f = (g * n2);
         int h = n1 - f;
         System.out.print(n1 + " = " + "(" + n2 + " * " + g + ") + " + h);
         System.out.println();
         if (h == 0)
         {
            break;
         }
         n1 = n2;
         n2 = h;
     }

     for (int i = 1; i <= n1 && i <= n2; ++i) {
         if (n1 % i == 0 && n2 % i == 0)
         {
            int ans = i;
            System.out.println("Your GCD is " + ans);
         }
      }   
    } 
 }

推荐阅读