小易参加了一个骰子游戏,这个游戏需要同时投掷n个骰子,每个骰子都是一个印有数字1~6的均匀正方体。
小易同时投掷出这n个骰子,如果这n个骰子向上面的数字之和大于等于x,小易就会获得游戏奖励。
小易想让你帮他算算他获得奖励的概率有多大。
输入包括两个正整数n和x(1 ≤ n < 25, 1 ≤ x < 150),分别表示骰子的个数和可以获得奖励的最小数字和。
输出小易可以获得奖励的概率。 如果概率为1,输出1,如果概率为0,输出0,其他以最简分数(x/y)的形式输出。
3 9
20/27
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); int x = Integer.parseInt(params[1]); long all = (long)Math.pow(6, n); long[][] dp = new long[n + 1][151]; for(int i = 0; i <= n; i++){ for(int j = 0; j <= 150; j++){ dp[i][j] = -1; } } long events = dfs(n, x, 0, dp); long g = gcd(all, events); System.out.println(events == 0? 0: all == events? 1: (events / g) + "/" + (all / g)); } private static long dfs(int rest, int x, int point, long[][] dp) { if(rest == 0){ return point >= x? 1: 0; }else{ if(dp[rest][point] > -1){ return dp[rest][point]; } long ways = 0L; for(int i = 1; i <= 6; i++){ ways += dfs(rest - 1, x, point + i, dp); } dp[rest][point] = ways; return ways; } } private static long gcd(long a, long b) { return b == 0? a: gcd(b, a % b); } }注意:得到有效的方案数之后,需要与事件的总数求最大公约数,以便约分得到概率表达的最简真分式,且分子为0时直接输出0,分子等于分母时直接输出1。
import java.util.Arrays;
import java.util.Scanner;
public class Solution43 {
/**
* 网易笔试https://www.nowcoder.com/questionTerminal/4ac62a94e4ba49df86a66eb7c44fa96a
n个骰子的和有 6*n-n+1 最大6n 最小n
用f[n][m]表示投第n个筛子时点数之和为m的个数
投第n个筛子的点数之和只与投第n-1个筛子有关
f(n,m)=f(n-1,m-1)+f(n-1,m-2)+f(n-1,m-2)+f(n-1,m-3)+f(n-1,m-4)+f(n-1,m-5)+f(n-1,m-6)
表示本轮点数之和为n的次数等于上一轮点数和为n-1,n-2,n-3,n-4,n-5,n-6出现的次数之和
例如:
f(2,6)=f(1,5)+f(1,4)+f(1,3)+f(1,2)+f(1,1)+f(1,0)=1+1+1+1+1=5
f(3,6)=f(2,5)+f(2,4)+f(2,3)+f(2,2)+f(2,1)+f(2,0)
如果有空间限制 其实只需要用两个数组 一个表示上次的和的次数,一个用来表示本次和出现的次数,用flag区分本次和上次
注意: 由于6的n次方可能会超过int的表示范围,所以 f和 count都要用long
* n 筛子的个数
* gMax 每个筛子的最大点数
* 返回值为 所有点数和出现的次数
*/
static int gMax=6;
long[] probabilities(int n){
int maxSum=gMax*n;
long[][] f=new long[n+1][maxSum+1];
int flag=0;
//初始化第1个筛子和的次数
for (int i = 1; i <=gMax ; i++) {
f[1][i]=1;
}
// System.out.println(Arrays.toString(f[1]));
//求投第i个筛子和的次数
for (int i = 2; i <=n ; i++) {
for (int j = 1; j <=maxSum ; j++) {
for (int k = 1; k <=gMax ; k++) {
if (j-k>0){
f[i][j]+=f[i-1][j-k];
}else {
//j-k<=0时后面的不用再加,都是0
break;
}
}
}
// System.out.println(Arrays.toString(f[i]));
}
return f[n];
}
/**
* 辗转相除法:
目的:求两个整数的最大公约数
最大公约数:能同时被两个整数整除的最大公约数
原理:
最大公约数 = 小数 与 (大数%小数) 的最大公约数
利用这条原理,反复执行,直到 大数%小数 = 0,此时较小的数就是原来两数的最大公约数
* @param x
* @param y
* @return
*/
public static long gcd(long x, long y){ // 这个是运用辗转相除法求 两个数的 最大公约数 看不懂可以百度 // 下
if(y == 0)
return x;
else
return gcd(y,x%y);
}
public static void main(String[] args) {
Solution43 solution43=new Solution43();
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int x=scanner.nextInt();
long[] f=solution43.probabilities(n);
long count=0;
for (int i =x ; i <=6*n ; i++) {
count+=f[i];
}
long max=(long)Math.pow(gMax,n); //最多gMax的n次方种情况
long g=gcd(count,max);
if (count==0)
System.out.println(0);
else if (count==max)
System.out.println(1);
else
System.out.println(count/g+"/"+max/g);
}
}