用于查找数组元素的 lcm 的 C 程序

你好，我不认为语言有问题 或编译器，尽管我有您的代码的增强版本。你可以试试 并检查它是否适合您。

#include <stdio.h>

int are_same(int array[], int length) {
    for (int i = 1; i < length; i++) {
        if (array[0] != array[i]) {
            return 0;
        }
    }
    return 1;
}

int get_min_index(int array[], int length) {
    int min_value = array[0];
    int min_index = 0;
    for (int i = 1; i < length; i++) {
        if (array[i] < min_value) {
            min_value = array[i];
            min_index = i;
        }
    }
    return min_index;
}

int calculate_lcm(int array[], int length) {
    int lcm = array[0];
    for (int i = 1; i < length; i++) {
        int a = lcm;
        int b = array[i];
        // Calculate the greatest common divisor (GCD) using Euclid's algorithm
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        // Calculate the least common multiple (LCM)
        lcm = (lcm * array[i]) / a;
    }
    return lcm;
}

int main(void) {
    int divisors[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
    int length = sizeof(divisors) / sizeof(divisors[0]);

    int lcm = calculate_lcm(divisors, length);

    printf("LCM = %d\n", lcm);
    return 0;
}

您的实现很好，可以完成工作。are_same

该算法找到最小的并添加其相应的除数，然后搜索最小的并重复执行相同的操作，该算法有一个错误，因为您将值加倍而不是将除数添加到其中。

即使正确实现，也可能需要很长时间才能完成，因为您搜索整个数组以便只更新一次一个值。相反，如果您可以将除数乘以 x 的乘积相加，使其至少与数组中的最大值一样大，则速度会更快。

然后稍作修改

• 搜索数组中的最大值。
• 用相应除数的倍数增加所有条目，使该值至少与最大值一样大。array
• 重复上述步骤，直到所有值都相等。

在这个例子中，我不关心最大的索引，所以这只返回最大的值：

int largest_value(int arr[], size_t length) {
    int l = arr[0];
    for(size_t i = 1; i < length; ++i) {
        if(arr[i] > l) l = arr[i];
    }
    return l;
}

函数需要复制传入数组（以修复当前实现中的错误）并实现上述算法：calculate_lcm

int calculate_lcm(const int array[], size_t length) {
    // copy array in to a "working array", wa:
    int* wa = malloc(length * sizeof *wa);
    if(!wa) exit(1);
    memcpy(wa, array, length * sizeof *wa);

    while(!are_same(wa, length)) {
        // find the largest value in wa:
        int large = largest_value(wa, length);

        for(size_t i = 0; i < length; ++i) {
            // make wa[i] at least as big as `large`
            wa[i] += ((large - wa[i] + array[i] - 1) / array[i]) * array[i];
        }
    }

    int lcm = wa[0];
    free(wa);
    return lcm;
}

演示

您也可以跳过调用，只检查自上次迭代以来最大值是否发生了变化。如果没有，则所有数字都相同：all_same

int calculate_lcm(const int array[], size_t length) {
    int* wa = malloc(length * sizeof *wa);
    if (!wa) exit(1);
    memcpy(wa, array, length * sizeof *wa);

    for(int largest = array[0];;) {
        int newlargest = largest_value(wa, length);
        if(newlargest == largest) break;
        largest = newlargest;

        for (size_t i = 0; i < length; ++i) {
            wa[i] += ((largest - wa[i] + array[i] - 1) / array[i]) * array[i];
        }
    }

    int lcm = wa[0];
    free(wa);
    return lcm;
}

演示