Самый большой общий делитель

Question

Я пытаюсь найти наибольший общий делитель для двух целых чисел. Но я не понимаю, что случилось с моим кодом:

public class Main { 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 

     int a = s.nextInt(); 
     int b = s.nextInt(); 

     while (a != 0 | b != 0) { 
      if (a >= b) { 
       a = a % b; 
      } else { 
       b = b % a; 
      } 
     } 

     if (a == 0) { 
      System.out.println(b); 
     } else { 
      System.out.println(a); 
     } 
    } 
} 

Answer 1

Просто измените

a != 0 | b != 0 

в

a != 0 && b != 0 

Потому что версия будет работать даже или б равен 0. Но вам нужно выйти из цикла, когда один из них равен 0. & & - лучше, чем &, потому что в вашем случае вам не нужно проверять правый оператор, если левый равен 0

Answer 2

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

То, что мы пытаемся найти это наибольшее число, которое делит как на и б.

Итак возникает вопрос, как мы это сделаем. Мы делаем петлю так же, как вы, но для этого случая предположим, что a больше b.

Первый шаг - начать цикл, пока расчет еще не завершен. Условием в нашем случае является , мы должны остановиться, когда любое из двух чисел станет равным нулю.

while (a != 0 && b != 0) 
{ 
    // Do the calculation here. 
} 

Теперь мы должны написать расчет. Мы предположили, что a больше b или оба равны.

Мы продолжаем назначая остаток в, деленное на б к .

while (a != 0 && b != 0) 
{ 
    a = a % b; 
} 

Это делает решение только половине правильного, мы будем иметь дело с другим случаем, то есть когда б больше . Почему это происходит после некоторого набора итераций, а станет меньше, чем b, и это приведет к тому, что a будет установлено в .

Так давайте сделаем то же самое решение для другого случая, когда меньше б.

while (a != 0 && b != 0) 
{ 
    if (a > b) 
     a = a % b; 
    else 
     b = b % a; 
} 

И это то, что вы хотите достичь. Решение будет отличным от нуля.

Давайте просто не остановимся здесь и посмотрим, почему ваша текущая версия не работает. У вас это было в вашем состоянии.

Ваше состояние:

a != 0 | b != 0 

Здесь используется побитовое оператор OR, между двумя булевыми значений, что приходит к следующему. Предположим, что любой из a и b равен нулю.

Случай 1:

a != 0 => true 
b != 0 => false 

true | false => true 

Случай 2:

a != 0 => false 
b != 0 => true 

false | true => true 

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

Надеюсь, это поможет.