Study Plan For Algorithms - Part36
1. n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
方法一：
def dicesProbability(n):maxValue = 6if n < 1:return []maxSum = maxValue * nres = [0] * (maxSum - n + 1)def helper(n, res):for i in range(1, maxValue + 1):computedSum(n, n, i, res)def computedSum(origin, current, sum, res):if current == 1:res[sum - origin] += 1else:for i in range(1, maxValue + 1):computedSum(origin, current - 1, i + sum, res)helper(n, res)total = 6 ** nratio = [res[i] / total for i in range(len(res))]return ratio
方法二：
def dicesProbability(n):maxValue = 6if n < 1:return []sumArr = [[0] * (maxValue * n + 1), [0] * (maxValue * n + 1)]temp = 0for i in range(1, maxValue + 1):sumArr[temp][i] = 1for j in range(2, n + 1):for k in range(j):sumArr[1 - temp][k] = 0for m in range(j, maxValue * j + 1):sumArr[1 - temp][m] = 0for l in range(1, min(m + 1, maxValue + 1)):sumArr[1 - temp][m] += sumArr[temp][m - l]temp = 1 - temptotal = 6 ** nratio = [sumArr[temp][i] / total for i in range(n, maxValue * n + 1)]return ratio
方法三：
def dicesProbability(n):ratio = [1/6] * 6for i in range(2, n + 1):temp = [0] * (5 * i + 1)for j in range(len(ratio)):for l in range(6):temp[j + l] += ratio[j] / 6ratio = tempreturn ratio