Как получить (Величайший общий делитель) GCD пар

Question

Это простая задача, но я не могу понять, как это сделать

Вот пример структуры функции

private double GetGCD(double num1, double num2)
{
    //should return the GCD of the two double
}

данные испытаний

   num1 = 6;
   num2 = 3;
   *return value must be 3*

   num1 = 8.8;
   num2 = 6.6;
   *return value must be 2.2*

   num1 = 5.1;
   num2 = 8.5;
   *return value must be 1.7*

примечание: максимальное количество знаков после запятой - 1. язык программирования не важен. мне просто нужен algorthm

пожалуйста, помогите .. спасибо!

Answer 1

Если у вас только один десятичный знак, умножьте числа на 10, преобразуйте их в целые числа и запустите целочисленную GCD-функцию .

Это также спасет вас Ошибки точности с плавающей запятой .

Цитируя этот ответ , базовый евклидов алгоритм на Python (для целых чисел!):

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

Итак, ваш код должен выглядеть примерно так:

 def gcd_floats(x,y):
     return gcd( int(x*10), int(y*10) )/10

Answer 2

Когда это 8,8 и 6,6, вы можете найти GCD 88 и 66, а затем разделить его на 10.

Answer 3

Нет такого понятия, как GCD числа, которое не является дискретным.Однако ваш случай более конкретен.Если вы вводите не двойное число, а десятичное, вы можете преобразовать его в дробную часть, умножить знаменатели, найти ГКД числителей и разделить обратно вниз.То есть:

8.800 = 8800/1000 = 44/5 (by GCD)
6.600 = 6600/1000 = 33/5 (by GCD)

5.100 = 5100/1000 = 51/10
8.500 = 8500/1000 = 17/2

Полезно упростить дроби на этом шаге, чтобы наши числа не становились слишком большими.

Переход к общему знаменателю:

44*5/5*5 = 220/25
33*5/5*5 = 165/25

51*2/2*10 = 102/20
17*10/2*10 = 170/20

GCD числителя:

gcd(165,220) = 55

gcd(102,170) = 34

Так что ответы 55/25 и 34 / 20.

Answer 4

вот источник из Google с некоторым кодом Java: http://www.merriampark.com/gcd.htm это довольно полный текст.

Answer 5

В Интернете есть миллионы мест, где можно найти код для функции GCD. Поскольку, строго говоря, он определен только для целых чисел, я предлагаю вам умножить ваши двойные числа на 10, обработать GCD и разделить результат на 10. Это избавит вас от боли, возникшей из-за использования неправильного типа данных.

Answer 6

Используя 2 метода

1. Традиционный метод деления
2. Метод Евклида

    class GCD
    {
        public static void main(String[] args)
        {
            int a = (int)(1.2*10);
            int b = (int)(3.4*10);

            System.out.println((float)gcd(a, b)/10);
        }
    // 1

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

    // 2
        public static int gcd(int a, int b)
        {
            int k,i;

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

            for(i=k; i>=2; i--)
            {
                if( (a%i==0)&&(b%i==0) )
                {
                    break;
                }
            }
            return i;
        }
    }