我正在try 编写一个程序,它会迭代地更新数组中的最小数字,直到数组中的所有数字都相同(用于查找LCM的algorithm).我的程序似乎在无休止的循环中结束.我的猜测是,这是因为are_same()总是返回零,这是由get_min_index()和/或divisors[min_index] += divisors[min_index]中的某些东西引起的.我想知道这是否与我没有意识到的C语言的某些特性有关.有经验的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 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 min_index;

    do {
        min_index = get_min_index(divisors, length);
        divisors[min_index] += divisors[min_index];
    } while (are_same(divisors, length) == 0);

    printf("lcm=%d", divisors[0]);
    return(0);
}

推荐答案

您的are_same实现很好,而且做得很好.

找到最小值并将其相应的除数相加,然后搜索最小值并重复相同的操作的算法有一个缺陷,因为您将值加倍,而不是将除数加到它上面.

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

然后稍微修改一下,就会改为

  • 在数组中搜索largest值.
  • 用相应除数的倍数增加array中的所有条目,以便该值至少与最大值一样大.
  • 重复该操作,直到所有值都相等.

在本例中,我不关心最大的索引,因此它只返回最大的value:

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;
}

Demo

C++相关问答推荐

使用额外的公共参数自定义printf

在C23中使用_GENERIC实现带有右值的IS_POINTER(P)?

C语言编译阶段与翻译阶段的关系

为什么memcpy进入缓冲区和指向缓冲区的指针工作相同?

S的这种管道实施有什么问题吗?

如何编写一个for循环来计算C中各项的总和?

为什么Fread()函数会读取内容,然后光标会跳到随机位置?

用C++构建和使用DLL的困惑

使用Open62541向OPCUA服务器发送读请求时内存泄漏

具有正确标头的C struct 定义问题

在下面的C程序中,.Ap0是如何解释的?

哪个首选包含第三个库S头文件?#INCLUDE;文件名或#INCLUDE<;文件名&>?

无算术运算符和循环的二进制乘法

Malloc和对齐

Leet代码运行时错误:代码不会在Leet代码上编译,而是在其他编译器中编译,如netbeans和在线编译器

如何在Rust中处理C的longjmp情况?

无法将字符串文字分配给 C 中的字符数组

使用 c 中的 write() 函数将非 ASCII 字符写入标准输出

如何转义包含指令中的字符?

如何在C中以0x格式打印十六进制值