Величайший общий делитель, использующий алгоритм Евклида?
Так что у меня проблема с моим кодом здесь.
Я кодирую наибольший общий делитель с помощью алгоритма Евклида и, похоже, не могу использовать цикл, чтобы деление повторялось до тех пор, пока я не получу наибольший общий делитель. Так что на данный момент я могу получить остаток, но не знаю, как дальше оттуда в принципе.
Любая помощь будет оценена!
Вот что у меня так далеко
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int a;//Holds the first number
int b;//Holds the second number
int temp;//Assign to greatest number
int hold;//Assign to smaller number
float euclid;//soon to be function?
int leftover;
float gcd;int main ()
{
cout<<"Welcome to Brian Garnadi's Version of GCD!\n"<<endl;
cout<<"Enter the first integer to be calculated: ";
cin>> a;
cout<<"Now enter the second integer: ";
cin>>b;
if (a>b)//Determines bigger number
{temp=a;
hold=b;
}
if (a<b)//Determines smaller number
{
temp=b;
hold=a;
}
leftover= temp%hold;
cout<<"\nThe remainder of the two numbers divided is "<<leftover<<".\n"<<endl;
}
Решение
На самом деле нет необходимости вычислять большее число, которым управляет алгоритм евклида.
Вот рабочий код:
#include <iostream>
using namespace std;
int gcd(int m,int n)
{
if(n == 0)
return m;
return gcd(n, m % n);
}
int main()
{
int a,b,answer;
cout<<"Welcome to Brian Garnadi's Version of GCD!\n"<<endl;
cout<<"Enter the first integer to be calculated: ";
cin>> a;
cout<<"Now enter the second integer: ";
cin>>b;
answer = gcd(a,b);
cout << "The GCD of the two numbers is : " << answer << endl;
return 0;
}
Другие решения
Не забудьте обработать отрицательные числа в алгоритме.
gcd(m, n) = gcd(n, m%n) when n != 0
= m when n = 0
функция:
int gcd(int m, int n) {
if(m == 0 && n == 0)
return -1;
if(m < 0) m = -m;
if(n < 0) n = -n;
int r;
while(n) {
r = m % n;
m = n;
n = r;
}
return m;
}