найти наименьшее общее кратное

Здесь я пытаюсь найти наименьшее общее кратное для массива чисел. Я использовал следующую формулу, чтобы найти значение, использующее наибольший общий делитель для определения НОК.

введите описание изображения здесь

Моя программа вычисляет GCD правильно, но когда дело доходит до определения LCM с использованием GCD, она дает неверное значение LCM. Что может быть не так в моей логике. Любая помощь приветствуется.

#include <stdio.h>

int main() {
   int arr[10] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
   int GCD = findGCD(arr[0], arr[1]);
   int LCM = (arr[0] * arr[1]) / GCD;
   int i;
   for (i = 2; i < sizeof(arr) / sizeof(arr[0]); i++) {
        int temp = GCD;
        GCD = findGCD(temp, arr[i]);
        LCM = (temp * arr[i]) / GCD;
   }
   printf("GCD IS %d AND LCM IS %d", GCD, LCM);
}

int findGCD(int num1, int num2) {
    if (num2 == 0) {
        return num1;
    }
    if (num1 % num2 == 0) {
        return num2;
    }
    return findGCD(num2, num1 % num2);
}

c arrays greatest-common-divisor lcm
person AL-zami    schedule 24.10.2016    source источник
comment
gcd и lcm чего и чего?   -  person user3528438    schedule 24.10.2016
comment
Пожалуйста, покажите пример ожидаемого и фактического результата.   -  person Jabberwocky    schedule 24.10.2016
comment
int arr[10]={49,21,7,14,28,42,35,49,56,70,64}; должно быть int arr[11]={49,21,7,14,28,42,35,49,56,70,64};   -  person Marek Klein    schedule 24.10.2016
comment
Может быть проблема в вашем arr [10]. вы даете в нем 11 чисел.   -  person chex    schedule 24.10.2016
comment
Обратите внимание, что (temp*arr[i])/GCD может переполняться, когда эквивалент (temp/GCD)*arr[i]) - нет.   -  person chux - Reinstate Monica    schedule 24.10.2016

Ответы (4)


arrow_upward
0
arrow_downward

Это помогает? Или вашей целью было вычислить GCD и LCM при вызове findGCD как можно реже?

int main(){
   int arr[10]={10,20,30,40,50,60,70,80,90,100};
   int GCD=arr[0];
   int LCM=arr[0];
   int i;

   for(i=1;i<sizeof(arr)/sizeof(arr[0]);i++){
        GCD = findGCD(GCD,arr[i]);
        LCM = (LCM * arr[i]) / findGCD(LCM, arr[i]);
   }

   printf("GCD IS %d AND LCM IS %d",GCD,LCM);
}
person Marek Klein    schedule 24.10.2016

arrow_upward
0
arrow_downward

Вышеупомянутая формула верна только для двух чисел, а не для нескольких чисел (в вашем случае 10). Правильная формула для трех чисел:

lcm(a,b,c)=abc/gcd(ab,bc,ca)

Для получения дополнительной информации см. Этот https://math.stackexchange.com/questions/319297/gcd-to-lcm-of-multiple-numbers

person Ishpreet    schedule 25.10.2016

arrow_upward
0
arrow_downward

В вашем коде несколько проблем:

  • вы вычисляете НОК для всех элементов массива, но НОД только для двух начальных значений.

  • Формула умножения может переполниться до того, как вы разделите на НОД. Вы должны выполнить операцию в обратном порядке и по-прежнему проверять возможное переполнение.

  • прототип для findGCD неверен: он возвращает int.

Вот исправленная версия:

#include <limits.h>
#include <stdio.h>

int findGCD(int num1, int num2) {
    if (num2 == 0) {
        return num1;
    }
    if (num1 % num2 == 0) {
        return num2;
    }
    return findGCD(num2, num1 % num2);
}

int main() {
    int arr[10] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
    int GCD = arr[0];
    int LCM = arr[0];
    size_t i;

    for (i = 1; i < sizeof(arr) / sizeof(arr[0]); i++) {
        if (LCM == 0 || arr[i] == 0) {
            LCM = 0;
            break;
        }
        GCD = findGCD(GCD, arr[i]);
        LCM = LCM / findGCD(LCM, arr[i]);
        if (arr[i] > INT_MAX / LCM) {
            printf("integer overflow: the LCM exceeds the range of type int\n");
            return 1;
        }
        LCM = LCM * arr[i];
    }
    printf("GCD IS %d AND LCM IS %d", GCD, LCM);
    return 0;
}
person chqrlie    schedule 30.09.2018

arrow_upward

arrow_downward

person    schedule
comment
Пожалуйста, объясните свой подход и ответ на исходный вопрос. - person Chota Bheem; 03.10.2018