1

在这里，我试图找到一组数字的最小公倍数。我使用以下公式来找到使用最大公约数来找出 LCM 的值。

在此处输入图像描述

我的程序正确计算了 GCD，但是当使用 GCD 找出 LCM 时，它给出了错误的 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);
}
4

4 回答 4

0

您的代码中有多个问题：

  • 您为数组的所有元素计算 LCM，但 GCD 仅为 2 个初始值。

  • 在除以 GCD 之前，乘法公式可能会溢出。您应该以相反的顺序执行操作，并且仍然检查潜在的溢出。

  • 的原型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;
}
于 2018-09-30T18:12:19.463 回答
0

这有帮助吗？或者您的目标是在尽可能少地调用 findGCD 的同时计算 GCD 和 LCM？

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);
}
于 2016-10-24T13:43:15.087 回答
0 
#include <stdio.h>
#include <stdlib.h>
#define VSTUP "cisla.txt"
#define VYSTUP "vystup.txt"

int nsd(int x,int y){
    int delitel = (x < y) ? x : y;
    while(x % delitel != 0 || y % delitel != 0)
        delitel--;
    return delitel;
}

int nsn(int x,int y){
    int nasobek = (x > y) ? x : y;
    while(nasobek % x != 0 || nasobek % y != 0)
        nasobek += (x > y) ? x : y;
    return nasobek;
}

int main(int argc, char** argv) {
    FILE * vstup;
    FILE * vystup;
    int c1, c2;
    int i = 1, j = 1;
    vstup = fopen (VSTUP,"r");
    if (vstup == NULL){
        printf("Soubor %s nebyl otevren.\n",VSTUP);
        return (EXIT_FAILURE);
    }
    vystup = fopen (VYSTUP,"w");
    printf("Vypis cisel ze souboru %s\n-------------------------------- \n",VSTUP);
    fprintf(vystup,"Vypis delitelnych cisel ze souboru %s\n--------------------------------------------\n",VYSTUP);
    printf("%7s%7s%7s%7s%7s\n","poradi","cislo1","cislo2","nsn","nsd");
    fprintf(vystup,"%7s%7s%7s%7s%7s\n","poradi","cislo1","cislo2","nsn","nsd");
    while (fscanf(vstup,"%d %d",&c1,&c2) == 2){
        printf("%6d.%7d%7d%7d%7d\n",i,c1,c2,nsn(c1,c2),nsd(c1,c2));
        if (nsd(c1,c2) != 1){
            fprintf(vystup,"%6d.%7d%7d%7d%7d\n",j,c1,c2,nsn(c1,c2),nsd(c1,c2));
            j++;
        }
        i++;
    }
    printf("\nSoubor %s obsahuje %d dvojic cisel.\n\n",VSTUP,i-1);
    fprintf(vystup,"\nSoubor %s obsahuje %d dvojic cisel.\n",VYSTUP,j-1);
    if (fclose (vstup) == EOF)
        printf("Soubor %s nebyl uzavren.\n",VSTUP);
    if (fclose (vystup) == EOF)
        printf("Soubor %s se nepovedlo vytvorit.\n",VYSTUP);
    else
        printf("Byl vytvoren soubor delitelnych cisel %s.\n\n",VYSTUP);
    return (EXIT_SUCCESS);
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define VSTUP "cisla.txt"
#define VYSTUP "vystup.txt"


int mocnina (int z, int e){
    int v = 1;
    for(;e > 0;e--)
        v *= z;
    return v;
}

int prvocislo(int n){
    int i;
    for(i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) 
            return 0;
        }
    return 1;
}

int main(int argc, char** argv) {
    FILE * vstup;
    FILE * vystup;
    int z,e;
    int i = 1, j = 1;
    vstup = fopen (VSTUP,"r");
    if (vstup == NULL){
        printf("Soubor %s nebyl otevren.\n",VSTUP);
        return (EXIT_FAILURE);
    }
    vystup = fopen (VYSTUP,"w");
    printf("Vystup cisel ze souboru %s\n",VSTUP);
    printf("---------------------------------\n");
    printf("%6s%9s%9s%9s\n","poradi","zaklad","exponent","mocnina");
    fprintf(vystup,"Vystup cisel s prvociselnym zakladem ze souboru %s\n",VYSTUP);
    fprintf(vystup,"---------------------------------------------------------\n");
    while( fscanf (vstup,"%d %d",&z,&e) == 2){
        printf("%5d.%9d%9d%9d\n",i,z,e,mocnina(z,e));
        if (prvocislo(z)){
            fprintf(vystup,"%5d.%8d%8d%8d\n",j,z,e,mocnina(z,e));
            j++;
        }
        i++;
    } 
    fprintf(vystup,"Soubor %s obsahuje %d dvojic cisel.\n",VYSTUP,j-1);
    if (fclose (vstup) == EOF)
        printf("Soubor %s nebyl uzavren.\n",VSTUP);
    if (fclose (vystup) == EOF)
        printf("Soubor %s se nepovedlo vytvorit.\n\n",VYSTUP);
    else
        printf("\nByl vytvoren soubor cisel %s s poctem dvojic cisel rovnym %d.\n\n",VYSTUP,j-1);
    return (EXIT_SUCCESS);
}
于 2018-10-03T07:21:25.230 回答
0

您提到的上述公式仅适用于两个数字而不是多个数字（在您的情况下为 10）。3个数字的正确公式是：

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

有关更多信息，请参阅此https://math.stackexchange.com/questions/319297/gcd-to-lcm-of-multiple-numbers

于 2016-10-25T11:29:27.620 回答