拼多多笔试题-掷骰子

快来打我* 2023-08-17 17:30 57阅读 0赞

#### 拼多多2020校招笔试题 ####

#### 题目 掷骰子 ####

> 掷n个不同面数的骰子，以最大点数为结果，求点数的期望。一共有n个骰子  
> 第i个骰子面数为 n i n\_i ni，点数为\[1, n i n\_i ni\]，每个面的概率相同,同时掷这n个骰子，
> 
> 所有骰子中的最大点数为最终点数,求骰子投出的期望值

#### example1 ####

输入

2
    2 2

输出

1.75

#### example2 ####

输入

4
    1 2 3 4

输出

2.875

#### 分析 ####

开始想暴力解，发现几乎不可能，最后发现竟然可以用动态规划的思路解出来。

假设前n-1个色子,最终获得各个点数的概率为 \[ p 1 , p 2 , . . . p s \] \[p\_1, p\_2,...p\_s\] \[p1,p2,...ps\] ,

( p 1 p\_1 p1对应点数为1的概率，以此类推，m是所有n-1个色子中最大面数)

n个色子，最终获得各个点数的概率 \[ p 1 , p 2 , p 3 , . . . p t \] \[p\_1,p\_2,p\_3,...p\_t\] \[p1,p2,p3,...pt\]，(n是所有n个色子中最大面数)

可以由前n-1个色子推出来。

假设最终的点数为m,可以由以下几种情况组成

*  前n-1个色子最终点数小于m的概率 , 乘于 第n个色子点数为m的概率
 *  前n-1个色子最终点数等于m的概率，乘于 第n个色子点数为小于等于m的概率

得到递推公式后，码出代码就是很简单的事了

#### java AC代码 ####

import java.util.Scanner;
    import java.io.File;
    public class Main{ 
        public static void main(String args[]) throws Exception{ 
            //File file = new File("in.txt");
            //Scanner sc = new Scanner(file);
            Scanner sc = new Scanner(System.in);
            int number = sc.nextInt();
            int []arr = new int[number];
            for(int i = 0; i < number; i++) arr[i] = sc.nextInt();
            int maxNumber = 0;
    
            //获取最大面数
            for(int i = 0; i < number; i++) { 
                if (maxNumber < arr[i]) maxNumber = arr[i];
            }
    
            //result存储最后结果，temp存储临时结果
            double [] result =  new double[maxNumber+1];
            double [] temp  = new double[maxNumber+1];
            for(int i = 0; i <= maxNumber; i++) { 
                result[i] = 0; temp[i] = 0;
            }
    
            //第一个色子
            for(int i = 1; i <= arr[0]; i++) result[i] = 1.0 / arr[0];
            for(int i = 1; i <= arr[0]; i++) temp[i] = 1.0 / arr[0];
    
            //递推
            for(int i = 1; i < number; i++) { 
                for(int j = 1; j <= arr[i]; j++) { 
                    //第一种情况 + 第二种情况
                    result[j] = sum(temp, j-1) * (1.0/arr[i]) + temp[j] * j *(1.0/arr[i]);
                }
                for(int t = 1; t <= maxNumber; t++) temp[t] = result[t];
            }
    
            double finalResult = 0;
            for(int i = 1; i <= maxNumber; i++) finalResult += i * result[i];
            
            sc.close();
            System.out.println(finalResult);
        }
    
        public static double sum(double []arr, int index) { 
            double total = 0;
            for(int i = 1; i <= index; i++)  total += arr[i];
            return total;
        }
    }