代码之家 › 专栏 › 技术社区 › TommyBs

根据骰子卷的x个输入生成一个特定的数字

dice algorithm javascript

2

TommyBs · 技术社区 · 7 年前

我正试图想出一个解决方案,我需要掷几个骰子(所有的骰子大小相同),然后得到一个指定的数字。如果我已经准备好了所有的验证以确保这些数字是有效的,并且理论上可以得到期望的结果,有人有一个好的算法来解决这个问题吗?注意,它应该是随机的,而不仅仅是一个直除。

一些实例

滚动3 d6并获得14->以便输出5、3、6或6、6、2

滚动4 d20并获得66->以便输出16、14、19、17

我需要一个通用函数,它可以接受任意大小的骰子、任意数量的骰子以及所需的结果。

我的初始尝试如下,尽管这不会产生所需的输出(您可以忽略 mod 现在,这也是允许修改的)。这个例子也没有验证所需的输出是可以实现的,但这不是问题的一部分。

let desired = 19
let mod = 0
let dm = desired - mod
let n = 5;// number of dice
let d = 6 // dice sides
let nums = []

for(i =0; i< n; i++) {
    nums.push(Math.round(Math.random() * Math.round(d)) + 1)
}

let sum = nums.reduce((acc,val) => acc + val)


nums = nums.map(a => Math.round((a/sum) * dm))

let diff = dm - (nums.reduce((acc,val) => acc + val))
function recursive(diff) {
    let ran = nums[Math.random() * Math.round(nums.length -1)]
    if(nums[ran] + diff > d || nums[ran] + diff < 1) {
        recursive(diff)
    } else {
        nums[ran] += diff
    }
}
while(diff != 0) {
    recursive(diff)
    diff += diff < 0 ? 1 : -1;
}

alert(nums)

2 回复 | 直到 7 年前

1

dfens 7 年前

Ruby中的解决方案:

def foo(count, dim, desired, results = [])
  return results if count == 0
  raise ArgumentError if count > desired
  raise ArgumentError if count * dim < desired

  max_roll = (dim <= desired - count) ? dim : desired - count + 1
  min_roll = [(desired - (count-1) * dim), 1].max
  roll = (rand(min_roll..max_roll))
  results << roll

  foo(count - 1, dim, desired - roll, results)

  results
end

puts foo(3, 6, 11).inspect
puts foo(2, 6, 11).inspect
puts foo(4, 4, 11).inspect

结果:

[3, 4, 4]
[5, 6]
[2, 3, 4, 2]

所以基本上是递归函数。每一步:

掷骰子(在允许的范围内,最小值/最大值)
调用相同的函数,但按骰子已消耗的数字减少计数,并按掷骰的值扩展结果数组

注意一件事:有了这种行为,结果的开头可能会有更大的数字。为了避免这种情况,只需在函数结束时对其结果进行无序处理。

2

marzelin 7 年前

递归的:

function foo(desired, rolls, sides, current) {
  if (rolls === 0) {
    return current.reduce((s, c) => s + c) === desired ? current : null;
  }
  
  const random = [];
  for (let i = 1; i <= sides; i++) {
    const randomIndex = Math.floor(Math.random() * (random.length + 1))
    random.splice(randomIndex, 0, i);
  }
  
  for (const n of random) {
    const result = foo(desired, rolls - 1, sides, [...current, n]);
    if (result) {
      return result;
    }
  }
}

console.log(foo(14, 3, 6, []))

非递归的:

function foo(desired, rolls, sides) {
  const stack = [[]];
  while (stack.length) {
    const current = stack.pop();    
    const random = [];
    for (let i = 1; i <= sides; i++) {
      const randomIndex = Math.floor(Math.random() * (random.length + 1));
      random.splice(randomIndex, 0, i);
    }
  
    for (const n of random) {
      if (current.length === rolls - 1) {
        if (current.reduce((s, c) => s + c + n) === desired) {
          return [...current, n];
        }
      } else {
        stack.push([...current, n]);
      }
    }
  }   
}

console.log(foo(14, 3, 6));

具有最小内存消耗的非递归:

function foo(desired, rolls, sides) {
  const currentIndexes = Array(rolls).fill(0);
  const randoms = Array.from({ length: rolls }, () => {
    const random = [];
    for (let i = 1; i <= sides; i++) {
      const randomIndex = Math.floor(Math.random() * (random.length + 1));
      random.splice(randomIndex, 0, i);
    }
    return random;
  })
  while (true) {
    if (currentIndexes.reduce((s, idx, i) => s + randoms[i][idx], 0) === desired) {
      return currentIndexes.map((idx, i) => randoms[i][idx]);
    }
    for (let i = currentIndexes.length - 1; i >= 0; i--) {
      if (currentIndexes[i] < sides - 1) {
        currentIndexes[i] += 1;
        break;
      }
      currentIndexes[i] = 0;
    }
  }
}

console.log(foo(14, 3, 6));

非递归解决方案,通过基于前一卷计算最后一卷来减少内存消耗和提高性能。

function foo(desired, rolls, sides) {
  const currentIndexes = Array(rolls - 1).fill(0);
  const randoms = Array.from({ length: rolls - 1 }, () => {
    const random = [];
    for (let i = 1; i <= sides; i++) {
      const randomIndex = Math.floor(Math.random() * (random.length + 1));
      random.splice(randomIndex, 0, i);
    }
    return random;
  })
  while (true) {
    const diff = desired - currentIndexes.reduce((s, idx, i) => s + randoms[i][idx], 0);
    if (diff > 0 && diff <= sides) {
      return [...currentIndexes.map((idx, i) => randoms[i][idx]), diff];
    }
    for (let i = currentIndexes.length - 1; i >= 0; i--) {
      if (currentIndexes[i] < sides - 1) {
        currentIndexes[i] += 1;
        break;
      }
      currentIndexes[i] = 0;
    }
  }
}

console.log(foo(66, 4, 20));