Как мне найти GCD с циклом while? Как работает оператор модуля?

Question

#include <iostream>

int GCD()
{
    int a,b,k;
    cout<<"Enter a and b"<<endl;
    cin>>a>>b;
    cout<<endl;

    if (a>b)
    {
        k=a;
    }
    else
    {
        k=b;
    }

    cout<<k<<endl;

    do
    {
        k=k-1;
    } while(a%k !=0 && b%k !=0);

    cout<<k<<endl;

    return 0;
 }

Почему такая программа не работает правильно? Например, когда я ввожу 125 и 5, ответ - 25, но должен быть 5? Я не прав с логикой в ​​то время как цикл? Как я понял, проблема в модуле оператора. Когда k достигает 25, это говорит о том, что 125%25=0 и 5%=25=0. Как я могу это исправить?

Answer 1

У вас есть некоторые ошибки здесь:

1. GCD меньше или равен меньшему числу. В настоящее время вы начинаете проверять большее число. Вам нужно перевернуть блок if на if (a<b). (не совсем ошибка, но вы проверяете гораздо больше чисел, чем необходимо)

2. Вам необходимо проверить, является ли начальный k GCD. При использовании do {} while() первый проверяемый номер - k-1. Вместо этого используйте простой while. Также условие цикла имеет логический недостаток.

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

Обратите внимание, что скобки вокруг модуля не являются необходимыми, но немного улучшают читаемость.

Ваш код не будет компилироваться под всеми компиляторами, и вы не должны пропускать пространство имен std::.

Answer 2

Ваш оператор while имеет логическую ошибку. Оно должно быть

while(!(a%k == 0 && b%k == 0));

Когда k равно 25, 125%25==0, поэтому в вашем while выражении a%k !=0 часть равна false, поэтому она выходит из вашего do-while, но это необходимочтобы проверить, равен ли b%k 0 или нет!

Также ваша реализация имеет тенденцию выполняться медленно, когда a и b велики. Вы можете посмотреть эффективные решения .