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個整數

回答

相關問題