剑指offer-n个骰子的点数

一、题意

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

二、解法一

现在考虑如何统计每一个点数出现的次数。要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有一个，另一堆有n-1个。单独的那一个骰子可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的 n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆，第一堆只有一个，第二堆有n-2个。我们把上一轮单独骰子的点数和这一轮单独骰子的点数相加，再和n-2个骰子来计算点数和。分析到这里，我们不难发现这是一种递归的思路，递归结束的条件就是最后只剩下一个骰子。

三、解法二

可以换一个思路来解决这个问题，我们可以考虑用两个数组来存储骰子点数的每一个总数出现的次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。在下一轮循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一次循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的次数的总和，所以把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6之和。

四、代码实现

>folded main.go

package main

import (
	"fmt"
	"math"
)

// 动态规划解法
const gmax = 6

func printProbability(n int) (result []float64) {
	var (
		i, j, k 	int
		total 		= math.Pow(float64(gmax), float64(n))
		flag 		= 0
		probabilities 	= make([][]int, 2)
	)
	probabilities[0] = make([]int, n*gmax+1)
	probabilities[1] = make([]int, n*gmax+1)

	// 初始掷第一枚骰子
	for i = 1; i <= gmax; i++{
		probabilities[flag][i] = 1
	}

	for k = 2; k <= n; k++ {
		for i = 0; i < k; i++ {
			probabilities[1-flag][i] = 0
		}

		for i = k; i <= k*gmax; i++ { // 使用i个骰子最小点数为i，最大点数6*i
			probabilities[1-flag][i] = 0
			for j = 1; i-j >= 0 && j <= gmax; j++ { // 第j个骰子的6种情况
				probabilities[1-flag][i] += probabilities[flag][i-j]
			}
		}
		flag = 1 - flag
	}

	result = make([]float64, gmax*n-n+1)
	for i = n; i <= gmax*n; i++ {
		result[i-n] = float64(probabilities[flag][i]) / total
	}

	return result
}

func main() {
	result := printProbability(3)
	for i := 0; i < len(result); i++ {
		fmt.Println(result[i])
	}
}

// 输出如下：
--------------------------------
0.004629629629629629
0.013888888888888888
0.027777777777777776
0.046296296296296294
0.06944444444444445
0.09722222222222222
0.11574074074074074
0.125
0.125
0.11574074074074074
0.09722222222222222
0.06944444444444445
0.046296296296296294
0.027777777777777776
0.013888888888888888
0.004629629629629629
--------------------------------
Process finished with exit code 0

参考文章:
1、面试题60n个骰子的点数