Swift学习——n个骰子的总和

概述参考自：http://www.cnblogs.com/python27/archive/2011/11/26/2263332.html （作者原话）题目：把n个骰子仍在地上，所有骰子的点数和为s。输入n，打印s所有可能取值的概率。 分析1：容易知道，有n个骰子的话，s的最小取值为n（全为1），最大取值为6n（全为6）。 如果只有1个骰子，那么很简单，s取1，2，3，4，5，6的情况数均为1，概率为

参考自：http://www.cnblogs.com/python27/archive/2011/11/26/2263332.html
（作者原话）题目：把n个骰子仍在地上，所有骰子的点数和为s。输入n，打印s所有可能取值的概率。

分析1：容易知道，有n个骰子的话，s的最小取值为n（全为1），最大取值为6n（全为6）。

如果只有1个骰子，那么很简单，s取1，2，3，4，5，6的情况数均为1，概率为1/6；设想有n个骰子，出现和为s，我们可以这样考虑，如果第一个骰子有6中情况，取1，2，3，4，5，6；那么剩下的n-1个骰子的和则分别取s-1，s-2,s-3,s-4,s-5,s-6，我们将所有这些情况相加，就可以得出总的情况数。看出了吗？亲，这是什么问题？对了，还是递归问题，根据以上分析我们不难写出如下的递归公式：

（作者原话）对公式的说明：（1）f(s,n)表示，有n个骰子，出现和为s的情况总数；（2）对于公式第二行的解释；如果有一个骰子，那么点数为8或者0的情况数，我们记为0，这样是为了在计算递归时更为方便所作的处理；例如有公式可知f(8,2)=f(7,1)+f(6,1)+f(5,1)+f(4,1)+f(3,1)+f(2,1)，如果我们规定了f(7,1)=0那么计算会方便很多。

有了上面的分析，我们可以写出如下代码：

var diceMaxValue:Int = 6//计算给定diceNumber个骰子，出现和为dicetotalSum的所有可能情况的总数//int fun(int dicetotalSum,int diceNumber)func mainFun(dicetotalSum:Int,diceNumber:Int)->Int{    //骰子数少于1，错误    if diceNumber < 1 {        return 0    }    //骰子数等于1，如果超出1~6范围便错误，未超出则是1    if diceNumber == 1 {        if (dicetotalSum >= diceNumber && dicetotalSum <= diceMaxValue*diceNumber) {            return 1        }        else {            return 0        }    }    //n>1,采用递归    if diceNumber > 1 {        var sum:Int = 0        for var index:Int = 1; index <= diceMaxValue; ++index {            sum += mainFun(dicetotalSum-index,diceNumber-1)        }        return sum    }    return 0}//给定number个骰子，打印出现各种情况的概率func printSumProbabilityOfDice1(number:Int) {    if number < 1 {        return    }    var maxSum:Int = number * diceMaxValue    var pProbability:Array<float> = Array()    for index in number...maxSum {        pProbability.insert(float(mainFun(index,number)),atIndex: index-number)    }    var total:Int = Int(pow(float(diceMaxValue),float(number)))    for count in 0...maxSum-number {        pProbability[count] /= float(total) println("\(count+number)\t\(pProbability[count])") } }

（作者原话）分析2：和算法2中求解斐波那契数列的方法类似，递归的效率太差，我们可以正向来求解，假设我们有一个数组表示k-1个骰子中各点数的情况，令第s个分量表示和为s时情况总数，那么当有k个骰子是，其和为s时的情况总数，就是表示k-1骰子的数组中的s-1,s-2,s-6的和（分别令引入的第k个骰子的值分别取1，2，3，4，5，6即可，其实和分析1的思路差不太多）。根据这个思想，我们可以用两个数组交替表示数组k-1和数组k，于是我们有如下的代码：

func printSumProbabilityOfDice2(number:Int){    //创建并初始化一个二维数组    var pProbability:Array = Array(count: 2,repeatedValue: Array(count: number * diceMaxValue + 1,repeatedValue: Double(0)))    var flag:Int = 0    //将第一个数组下标为1~6的赋值为1    for index in 1...diceMaxValue {        pProbability[flag][index] = Double(1)    }    //骰子数k从2到n循环；对于每一k，s取值为[k,6k]，对于每一个s计算前一个数组    //的s-1,s-6;因为前一个数组的最小值为k-1,因为因而有s-j>=k-1；    for k in 2...number {        for s in k...diceMaxValue*k {            pProbability[1-flag][s] = 0            for var j = 1; j <= diceMaxValue && j <= s - k + 1; j++ {                pProbability[1-flag][s] += pProbability[flag][s-j]            }        }        flag = 1 - flag    }    var total:Double = pow(Double(diceMaxValue),Double(number))    for ss in number...number*diceMaxValue {        pProbability[flag][ss] /= total        println("\t\(pProbability[flag][ss])")    }}

（作者原话）最后分析：我们看到和【算法02】中提到的一样，虽然该算法的时间复杂度提高了很多，但是动态创建了两个数组，而且每一个的数组长度都没分析1中的长度多了一个n，因而还是以空间换时间的思想。好了，这个算法就到这，祝各位愉快！

参考文献：

【1】何海涛博客：http://zhedahht.blog.163.com/blog/static/254111742009101524946359/

【2】Wikipedia:http://en.wikipedia.org/wiki/Dice#Probability

【3】http://www.helium.com/items/1538174-how-to-calculate-probability-using-multiple-dice

总结

以上是内存溢出为你收集整理的Swift学习——n个骰子的总和全部内容，希望文章能够帮你解决Swift学习——n个骰子的总和所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。