首页 > 代码库 > 剑指Offer面试题43(Java版):n个骰子的点数
剑指Offer面试题43(Java版):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的骰子出现的次数应该等于上一次循环中骰子点数和为n-1,n-2,n-3,n-4,n-5的次数之和,所以我们把还有一个数组的第n个数字设为前一个数组相应的第n-1。n-2。n-3,n-4,n-5
基于这个思路实现代码例如以下:
/** * n个骰子的点数 */ package swordForOffer; /** * @author JInShuangQi * * 2015年8月11日 */ public class E43DicsProbability { /* * 把n个骰子仍在地上,全部骰子朝上一面的点数之和为s,输入n,打印出s的全部可能出现的概率 */ public void printProbability(int number) { if (number < 1) return; int g_maxValue = http://www.mamicode.com/6;>
剑指Offer面试题43(Java版):n个骰子的点数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。