Greatest Common Divisor
Здравейте,
решавам от C++ Basic Syntax последната задача 06. Greatest Common Divisor (линк) и попаднах в интернет на следното решение:
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main() {
int a , b;
cout << "Enter the values of a and b: " << endl;
cin>>a>>b;
cout << "GCD of " << a << " and " << b <<" is " << gcd(a, b);
return 0;
}
И доколкото разбирам, когато извиквам gcd функцията, в нейния блок тя се се самоизвиква отново? Тоест освен циклите, които знаем до сега, може да правим цикли и чрез функция както е в този пример?
Отделно не разбирам ако a е по-малко от b как работи кода? Примерно ако a = 54, b = 888, то return gcd(b, a % b) би следвало в скобите да е (888, 54%888) и как 54%888 става 54? И от там вече на следващото завъртване е ясно (54, 888%54) и т.н. до gcd 6;
Иначе ето аз какво направих, за да може b да е винаги по-голямото:
#include <iostream>
int gcd(int a, int b) {
if (a > b) { //swap the two number so b is always the greater
int c = a;
a = b;
b = c;
}
while (a != 0) { // while a is > 0 then keep b % a
int c = b % a;
b = a;
a = c;
}
return b; // according euclidean algorithm when a is 0, b is the greatest common divison
}
int main() {
int x = 0;
int y = 0;
std::cin >> x >> y;
std::cout << gcd(x, y);
return 0;
}
Благодаря предварително!
Поздрави,
Илиян
Ясно. Много благодаря!
Така разписан оператора % е съвсем ясно защо се получаваше така.