Использование алгоритма Евклида для поиска GCF (GCD)
Я пытаюсь написать функцию, чтобы найти gcd из 2 чисел, используя алгоритм Евклида, который я нашел Вот.
Из большего числа вычитайте меньшее число столько раз, сколько сможете, пока не получите число, которое меньше малого числа. (или без получения отрицательного ответа) Теперь, используя исходное небольшое число и результат, меньшее число, повторите процесс. Повторяйте это, пока последний результат не станет равным нулю, и GCF не станет последним последним результатом с небольшим числом. Также см. Наш калькулятор алгоритма Евклида.
Пример: найти GCF (18, 27)
27 — 18 = 9
18 — 9 = 9
9 — 9 = 0
Итак, наибольший общий коэффициент 18 и 27 равен 9, наименьший результат, который мы имели до того, как достиг 0.
Следуя этим инструкциям, я написал функцию:
int hcf(int a, int b)
{
int small = (a < b)? a : b;
int big = (a > b)? a : b;
int res;
int gcf;
cout << "small = " << small << "\n";
cout << "big = " << big << "\n";
while ((res = big - small) > small && res > 0) {
cout << "res = " << res << "\n";
}
while ((gcf = small - res) > 0) {
cout << "gcf = " << gcf << "\n";
}return gcf;
}
Однако второй цикл кажется бесконечным. Кто-нибудь может объяснить почему?
Я знаю, что веб-сайт на самом деле показывает код (PHP), но я пытаюсь написать этот код, используя только инструкции, которые они дают.
Решение
Конечно, этот цикл бесконечен:
while ((gcf = small - res) > 0) {
cout << "gcf = " << gcf << "\n";
}
small а также res не меняйте в цикле, так gcf тоже нет Этот цикл эквивалентен:
gcf = small - res;
while (gcf > 0) {
cout << "gcf = " << gcf << "\n";
}
что, вероятно, более понятно.
Я бы перенес этот алгоритм в код:
int gcd(int a, int b) {
while (a != b) {
if (a > b) {
a -= b;
}
else {
b -= a;
}
}
return a;
}
Хотя обычно gcd реализован с использованием мода, так как он намного быстрее:
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
Другие решения