首页 > 试题广场 > 骰子期望
[编程题]骰子期望
  • 热度指数:1302 时间限制: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
#这里需要懂一点概率论的知识,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 回复(3)
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)

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)
对于最终结果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 回复(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)
详细的解题思路以及代码可以参考我的这篇博客http://39.108.236.169:8080/article/2
发表于 2020-05-26 23:59:15 回复(2)
#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)
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)
因为超过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)
#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)