算法分析:

算法1.基于递归求色子点数,时间效率不高
现在我们考虑如何统计每一个点数出现的次数。要向求出n个骰子的点数和,可以先把n个骰子分为两堆:第一堆只有一个,另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆,第一堆只有一个,第二堆有n-2个。我们把上一轮哪个单独骰子的点数和这一轮单独骰子的点数相加,再和n-2个骰子来计算点数和。分析到这里,我们不难发现这是一种递归的思路,递归结束的条件就是最后只剩下一个骰子。我们可以定义一个长度为6n-n+1的数组,和为s的点数出现的次数保存到数组的第s-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-6之和。
/**************************************************************
* Copyright (c) 2016,
* All rights reserved.
* 版 本 号:v1.0
* 题目描述:n个色子的点数
* 把n个色子仍在地上,所有色子朝上一面的点数之和为s,输入n,打印出s的所有可能值出现的概率
* 输入描述:请输入色子个数:2
* 请输入色子最大值:6
* 程序输出: 算法一的输出为:
* 0.0278 0.0556 0.0833 0.1111 0.1389 0.1667 0.1389 0.1111 0.0833 0.0556 0.0278
* 算法二输出为:
* 点数为2的概率为:0.0278 点数为3的概率为:0.0556 点数为4的概率为:0.0833 点数为5的概率为:0.1111
* 点数为6的概率为:0.1389 点数为7的概率为:0.1667 点数为8的概率为:0.1389 点数为9的概率为:0.1111
* 点数为10的概率为:0.0833 点数为11的概率为:0.0556 点数为12的概率为:0.0278
*
* 问题分析: 无
* 算法描述: 现在我们考虑如何统计每一个点数出现的次数。要向求出n个骰子的点数和,可以先把n个骰子分为两堆:
* 第一堆只有一个,另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和
* 剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆,第一堆只有一个,第二堆有n-2个。
* 我们把上一轮哪个单独骰子的点数和这一轮单独骰子的点数相加,再和n-2个骰子来计算点数和。分析到这里,
* 我们不难发现这是一种递归的思路,递归结束的条件就是最后只剩下一个骰子。
* 我们可以定义一个长度为6n-n+1的数组,和为s的点数出现的次数保存到数组的第s-n个元素里。
* 完成日期:2016-09-26
***************************************************************/
package org.marsguo.offerproject43; import java.util.Scanner; class SolutionMethod1{
/**
* 基于递归求解
*
* @param number 色子个数
* @param maxvalue 色子的最大值
*/
public void printProbFunction(int number,int maxvalue){
if(number < 1 || maxvalue < 1){
return;
}
System.out.println("算法一的输出为:");
int maxSum = number*maxvalue; //所有色子点数和的最大值
int[] probabilities = new int[maxSum - number +1]; //probabilities 不同色子数出现次数的计数数组。
probalityFunction(number,probabilities,maxvalue); double total = 1;
for(int i = 0; i < number; i++){
total *= maxvalue; //total表示所有可能的组合种类
System.out.println("total=" + total);
} for(int i = number; i <=maxSum; i++){
double ratio = probabilities[i-number]/total; //每个点数出现的概率
System.out.printf("%-8.4f",ratio);
//System.out.printf("点数为" + i + "的概率为:" +"%-8.4f",ratio);
}
System.out.println();
} /**
* @param number 色子个数
* @param probabilities 不同色子数出现次数的计数数组
* @param max 色子的最大值
*/
private void probalityFunction(int number,int[] probabilities,int maxvalue){
for(int i = 1; i <= maxvalue; i++){
probalityFunction(number, number,i,probabilities, maxvalue);
}
}
/**
* @param original 总的色子数
* @param current 剩余要处理的色子数
* @param sum 前面已经处理的色子数和
* @param probabilities 不同色子数出现次数的计数数组
* @param maxvalue 色子的最大值
*/
private void probalityFunction(int original, int current, int sum,
int[] probabilities, int maxvalue) {
// TODO Auto-generated method stub
if(current == 1){
probabilities[sum - original]++;
}
else{
for(int i = 1; i <= maxvalue; i++){
probalityFunction(original,current - 1,i + sum, probabilities,maxvalue);
}
}
}
}
class SolutionMethod2{
/**
* 基于循环求解
* @param number 色子个数
* @param max 色子的最大值
*/
public void printProbFunction2(int number,int maxvalue){
if(number < 1 || maxvalue < 1){
return;
}
System.out.println("算法二输出为:");
int[][] probarry = new int[2][maxvalue*number + 1];
//数据初始化
for(int i = 0; i< maxvalue*number + 1; i++){
probarry[0][i] = 0;
probarry[1][i] = 0;
} int flag = 0; // 标记当前要使用的是第0个数组还是第1个数组 // 抛出一个骰子时出现的各种情况
for(int i = 1;i <= maxvalue; i++){
probarry[flag][i] = 1;
}
// 抛出其它骰子时的情况
for(int k = 2; k <= number; k++){
// 如果抛出了k个骰子,那么和为[0, k-1]的出现次数为0
for(int i = 0; i < k; i++){
probarry[1-flag][i] = 0;
}
// 抛出k个骰子,所有和的可能
for(int i = k;i <= maxvalue*k;i++){
probarry[1-flag][i] = 0;
// 每个骰子的出现的所有可能的点数
for(int j = 1;j <= i&& j <=maxvalue;j++){
// 统计出和为i的点数出现的次数
probarry[1-flag][i] +=probarry[flag][i-j];
}
}
} flag = 1-flag; double total = 1;
for(int i = 0; i < number; i++){
total *= maxvalue;
}
int maxSum = number*maxvalue;
for(int i = number; i <= maxSum; i++){
double ratio = probarry[flag][i]/total;
System.out.printf("点数为" + i + "的概率为:" +"%-8.4f",ratio);
}
System.out.println();
}
}
public class PrintProbability {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
System.out.println("请输入色子个数:");
int number = scanner.nextInt();
System.out.println("请输入色子最大值:");
int maxvalue = scanner.nextInt();
scanner.close(); SolutionMethod1 solution1 = new SolutionMethod1();
solution1.printProbFunction(number, maxvalue); SolutionMethod2 solution2 = new SolutionMethod2();
solution2.printProbFunction2(number, maxvalue);
}
}
05-11 20:54