首页 > 试题广场 >

骰子期望

[编程题]骰子期望
  • 热度指数：1937 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解 
扔n个骰子，第i个骰子有可能投掷出Xi种等概率的不同的结果，数字从1到Xi。所有骰子的结果的最大值将作为最终结果。求最终结果的期望。

输入描述:
第一行一个整数n，表示有n个骰子。（1 <= n <= 50）
第二行n个整数，表示每个骰子的结果数Xi。(2 <= Xi <= 50)


输出描述:
输出最终结果的期望，保留两位小数。
示例1

输入

2
2 2

输出

1.75
算法知识视频讲解
添加回答
Cyan1956头像 Cyan1956

csdn [编程题]骰子期望

这套卷子做下来感觉很难受，每道题都有思路，但是只有第一道题完美通过，做题速度堪忧。
本想把5道题都做了整一套题解，但是明天有华为笔试，我得去刷华为面经了，先写两道吧，剩下的后面再更新。

还是结合例子来讲。
4颗🎲，
最大值：25 9 10 43。

因为每颗骰子的结果都是独立的，同时每一面出现的可能都是相同的，因此可以用可能性相除得概率。

总的可能性为 种。

最大值为k（例如k=5）的可能性怎么求呢？
我们先求所有骰子值的情况：
然后再求所有骰子值的情况：
（如果k大于某一个骰子的最大值x，乘数取x。）

那么我们将前者减去后者，就可以得到：
所有骰子值并且不全部的情况，
换句话说必定存在。

实际上得到的就是最大值为k的所有可能性。

将一类可能性除以总的可能性得概率，概率乘数值再求和得期望。

还有一个细节值得一提，我最开始的做法是
将每一类可能性 乘以 其最大值 求和之后 再除以 总的可能性，这样会溢出。

所以不能等到最后再除，求和的过程中顺便除一下就不会溢出了。

代码是golang，但没什么高级语法，写其他语言的应该也能轻松读懂。 

package main

import "fmt"

func min(a,b int) int {
    if a<b{
        return a
    }else {
        return b
    }
}

func main() {
    var n,num int
    total:=1
    max:=0
    //fmt.Println(min)
    var nums []int
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&num)
        if num>max{
            max=num
        }
        total*=num
        nums= append(nums,num )
    }
    var ans float64
    pre:=0.0
    for i:=1;i<=max;i++{
        cur:=1.0
        for j:=0;j<n;j++{
            cur*=float64(min(i,nums[j]))/float64(nums[j])
        }
        ans+=(cur-pre)*float64(i)
        pre=cur
    }
    fmt.Printf("%.2f",ans)
}
编辑于 2020-05-19 17:04:11 回复(4)
Python
想去东北泡澡的芝士在刷题头像 想去东北泡澡的芝士在刷题 
def frac(a, b):
    if a > b:
        return 1
    if a <= b:
        return a / b

n = int(input())
x = list(map(int, input().split()))

m = max(x)
sum = 0
temp0 = 0
temp1 = 1
for i in range(1, m + 1):
    for j in x:
        temp1 *= frac(i, j)
    sum += (temp1 - temp0) * i
    temp0 = temp1
    temp1 = 1
print("{:.2f}".format(sum))

发表于 2020-08-08 14:31:49 回复(0)
为梦走路头像 为梦走路 
迭代
#include<bits/stdc++.h>
using namespace std;
vector<double> helper(vector<double> AG,vector<double> BG,int B){
    int A = AG.size();
    vector<double> r(max(A,B),0);
    if(A>B){
        for(int i = 0;i<A;i++){
            for(int j = 0;j<B;j++){
                int t = max(i+1,j+1);
                r[t-1] += AG[i]*BG[j]; 
            }
        }
    }
    else{
        for(int i = 0;i<B;i++){
            for(int j = 0;j<A;j++){
                int t = max(i+1,j+1);
                r[t-1] += AG[j]*BG[i]; 
            }
        }
    }
    return r;
}
int main(){
    int N,N1;
    cin>>N;//N个骰子
    N1 = N;
    vector<int> v;
    while(N1--){
        int temp;
        cin>>temp;
        v.push_back(temp);
    }
    vector<double> res(v[0],(double)1/v[0]);
    for(int i =1;i<N;i++ ){
        vector<double> B0(v[i],(double)1/v[i]); 
         res =  helper(res,B0,v[i]);  //迭代
    }
    double out_r = 0.0;
    for(int k = 0;k<res.size();k++){
        out_r+=(k+1)*res[k];
    }
    printf("%.2f",out_r);
    return 0;
}

发表于 2020-08-06 14:02:25 回复(0)
潜艇上的猫头像 潜艇上的猫 
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = 0;
        if(sc.hasNextLine())
            m = Integer.parseInt(sc.nextLine());
        //System.out.println(m);
        int[] numbers=new int[m];
        int count = 0;
        int max = 0;
        double res = 0;
        double pre=0;
        for(int i = 0; i < m;i++){
            int k = sc.nextInt();
            numbers[count++] = k;
            max=Math.max(max,k);
        }
        for(int i = 1; i <= max;i++){
            double temp = 1.0;
            for(int j = 0;j<m;j++){
                    temp *= (double)Math.min(i,numbers[j])/numbers[j];

            }
            res += (temp-pre)*i;
            pre = temp;
        }
        System.out.println(String.format("%.2f", res));
    }
}
根据最高赞的牛奶泡泡糖大神的python写的java版本

发表于 2020-08-02 17:32:16 回复(0)
梦心尘头像 梦心尘
 
总次数就是x1*x2*……*xn 
我们将其排序，假设x1……xn从小到大排列，从最大的开始看起，如果要让最大值=xn ，则让第n个色子的取值为xn，其他色子任取，情况有x1*x2*……xn-1种。然后我们第n个色子不能取xn了，把它减1放回原序列。
依次进行以上步骤，直到序列全部为1. 

import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;

public class Q4_2020 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] X = new int[num];
        for (int i=0; i<num; i++){
            X[i] = sc.nextInt();
        }
        DecimalFormat decimalFormat=new DecimalFormat(".00");
        String p=decimalFormat.format(qiwang(X));

        System.out.println(p);
    }
    public static double qiwang(int[] x){
        int len = x.length;
        double n=1;
        for (int value : x) {
            n = n*value;
        }
        Arrays.sort(x);
        double qiwang = 0;
        while (x[len-1]!=1){
            double a = 1;;
            for (int i = 0; i<len-1;i++){
                a = a*x[i];
            }
            qiwang += a*x[len-1];
            x[len-1] -=1;
            Arrays.sort(x);
        }
        qiwang +=1;
        return qiwang/n;
    }


}


发表于 2020-05-20 10:20:32 回复(2)
Fu188头像 Fu188
详细的解题思路以及代码可以参考我的这篇博客http://39.108.236.169:8080/article/2
发表于 2020-05-26 23:59:15 回复(2)
牛奶泡泡糖头像 牛奶泡泡糖 
#这里需要懂一点概率论的知识，p(x=k)=p(x<=k)-p(x<=k-1)
#以两个筛子为例，可以转化为求联合概率分布的面积/总面积
#期望就是p(k)*k 求和
def main(n,nums):
    total=1
    maxs=max(nums)
    ans=0
    pre=0
    for i in range(1,maxs+1):
        cur=1
        for j in range(n):
            cur*=min(i,nums[j])/nums[j]
        ans +=(cur-pre)*i
        pre=cur
    return ans


n=int(input())
nn=list(map(int,input().split()))
ans=main(n,nn)
print("%.2f" % ans)
以两个筛子，最大值为2,3为例
可以得出，总概率分布的面积为2*3=6
对1来说，最大值为1 的概率就是1*1的正方形，概率为cur=1/2*1/3=1/6  
对2来说，最大值为2的概率就是2*2的正方形减去1*1的正方形，也就是cur-pre=2/2*2/3-1/6 =3/6
对3来说，最大值为3的概率就是面积为6的长方形减去面积为4的情况2，也就是2/2*3/3-4/6
综上，求得nums的max值，对其i遍历
           对于每个i，计算i的概率cur
           ans=(cur-pre)*i

发表于 2020-07-02 17:36:52 回复(4)
pein531头像 pein531
对于最终结果k，只要n个骰子中有一个掷出了k，其余的点数均小于等于k，那最终结果就是k。
A.计所有骰子的点数都不超过k的概率为P(x<=k)
B.计所有骰子的点数都小于k的概率为P(x<=k-1)
很明显，事件A是包含事件B的，最终结果为k（即事件A-B）的概率为P(x=k)=P(x<=k)-P(x<=k-1)。而对于一组骰子X=[X1,X2,...,Xn]，最终结果的可能取值就是[2,max(X)] 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strArr = br.readLine().trim().split(" ");
        int[] X = new int[n];
        // 计算最大的点数
        int maxPoint = 0;
        for(int i = 0; i < n; i++) {
            X[i] = Integer.parseInt(strArr[i]);
            if(X[i] > maxPoint) maxPoint = X[i];
        }
        double preE = 0.0;
        double expectation = 0.0;
        // 题中指出Xi>=2
        for(int k = 2; k <= maxPoint; k++){
            double curE = 1.0;
            // 计算每个骰子点数不超过k的概率，注意有些骰子掷不到点数k
            for(int i = 0; i < n; i++)
                curE *= Math.min(k, X[i])*1.0 / X[i];
            // ∑[P(x<=k)-P(x<=k-1)]*k
            expectation += (curE - preE)*k;
            preE = curE;
        }
        System.out.printf("%.2f", expectation);
    }
}


发表于 2021-02-05 16:07:52 回复(1)
Nekiu头像 Nekiu
C++ 解法： 
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  cin.get();
  vector<int> dices(n, 0);
  int max_val = INT32_MIN;
  for (int i = 0; i < n; i++) {
    cin >> dices[i];
    max_val = max(dices[i], max_val);
  }
  float result = 0.0, pre = 0.0;

  for (int i = 1; i <= max_val; i++) {
    double item = 1.0;
    for (int j = 0; j < n; j++) {
      int dice = dices[j];
      item *= (min(i, dice) / (dice * 1.0));
    }
    result += ((item-pre) * i);
    pre = item;
  }
  printf("%.2f", result);
}
// 64 位输出请用 printf("%lld")


发表于 2023-03-08 22:02:45 回复(0)
Python
刘洁o头像 刘洁o
L=[2,3,5]
p=list(range(max(L)+1))
P=list(range(max(L)+1))
p_sum=0
def FUN(N,K):
    return min(1,K/N)
for i in range(1,max(L)+1):
    P[i]=1
    for j in L:
        P[i]=P[i]*FUN(j,i)
    if i>1:
        p[i]=P[i]-P[i-1]
    else:
        p[i]=P[i]
    p_sum=p_sum+i*p[i]
print(p_sum)
发表于 2022-12-23 13:48:20 回复(0)
苏觅云头像 苏觅云 
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, xi;
    cin >> n >> xi;
    vector<double> dp(xi + 1, 1.0 / xi);
    for (int ni = 1; ni < n; ni++) {
        cin >> xi;
        vector<double> ndp(xi + 1, 1.0 / xi);
        if (dp.size() < ndp.size()) {
            swap(dp, ndp);
        }
        vector<double> tdp(dp.size(), 0);
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < ndp.size(); j++) {
                if (i >= j)
                    tdp[i] += (dp[i] * ndp[j]);
                else
                    tdp[j] += (dp[i] * ndp[j]);
            }
        }
        swap(dp, tdp);
    }
    double ans = 0;
    for (int i = 1; i < dp.size(); i++) {
        ans += dp[i] * i;
    }
    printf("%.2lf", ans);
    return 0;
}

发表于 2022-08-10 21:31:21 回复(0)
C/C++
cymm保佑拿理想offer头像 cymm保佑拿理想offer 
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>x(n);
    int maxk=0;
    
    for(int i=0;i<n;i++){
        cin>>x[i];
    //    sum*=x[i];
        if(x[i]>maxk){
            maxk=x[i];
        }
    }
    
    vector<double>arr(maxk+1,0);
    double s=0;
    for(int i=1;i<=maxk;i++){
        double t=1;
        for(int j=0;j<n;j++){
            t*=(double)min(x[j],i)/x[j];
        }
        arr[i]=t;
        //cout<<t<<" ";     
        s+=(double)(arr[i]-arr[i-1])*i;
    }
    printf("%.2f\n",s);    
    
}

发表于 2020-12-31 16:09:26 回复(0)
Cingti头像 Cingti 
n = int(input())
nums = list(map(int, input().strip().split()))
# S表示所有可能的结果
S = 1
for x in nums:
    S = S * x
# max_x表示结果的最大值
max_x = max(nums)
# S_k_1表示最大值k-1的所有可能的结果
S_k_1 = 0
# mu为期望
mu = 0
for k in range(1, max_x+1):
    S_k = 1
    for x in nums:
        # 由于不是所有的骰子的结果都能取到k,因此需要min
        S_k = S_k * min(k, x)
    mu += k*(S_k - S_k_1)/S
    S_k_1 = S_k
print('{:.2f}'.format(mu))

编辑于 2020-09-09 15:34:42 回复(0)
~锦鲤附身~头像 ~锦鲤附身~ 
def helper(X):
    p_x = 1
    for xi in X:
        p_x /= xi 

    res = 0
    for i in range(1, max(X)+1):
        tmp = 0
        tmp1 = 1
        for xi in X:
            if xi >= i:
                tmp += 1
            else:
                tmp1 *= xi
        # print((i**tmp - (i-1)**tmp) * tmp1)
        res += i * (i**tmp - (i-1)**tmp) * tmp1 * p_x
    print('{:.2f}'.format(res))

while True:
    try:
        N = int(input())
        nums = list(map(int, input().split()))
        helper(nums)
    except:
        break 

发表于 2020-08-02 18:25:55 回复(0)
passerby_A头像 passerby_A
因为超过int，double范围改了好多次，而且自己没装c++编译器导致排错浪费了太多时间，自己做法本质还是直接穷举，对结果为1-max分别求出期望加上

#include <iostream>
#include <cmath>
#include<iomanip>
using namespace std;
 
int main(){
    int ncase;
    double e = 1;
    int max = 0;
    cin>>ncase;
    int* cases = new int[ncase];
    if(ncase < 1 || ncase > 50){
        delete cases;
        return 0;
    }
    for(int i = 0; i < ncase; ++i){
        cin>>cases[i];
        if(cases[i] < 2 || cases[i] > 50){
            delete cases;
            return 0;
        }
        if(cases[i] > max){
            max = cases[i];
        }
    }
    for(int i = 2; i <= max; ++i){
        long double port = 1;
        int counter = 0;
        for(int j = 0; j < ncase; ++j){
            if(cases[j] < i){
                port *= cases[j];
            }
            else{
                counter++;
            }
        }
        port *= (pow(i, counter) - pow(i - 1, counter));
        for(int j = 0; j < ncase; ++j){
            port /= cases[j];
        }
        e += i * port;
    }
    e -= 1;
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<e<<endl;
    delete cases;
    return 0;
}
发表于 2020-06-30 22:35:52 回复(0)
菜鸟201711052124359头像 菜鸟201711052124359 
#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
int main(){
    unsigned long int n, max;
    cin>>n;
    vector<int> inputArray(n);
    for(int i=0;i<n;i++){
        cin>>inputArray[i];
        if(inputArray[i]>max){
          max=inputArray[i];
        }  
    }
    double ans = 0.0, pre = 0;
    for(int i=1;i<=max;i++){
       double cur = 1.0;
       for(int j=0;j<n;j++){
           cur *=(min(i,inputArray[j])/(double)inputArray[j]) ;
           //一定要加括号把右侧括起来，否则通过率会下降，求解
       }
           ans += (cur - pre)*(double)i;
           pre  = cur;
    }
    cout<<fixed<<setprecision(2)<<ans<<endl;
}


package main
import "fmt"
func min(a, b int) int {
    if a<b{
        return a
    }else{
        return b
    }
}
func main(){
    var n, num int
    max   := 0
    var nums []int
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&num)
        if num>max{
            max=num
        }
        nums   = append(nums, num)
    }
    var ans float64
    pre :=0.0
    for i:=1;i<=max;i++{
        cur := 1.0
        for j:=0;j<n;j++{
            cur*=float64(min(i,nums[j]))/float64(nums[j])
        }
        ans += (cur - pre)*float64(i)
        pre =cur
    }
    fmt.Printf("%.2f", ans)
}

编辑于 2020-06-25 21:31:31 回复(2)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 前端工程师 算法工程师 PHP工程师 2020 拼多多 大数据开发工程师 Java工程师 信息技术岗
上传者：小小
难度：
16条回答 8833浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号