9 条题解

  • 2
    @ 2017-07-02 19:08:17

    不是很懂楼下的化简,直接f[i]=i*(i^n-(i-1)^n)/(m^n)直接算啊?

    #include<stdio.h>
    #include<math.h>
    #define d double
    int m,n; d ans=0.;
    int main(){
        scanf("%d%d",&m,&n);
        for(int i=m;i;--i)
            ans+=i*(pow((d)i/m,n)-pow((i-1.)/m,n));
        printf("%.4lf\n",ans);
    }
    
  • 0
    @ 2015-02-19 15:22:27

    这题是算数学期望题目,关键是怎么算的快,不能越界,不能丢精度,关于精度问题好像不是特别重要,关键是不越界。

    一共m朵花,第i朵有i片花瓣,i=1...m, 一共随机n次,每次选一朵花,问这n次选到的一朵花花瓣数最大值的期望是多少。

    典型数学题,先列公式,E=sum(i=1..m) i*(i^n-(i-1)^n)/m^n, 直接计算出现指数,m n较大,显然不行,除非高精度,不过太费周折,
    于是简化公式,把公式展开,带i的一坨变为 1*1^n-1*0^n+2*2^n-2*1^n+....m*m^n-m*(m-1)^n=m*m^n-(1^n+...(m-1)^n)/m^n, 当时
    还一直在想有没有1^n+..m^n的求和公式,结果发现特别复杂,看来不对,不过一看这个,已经可以计算了,因为每一项都可以除以分母了,是小数的指数次
    于是直接列公式搞定。

    代码如下:

    int main()
    {
    int m, n;
    while(cin>>m>>n)
    {
    double sum=m;
    for(int i=1;i<m;i++)
    {
    sum-=pow(double(i)/m, n);
    }
    printf("%.4f\n", sum);
    }
    return 0;
    }

    这里面有一点组合数学的技巧,或者说对立事件,例如选择最大为i的次数,用1...i里面选n次,减去1..i-1里面选n次,这样剩下的就是至少选一次i片花瓣的次数了,

  • 0
    @ 2015-02-18 20:27:03

    易知最后最有活力的花有i个花瓣的概率 P(i) = i ^ n - (i - 1) ^ n。那么有:

    ans = 1 / (n ^ m) * \sum_{i = 1}^{m} (i ^ n - (i - 1) ^ n) * i

    可以推出:

    ans = m - \sum_{i = 0}^{m - 1} (i / m) ^ n

    ###Python 2.7 Code

    #input
    m, n = raw_input().split()
    m = int(m)
    n = int(n)

    # ans = 1 / (n ^ m) * sigma(i = 1 ~ m) { [i ^ n - (i - 1) ^ n] * i }
    # ==> n ** m * ans = m ** (n + 1) - sigma(i = 1 ~ m) { (i - 1) ^ n }
    # ==> ans = m - sigma(i = 1 ~ m) { [(i - 1) / m] ^ n }
    ans = m * 1.0

    for i in range(0, m) :
    ans -= (i * 1. / m) ** n

    print "%.4f" % ans

    不得不说Python确实很直观

  • 0
    @ 2015-02-18 17:02:32

    等比数列求和,如果要计算最大活力值为\(i\)的概率,首项为\(\dfrac{m-i+1}{m}\),公比为\(\dfrac{i-1}{m}\),项数为\(n\),然后减去以前所有数的和。

    Pascal Code

    var
    n,m:longint;
    i:longint;
    ans,sum,q,f:real;
    a:array[1..100001] of real;
    begin
    readln(m,n);
    sum:=0;
    for i:=m downto 1 do
    begin
    q:=(i-1)/m;
    f:=(m-i+1)/m;
    if i=1 then a[i]:=f
    else a[i]:=f*(1-exp(n*ln(q)))/(1-q);
    a[i]:=a[i]-sum;
    ans:=ans+a[i]*i;
    sum:=sum+a[i];
    end;
    writeln(ans:0:4);
    end.

  • 0
    @ 2015-02-17 16:57:14

    ###Code
    #include<cstdio>
    #include<cmath>
    int main()
    {
    int m,n;
    scanf("%d%d",&m,&n);
    double ans=m;
    for(int i=1;i<=m-1;i++)
    ans-=pow((i+0.0)/m,n);
    printf("%.4f",ans);
    return 0;
    }

  • 0
    @ 2015-02-16 11:58:20

    #include <cstdio>

    #include <cstring>

    #include <cstdlib>

    using namespace std;

    const int N=100001;

    int n,m;

    double res,t[N];

    double mi(double i,int k)

    {

    if (!k) return 1;

    double ans=mi(i,k>>1);

    return ans*ans*(k&1?i:1);

    }

    int main(void)

    {

    freopen("test.in","r",stdin);

    scanf("%d%d",&m,&n);

    for (int i=1;i<=m;i++) t[i]=mi((double)i/m,n);

    for (int i=m;i;i--) res+=(double)i*(t[i]-t[i-1]);

    printf("%0.4lf\n",res);

    return 0;

    }
    http://shadowchaser.lofter.com/post/1d04e306_5df51b3

  • 0
    @ 2015-02-15 13:05:44

    这个问题朴素地计算就行了. 选n次之后得到花瓣最多的花有k片花瓣的概率是(k^n-(k-1)^n)/m^n, 因为总共有m^n中选法, 而需要最多只有k片花瓣, 所以每次都得在1~k之内选, 选法有k^n种, 但是必须至少有一次选中了k片花瓣的花, 也就是不能每次都选中k-1以下的, 即减去(k-1)^n. 得出每个概率之后求期望就容易了, 最终得到m-((1/m)^n+(2/m)^n+...+((m-1)/m)^n). 用double计算不知道精度有没有问题...

    • @ 2015-02-17 16:22:11

      精度没问题~

  • -1
    @ 2015-02-15 12:06:24

    数论+快速幂?

  • -1
    @ 2015-02-13 21:49:41

    1234

  • 1

信息

ID
1919
难度
3
分类
概率论 | 数学期望 点击显示
标签
(无)
递交数
303
已通过
141
通过率
47%
上传者