Нахождение наибольшего общего делителя с помощью евклидова алгоритма - PullRequest
Новая
       19

Нахождение наибольшего общего делителя с помощью евклидова алгоритма

0 голосов
/ 25 марта 2020

Я пытался найти решение, с помощью которого я могу найти GCD из 2 чисел наиболее оптимальным способом, поэтому мне нужна некоторая помощь здесь, чтобы выяснить, работает ли программа, которую я выпустил, для всех возможных случаев или в любом случае это сломается или я могу улучшить его, чтобы сделать его оптимальным решением.

Программа: 

public static void main(String[] args) {
     int a= 153;
        int b= 81;
        boolean flag = true;
        int gcd = 1;
        while(flag)
        {
          if(a>b && a%b ==0)
           {
                flag = false;
                gcd = b;
            }
            else if(b>a && b%a ==0)
            {
                flag=false;
                gcd = a;
            }
            else if( a>b)
            a = a-b;
            else
            b = b-a;
        }
        System.out.println(gcd);

}

Пожалуйста, помогите мне найти правильное решение, спасибо заранее.

1 Ответ

1 голос
/ 25 марта 2020

Попробуйте что-нибудь подобное. Алгоритм Евклида GCD в основном говорит это: GCD из 2 чисел (мы будем называть их больше и меньше) равен GCD меньшего числа и разности между большим и меньшим числом. Повторяйте процедуру, пока два числа не будут одинаковыми. Ниже приведено итеративное решение. 

    int a= 153 , b = 81, gcd = 1;

    while( gcd != a ) {

        if( a > b ) a -= b;
        else if( b > a) b -= a;
        else gcd = a;
    }

    System.out.println(gcd);

Это рекурсивное решение. Надеюсь, это поможет. 

    public static int euclidGCD(int a, int b) {
        if (b == a) return a;
        if (b > a)  return euclidGCD(b - a, a);
        else  return euclidGCD(a - b, b);
}

Вот модификация вашей программы. Чтобы протестировать программу, лучше всего записать ее условия и случаи. В этом упражнении есть два условия:

  • 1.) Число должно быть целым числом
  • 2.) Число должно быть положительным.

Работа с числами обычно имеет дискретное количество случаев. В этом упражнении есть два случая:

  • 1.) Числа равны.
  • 2.) Номера разные.

Ваш код неверен, когда a равно b (попробуйте сами). Когда цифры разные, ваш код работает нормально. Ниже приведена модификация. 

    int a= 55;
    int b= 55;
    boolean flag = true;
    int gcd = b;
    while(flag && b != a)
    {
        if(a>b && a%b ==0)
        {
            flag = false;
            gcd = b;
        }
        else if(b>a && b%a ==0)
        {
            flag=false;
            gcd = a;
        }
        else if( a>b)
            a = a-b;
        else
            b = b-a;
    }
    System.out.println(gcd);
...