首页 > 代码库 > 算法笔记_155:算法提高 概率计算(Java)

算法笔记_155:算法提高 概率计算(Java)

目录

1 问题描述

2 解决方案

 


1 问题描述

 

问题描述

 

  生成n个∈[a,b]的随机整数,输出它们的和为x的概率。

 

输入格式

 

  一行输入四个整数依次为n,a,b,x,用空格分隔。

 

输出格式

 

  输出一行包含一个小数位和为x的概率,小数点后保留四位小数

 

样例输入

 

2 1 3 4

 

样例输出

 

0.3333

 

数据规模和约定

 

  对于50%的数据,n≤5.
  对于100%的数据,n≤100,b≤100.

 

 

 


2 解决方案

下面代码在系统中运行评分为90分,第五组数据无法通过,我用同版本的C代码运行(PS:具体参见文末参考资料),却可以通过,具体无法通过的原因,有可能是下面代码原因,如有同学Java版代码能够通过,还望分享一下代码哦~

技术分享

 

具体代码如下:

import java.util.Scanner;

public class Main {
    public static int n, a, b, x;
    
    public void getResult() {
        double[][] dp = new double[n + 1][x + 1];
        for(int j = a;j <= b;j++)
            dp[1][j] = 1.0 / (b - a + 1);
        for(int i = 2;i <= n;i++) {
            for(int k = a;k <= b;k++) {
                for(int j = a;j <= x;j++) {
                    if(j - k >= 0)
                        dp[i][j] += dp[i - 1][j - k] / (b - a + 1);
                }
            }
        }
        System.out.printf("%.4f",dp[n][x]);
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        a = in.nextInt();
        b = in.nextInt();
        x = in.nextInt();
        test.getResult();
    }
}

 

 

 

参考资料:

   1. 算法提高 概率计算

 

算法笔记_155:算法提高 概率计算(Java)