1

我在这里遇到了这个问题。这是今年早些时候举办的一场编程比赛。
这是摘要：
给定一个包含 N 个整数的数组，找到所有连续 M 个整数的 LCM。
例如 

Array = [3,5,6,4,8] (hence N = 5)  
M = 3

输出 ： 

LCM(3,5,6) = 30  
LCM(5,6,4) = 60  
LCM(6,4,8) = 24

实际上这里有一个解决方案草图，但我无法理解动态编程部分。
因此，如果有人可以通过一些示例详细说明相同的解决方案，那就太好了。
一个新的、易于理解的解决方案也将受到赞赏。

4

1 回答 1

0

我无法再访问该解决方案（也许链接已损坏？），但这是我要做的：我会让我的程序像金字塔一样工作。在最低行，我将拥有具有给定数字的数组。在上面的每一行上，我都会有一个比下面的数组少一个字段的数组。它将存储下面数组中两个值的 LCM。

[   30    ]
[ 15,  30 ]
[3,  5,  6]

通过这种方式，您可以使用递归函数，并且必须构建金字塔的 M-1 层。这是一个伪代码实现：

rekursivePyramid (Integer[] numbers, Integer height) {
    if (height == 0) return numbers;
    else {
        newNumbers = Integer[numbers.size() - 1];
        for (i=0; i<newNumbers.size(); i++) {
            newNumbers[i] = LCM ( numbers[i], numbers[i+1]);
        }
        return rekursivePyramid( newNumbers, height-1);
    }
}

这将为您提供一个数组，您可以在其中找到第一个字段中前 M 个数字的 LCM，第二个字段中从第二个到第 M+1 个数字的 LCM，等等。

于 2012-07-31T14:01:06.763 回答