当前位置:首页 > 开发 > 编程语言 > Java > 正文

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

发表于: 2012-02-28   作者:bylijinnan   来源:转载   浏览:
摘要: public class ProbabilityOfDice { /** * Q67 n个骰子的点数 * 把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,打印出S的所有可能的值出现的概率。 * 在以下求解过程中,我们把骰子看作是有序的。 * 例如当n=2时,我们认为(1,2)和(2,1)是两种不同的情况 */ private stati

public class ProbabilityOfDice {

	/**
	 * Q67 n个骰子的点数
	 * 把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,打印出S的所有可能的值出现的概率。
	 * 在以下求解过程中,我们把骰子看作是有序的。
	 * 例如当n=2时,我们认为(1,2)和(2,1)是两种不同的情况
	 */
	private static int MAX=6;
	public static void main(String[] args) {
		int n=2;
		printProbabilityOfDice(n);//solution 1,use recursion
		System.out.println("============");
		printProbabilityOfDice2(n);//solution 2,use DP
	}

	public static void printProbabilityOfDice(int n){
		if(n<1){
			return;
		}
		double total=Math.pow(MAX, n); 
		int len=n*MAX-n*1+1;//the sum of n dices is from n*1 to n*MAX
		int[] times=new int[len];
		for(int i=1;i<=MAX;i++){//initial the first dice.
			probabilityOfDice(n,i,n,0,times);//count the times of each possible sum
		}
		for(int i=0;i<len;i++){
			System.out.println((i+n)+","+times[i]+"/"+total);
		}
		
	}
	public static void probabilityOfDice(int n,int curDiceValue,int numOfDices,int curSum,int[] times){
		if(numOfDices==1){
			int sum=curSum+curDiceValue;
			times[sum-n]++;//n*1 to n*MAX <---> 0 to len
		}else{
			int sum=curSum+curDiceValue;
			for(int i=1;i<=MAX;i++){
				probabilityOfDice(n,i,numOfDices-1,sum,times);
			}
		}
	}
	
	/*
有k-1个骰子时,再增加一个骰子,这个骰子的点数只可能为1、2、3、4、5或6。那k个骰子得到点数和为n的情况有:
(k-1,n-1):第k个骰子投了点数1
(k-1,n-2):第k个骰子投了点数2
(k-1,n-3):第k个骰子投了点数3
....
(k-1,n-6):第k个骰子投了点数6
在k-1个骰子的基础上,再增加一个骰子出现点数和为n的结果只有这6种情况!
所以:f(k,n)=f(k-1,n-1)+f(k-1,n-2)+f(k-1,n-3)+f(k-1,n-4)+f(k-1,n-5)+f(k-1,n-6)
初始化:有1个骰子,f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。
	 */
	public static void printProbabilityOfDice2(int n){
		if(n<1){
			return;
		}
		double total=Math.pow(MAX, n); 
		int maxSum=n*MAX;
		double[][] f=new double[n+1][n*MAX+1];
		for(int i=1;i<=MAX;i++){
			f[1][i]=1;
		}
		for(int k=2;k<=n;k++){
			for(int sum=n;sum<=maxSum;sum++){
				for(int i=1;sum-i>=1&&i<=MAX;i++){
					f[k][sum]+=f[k-1][sum-i];
				}
			}
		}
		
		for(int sum=n;sum<=maxSum;sum++){
			System.out.println(sum+","+f[n][sum]+"/"+total);
		}
	}
}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
之前 javaeye 网站上有人写过 3颗骰子能掷出多少种结果 的一道面试题,用了面向对象的思考方式,后
/* * Copyright (c) 2013, 烟台大学计算机学院 * All rights reserved. * 作 者: 马广明 * 完成日
随机生成和为S的N个正整数——投影法 随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效
4 骰子
#include <iostream> #include <cstdlib> #include <ctime> using namespace std
输入N个数,输出所有可能的排列组合 一行代码一行泪。。。手都被发热的笔记本烤的不舒服了。。。。6
大家知道,微信聊天里可以玩猜拳和骰子点数,那么要是可以随意控制游戏的结果,是不是更有趣呢?下
地址:http://blog.csdn.net/morewindows/article/category/859207 随机生成和为S的N个正整数有很多
随机生成和为S的N个正整数——投影法 随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效
/* * Copyright (c) 2013, 烟台大学计算机学院 * All rights reserved. * 作 者:申玉迪 * 完成日期
#include <iostream> #include <stack> #include <math.h> using namespace std;
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号