蓝桥杯 算法提高 概率计算（Java解题）

问题描述 　　生成n个∈[a,b]的随机整数，输出它们的和为x的概率。 输入格式 　　一行输入四个整数依次为n，a，b，x，用空格分隔。 输出格式 　　输出一行包含一个小数位和为x的概率，小数点后保留四位小数 样例输入 2 1 3 4 样例输出 0.3333 数据规模和约定 　　对于50%的数据，n≤5.　　对于100%的数据，n≤100,b≤100.

【解析】：此题使用动态规划思想求解，dp[i][j]表示生成i个数和为j的概率。则此题最终求解的为dp[n][x]。

dp[i][k]可以想成i-1个数和为k-j时再加j。只有当k>j时才成立即k-j>0。

每个数出现的概率为1/（b-a+1）。

【代码】：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); int x = sc.nextInt(); double dp[][] = new double[101][10000]; for (int j = a; j <= b; j++) { dp[1][j] = (1.0 / (b - a + 1));// 生成1个数字和为a到b之间的概率为1/（b-a+1) } for (int i = 2; i <= n; i++) { for (int j = a; j <= b; j++) { for (int k = 1; k <= x; k++) { if (k - j > 0) dp[i][k] += dp[i - 1][k - j] * 1.0 / (b - a + 1);// 生成i个数和为k的概率 } } } System.out.printf("%.4f", dp[n][x]); } }