首页 > 程序开发 > 综合编程 > 其他综合 >

京东2017实习生真题 - 通过考试

2017-04-10

京东2017实习生真题 - 通过考试:小明同学要参加一场考试,考试一共有n道题目,小明必须做对至少60%的题目才能通过考试。考试结束后,小明估算出每题做对的概率,p1,p2,…,pn。你能帮他算出他通过考试的概率。

京东2017实习生真题 - 通过考试:小明同学要参加一场考试,考试一共有n道题目,小明必须做对至少60%的题目才能通过考试。考试结束后,小明估算出每题做对的概率,p1,p2,…,pn。你能帮他算出他通过考试的概率吗?

输入
输入第一行一个数n(1<=n<=100),表示题目的个数。第二行n个整数,p1,p2,…,pn。表示小明有pi%的概率做对第i题。(0<=pi<=100)
样例输入
4
50 50 50 50
输出
小明通过考试的概率,最后结果四舍五入,保留小数点后五位。
样例输出
0.31250
时间限制
C/C++语言:1000MS其它语言:3000MS
内存限制
C/C++语言:65536KB其它语言:589824KB

很遗憾,今天网上笔试没能做出来.
首先还是要明白,这道题是没法用穷举法做的,估算一下100道题,随机选60道,这个排列组合的数量级是非常恐怖的.

肿么办?
如果你数学学得好,就好办
递归一下就知道了

不然,就跟我一起凉拌吧!

假设小明考了3道题,每道题成功的概率如下:
答对概率: 0.4, 0.6, 0.5
答错概率: 0.6, 0.4, 0.5
二维表: r表示答对的题目个数,n表示总题目数量
比如:r为0,n为1,表示1道题,全错的概率;;小明如果只考第一题,则全错的概率为0.6
    r为0,n为3,表示3道题,全错的概率;;小明如果考了三道题,则全错的概率为0.12
r\n     0       1       2       3           记录
0       1       0.6     0.24    0.12        全错
1       0       0.4     0.52    0.38        对一道题
2       0       0       0.24    0.38        对两道题
3       0       0       0       0.12        对三道题
那么小明要想及格,3道得至少答对2道,所以概率为0.38+0.12=0.5
仔细想想,用了上面的二维表,假设小明考了100道题,我们只需要计算出101*101的二维表
那么如何计算二维表呢?
1.首先,全错的概率:错1*错2*....错n
那么表里的第一行,就求出来了.
2.你再仔细看看上面那张表,到底有什么规律,它的奥秘将会在下面揭示
数组p存储着答对的概率,dp存储的就是二维表
double[][] dp = new double[n + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i < n + 1; i++) {
    dp[i][0] = dp[i - 1][0] * (1 - p[i - 1]);
    for (int j = 1; j < n + 1; j++){
        dp[i][j] = dp[i - 1][j - 1]*p[i - 1]+dp[i-1][j]*(1- p[i - 1]);
    }
}
-------------------------看懂的到此为止,还需要往下面看的,编程或许不适合你
-----------------------------------------------------------------
没看懂吗?
我不信你看不懂,只是自己不太敢于亲自实操摸索,这也许就是中国应试教育下的最大弊端吧.
这样吧:
假设小明去参加考试,只有一道考题,小明答对概率为0.4
r\n     0       1   
0       1       0.6 
1       0       0.4 

假设小明去参加考试,只有两道考题,小明答对的概率分别为0.4,0.6
r\n     0       1       2       
0       1       0.6     0.24
1       0       0.4     0.52
2       0       0       0.24
他考了2道题,对了1道题的概率总是为:
考了1道题,对了0道题的概率  乘以  第2道题对的概率    再加上
考了1道题,对了1道题的概率  乘以  第2道题错的概率!!!!!!!!!!!!

假设小明去参加考试,只有两道考题,小明答对的概率分别为0.4,0.6,0.5
r\n     0       1       2       3   
0       1       0.6     0.24    0.12
1       0       0.4     0.52    0.38
2       0       0       0.24    0.38
3       0       0       0       0.12
他考了3道题,对了1道题的概率总是为:
考了2道题,对了0道题的概率  乘以  第3道题对的概率    再加上
考了2道题,对了1道题的概率  乘以  第3道题错的概率!!!!!!!!!!!!

他考了3道题,对了2道题的概率总是为:
考了2道题,对了1道题的概率  乘以  第3道题对的概率    再加上
考了2道题,对了2道题的概率  乘以  第3道题错的概率!!!!!!!!!!!!

不管考了几道题,他考了100道题,对了90道题的概率总是为:
考了99道题,对了89道题的概率    乘以  这道题对的概率 再加上
考了99道题,对了90道题的概率    乘以  这道题错的概率!!!!!!!!!!!!

他考了n道题,对了r道题的概率总是为:
考了n-1道题,对了r-1道题的概率  乘以  第n道题对的概率    再加上
考了n-1道题,对了r道题的概率    乘以  第n道题错的概率!!!!!!!!!!!!
好吧,又在谈数学了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

最后给上java代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double[] p = new double[n];
        for (int i = 0; i < n; i++) p[i] = (double)in.nextInt() / 100;
        double[][] dp = new double[n + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i < n + 1; i++) {
            dp[i][0] = dp[i - 1][0] * (1 - p[i - 1]);
            for (int j = 1; j < n + 1; j++){
                dp[i][j] = dp[i - 1][j - 1] * p[i - 1] + dp[i - 1][j] * (1 - p[i - 1]);
            }
        }
        double result = 0;
        for (int i = (3 * n + 4) / 5; i <= n; i++) {
            result += dp[n][i];
        }
        System.out.println(String.format("%.5f", result));
        in.close();
    }
}
相关文章
最新文章
热点推荐