1

TLDR:数値の可変配列に対して可能な限り最小の最小公倍数を返すアルゴリズムを探しています:

  • 数字の一つ
  • 私の配列のサイズ
  • 数値に可能な最小値と最大値

私は音楽アプリを使用していますが、アルゴリズムの問​​題があります: 異なるリズム (それぞれ異なるステップ数) を混合する場合、結果がループするために結果のステップ数を計算する必要があります。これは、最小公倍数の計算を使用して簡単に実行できます。さまざまな長さをすべて段階的に含む lengths 配列があると仮定しましょう

var lengths = [4,5,6,8]

//greatest common denominator
function gcd(a,b){
  var t,b,a
  while(b != 0){
    t = b;
    b = a%b
    a=t
  }
  return a;
}
//least common multiplier
function lcm(a,b){
  return a*b/gcd(a,b)
}
function getLoopLength(arr{
  var result = 1;
  for(var i = 0;i<arr.length;i++)
    result = lcm(result,arr[i])
  return m
}


getLoopLength(lengths)
==> 120
// superimposing 4 rhythm with length 4,5,6 and 8 will result in a a rhythms that loops in 120 steps

次に、次の仮説の最小ステップ数を計算する関数が必要です。

  • 可能なステップの長さは制限されています (私の場合は 2 から 11 の間で、変更される可能性があります)。
  • ステップの長さの値はすべて異なっていなければなりません
  • 1 つの長さの値が既知です (変数になります)
  • lengths 配列のサイズはさまざまです (私の場合は 1 から 4 の間で、変更されません)。

だから私が求めているのは、次のような関数です。

var minPossibleLength(knownLength, lengthsSize){
  ...
  return min
}

たとえば、minPossibleLength(4,4) は 24 を返す必要があります (長さが [2, 4 ,8,3] または [2, 4 ,8,6] の場合)

今、私はそれを力ずくで試し、すべての可能な長さの組み合わせをループして最小の lcm を見つけました。

どうも

4

1 に答える 1

1

の次のアルゴリズムはminPossibleLength(4,4)、24 よりも優れた解を見つけます: の最小公倍数[4, 2, 3, 6]は12です。

var lengths = [4,5,6,8]

    //greatest common denominator
    function gcd(a,b){
      var t,b,a
      while(b != 0){
        t = b;
        b = a%b
        a=t
      }
      return a;
    }
    //least common multiplier
    function lcm(a,b){
      return a*b/gcd(a,b)
    }
    function getLoopLength(arr, length){
      var result = 1;
      for(var i = 0;i<arr.length && i<length;i++)
        result = lcm(result,arr[i])
      return result
    }

    var minBound = 2;
    var maxBound = 11;

    function minPossibleLength(knownLength, lengthsSize) {      
      var min = 27720; // Maximum for bound range [2..11]
      var newmin; // Newly computed minimum.
      if (lengthsSize == 1)
        return knownLength;
      lengths[0] = knownLength;
      for(var i = minBound; i<=maxBound; i++) {
        if (i != knownLength) {
          lengths[1] = i;
          for(var j = (lengthsSize>2?i+1:maxBound); j<=maxBound; j++) {
            if (lengthsSize<3 || (i != j && j!= knownLength)) {
              lengths[2] = j;
              for(var k = (lengthsSize>3?j+1:maxBound); k<=maxBound; k++) {
                if (lengthsSize<4 || (i != k && j != k && k!= knownLength)) {
                  lengths[3] = k;
                  newmin = getLoopLength(lengths, lengthsSize)
                  if (newmin < min) {
                    min = newmin;
                    console.log('Minimum lcm so far for (['+knownLength+', '+i+(lengthsSize>2?', '+j+(lengthsSize>3?', '+k:''):'')+']) = '+min); 
                  }
                }
              }
            }
          }
        }
      }
      return min;
    }

    minPossibleLength(4,4);

于 2016-07-13T15:54:40.473 に答える