наибольшая общая фактор-функция

Question

Я пытаюсь решить эту проблему, где мне нужно найти GCD из двух введенных чисел, ссылаясь на функцию. Тем не менее, я не уверен, где именно я облажался. Вот точный вопрос для справки:

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

Я попытался создать функцию для поиска GCD, а затем просто сослаться на функцию позже. Я не уверен, что я делаю не так.

#include <iomanip>
using namespace std;


int gcd;

cout << "Enter a valid integer: ";
  cin >> n >> m;

int digit = number(n, m);



return 0;
}

int number(int n, int m){

  for (int i=1; i<=n; ++i){
    int gcd = i;
    if(n%i==0 && m%i==0) {
      break;
  }

    return gcd;
}
  }

Я должен получить это: Введите два целых числа: 12 8 GCD из 12 и 8 равен 4.

Но вместо этого я получаю сообщение об ошибке, поскольку gcd не объявляется в этой области, что не имеет смысла, поскольку я объявил его как int как внутри функции, так и снаружи.

Answer 1

Простое рекурсивное решение ... попробуйте это.

int gcd(int a, int b)
{
    if(b==0)
       return a;
    else
       gcd(b, a%b);
}

То же самое можно достичь без рекурсии -

int gcd(int a, int b)
{
     while(b!=0)
     {
         int tmp = a;
         a = b;
         b = tmp % b;
     {
     return a;
 }

Теперь основная функция ..

#include<iostream>
using namespace std;
int main()
{
   int a,b;
   cout<<"Enter two number: ";
   cin>>a>>b;
   cout<<"GCD of two number: "<<gcd(a,b)<<endl;
}

Answer 2

Для этого есть довольно хорошие рекурсивные алгоритмы, но поскольку они не разрешены, я очистил вашу реализацию:

• Замените неисправный iomanip на iostream
• Измените приглашение вводаот "Введите целое число" до "Введите два целых числа"
• Удален i из вашего основного, он вам не нужен
• Заменена переменная на gcd в вашем основном
• Добавленоcout для отображения результата в вашем основном
• С вашей функцией gcdf я переписал ее, сохранив только ваше условие прерывания
• Цикл, соответствующий вашему условию прерывания, должен быть обратным отсчетом, начиная с соответствующего числа (т.е. min (m, n) должно быть начальным значением, и мы возвращаемся назад, пока не достигнем 1).

#include <iostream>
using namespace std;

int gcdfunction(int n, int m);

int main() {
  int n, m;

  cout << "Enter two integers: ";
  cin >> n >> m;

  int gcd = gcdfunction(n, m);
  cout << "GCD: " << gcd << "\n";
  return 0;
}

int gcdfunction(int n, int m){
  for (int i = m<=n ? m:n ; i > 1; i--) {
    if (n%i==0 && m%i==0) return i;
  }
  return 1;
}

Answer 3

Для правильной работы вашей функции необходимо немного настроить.

1. gcd необходимо определить вне цикла for, чтобы его можно было использовать в качестве возвращаемого значения.
2. В цикле for использование break в операторе if логически неверно.Если вы сделаете это, вы всегда получите 1 в качестве ответа.После всего, n % 1 и m % 1 будут равны нулю для всех значений n и m.

Вот обновленная версия, которая работает в моих тестах.

int gcdfunction(int n, int m){

   int gcd = 1;
   for (int i=1; i<=n; ++i){
      if(n%i==0 && m%i==0) {
         gcd = i;
      }
   }

   return gcd;
}

Обратите внимание, что евклидов алгоритм , вероятно, является наиболее эффективным алгоритмом для вычисления GCD из двух чисел.

Евклидов алгоритм может быть легко реализован с использованием нерекурсивной функции.

int gcdfunction(int n, int m){

   // Make sure n is the smaller of the numbers.
   if ( n > m )
   {
      std::swap(n, m);
   }

   while ( m % n != 0 )
   {
      int next = m % n;
      m = n;
      n = next;
   }

   return n;
}

Answer 4

Я надеюсь, что вы ищете что-то вроде этого

#include <stdio.h>

int hcf(int, int); //function declaration 

int main()
{
int a, b, result;

printf(“Enter the two numbers to find their HCF: “);
scanf(“%d%d”, &a, &b);
result = hcf(a, b);
printf(“The HCF of %d and %d is %d.\n”, a, b, result);

return 0;
}

int hcf(int a, int b)
{
            while (a != b)
            {
                  if (a > b)
                 {
                            a = a – b;
                  }
           else
                    {
                         b = b – a;
                   }
}
return a;
}

Простая программа, которую легко понять.