M的计算在LCM N个整数

的阵列的连续编号我碰到这个问题here。这是今年早些时候举办的编程比赛。
这里是总结：
给定N个整数的数组，找到所有M个连续整数的LCM。
对于例如M的计算在LCM N个整数

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

其实有一个解决方案草图here，但我不明白的动态规划部分。
所以，如果有人能与一些例子中，相同的解决方案阐述这将是巨大的。
一个新的，易于理解的解决方案也可以理解。

来源

2012-03-05 dharm0us

该草图似乎有三个部分：1）一种方法，2）开始的部分“另一种方法将分解每个A [i] ...”，3）最后一部分，“另一种方法许多参赛者使用的是......“。你需要哪些部分帮助？ – Beta 2012-03-05 05:35:17

@Beta我想要动态规划部分的帮助。 – dharm0us 2012-03-05 06:39:42

@Carl我觉得这是找到所有的M个连续号码的LCM不使用DP或任何其他快捷方式最简单的解决方案。这是O（MN）时间。 – dharm0us 2012-03-05 06:41:16

我无法再访问解决方案（也许链接已损坏？），但这里是我会做的：我会让我的程序像金字塔一样工作。在最下面的一行中，我将使用给定数字的数组。在上面的每一行上，我将有一个数组，其中一个字段小于下面的数组。它会从下面的数组中存储两个值的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-31 14:01:06 Skrodde

M的计算在LCM N个整数

回答

相关问题