骰子期望

迭代
#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;
}

#这里需要懂一点概率论的知识，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)

csdn [编程题]骰子期望

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

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

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

总的可能性为 种。

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

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

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

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

代码是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)
}

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))

#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;
}

#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);    
    
}

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))

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 

#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)
}