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

もうソリューションにアクセスできません (リンクが壊れているのではないでしょうか?)。一番下の行には、指定された数値の配列があります。上の各行には、下の配列よりもフィールドが 1 つ少ない配列があります。以下の配列からの 2 つの値の 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、2 番目のフィールドに 2 番目から M+1 番目の数字までの LCM などがあります。

于 2012-07-31T14:01:06.763 に答える