不同数量的相关嵌套 for 循环

Question

我正在尝试通过掷 n 个骰子来确定所有可能的总和，其中 n 在编译时未知。

对于两个骰子，解决方案很简单，只需遍历两个骰子并将每个可能的边相加即可。如果传入 2 个 6 面骰子，则排序结果为：[2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7, 7,7,7,7,8,8,8,8,8,9,9,9,9,10,10,10,11,11,12]

我试图将这个解决方案扩展到任何 n 个骰子，但我意识到我需要 n 个 for 循环。

for(let i = 0; i < numDice; i++)
{
    dice.push(sides); 
}

for(let i = 0; i < numSides; i++)
{
    for(let j = 1; j < dice.length; j++)
    {
        for(let k = 0; k < numSides; k++)
        {
            results.add(dice[0][i] + dice[j][k]);
        }
    }
}

我还尝试了下面第一个问题建议的基于递归的方法。我相信它会循环正确的次数，但我不知道如何在不引入更多循环的情况下定义求和函数。

function doCallMany(numDice, numSides, sumFunc)
{
    if(numDice == 0) 
    {
        sumfunc(numDice, numSides) //?
    }
    else
    {
        for(let i = 0; i < numSides; i++)
        {
            doCallMany(numDice--, numSides, sumFunc)
        }
    }
}

我看了类似的问题 here and here 但他们没有回答我的问题。第一个不是因为我需要在循环中执行的操作不是独立的。第二个接近，但答案依赖于 Python-特定答案。

Answer 1

我建议你使用回溯法。它允许您改变要执行的循环数。您甚至可以执行随机数的循环，因为循环数可以保存在变量中。

Answer 2

关于解决方案复杂性的评论是正确的。它很快变大。话虽如此，为了解决您最初的问题，您可以使用一个相当简单的递归函数来处理小输入。基本上，您从一组骰子开始，弹出一个骰子，将其添加到一个总和中，然后对该总和和数组的其余部分进行递归。

例如：

function sums(dice, sum = 0, ans = []) {
  if (dice.length === 0) ans.push(sum) // edge case, no more dice
  else {
    let d = dice[0]
    for (let i = 1; i <= d; i++) {
      sums(dice.slice(1), sum + i, ans) // recurse with remaining dice
    }
    return ans
  }
}

// two six-sided dice
let ans = sums([6, 6]) 
console.log(JSON.stringify(ans.sort((a, b) => a - b)))

// three three-sided dice
ans = sums([3, 3, 3]) 
console.log(JSON.stringify(ans.sort((a, b) => a - b)))

不同数量的相关嵌套 for 循环

Varying number of related nested for loops

javascript

algorithm

nested-loops