求一个概率算法，给出算法者立即给分。

1-1000 取一个随机数a
用a做数组b大小，然后每个数组元素用1-1000的随机数填充，然后求数组b之和，1000*1000*0.7为c，问b大于c的概率。

解决方案 »

  1.   

    有可能a>700
    就有可能
      

  2.   

    楼上算错了
    是
    数组b之和-c
    不是
    数组b长度-c
      

  3.   

    这个1000*1000*0.5我跑100000 b>c概率是500/1000
    这个1000*1000*0.7我跑100000 b>c概率是4/1000
    这个1000*1000*0.9我跑100000 b>c概率是1/1000我想知道这个之间的关系.
      

  4.   

    楼上算错了
    是
    数组b之和-c
    不是
    数组b长度-c
    ..........................
    我写错了 算的是b的合-c
      

  5.   

    a: [1,1000]
    b.length: a
    b[i]:[1,1000]当a<=700的，不予考虑，这里有s1 = 1*1+2*1000^2+...+n*1000^n+...+70*1000^70种取法
    然后算a>700的情况,假设有s2种，大于700000的有s3种，
    那么结果就是
    s3/(s1+s2)这个东西直接算不现实。必须要用一些小技巧。
    下面的回复中，我会说一下这个。
      

  6.   

    1 数学算法：
    定义m=(n-700)*1000, 699<n<1001A(n) =1 + n + n^2/2! + n^3/3!…… + n^m/m!;
    B(n) = A(n)/1000^n;
    C = B(700) + B(701) + …… + B(1000);
    D = C / 1000;D就是结果了解析：
    明显，当n>699时才有可能
    对于每一个n>699的情况，我们可以看作所有数组都是由最大值(1000)减去一个0至999的随机值取得；所以对于每一个n，满足条件的减去的总数值不能超过m
    A(n)是在n个数中，减去不多于m个数的所有的可能情况的个数。而n个数所有的可能情况是1000^n;
    所以B(n)是对于单个n 满足条件的概率。而n总共有1000种可能，所以，总的概率是D
      

  7.   

    写错了一点
    A(n)是在n个数中，减去总和不多于m的所有组合的所有的可能情况的个数。晕，针绕嘴
    A(n)是在n个数中，减去（总和不多于m的数的所有组合）的所有的可能情况的个数。这下好像不容易产生歧义。
      

  8.   

    为说明问题，考虑等于1000×1000×0.7情形
    数学描述：
    假设实验次数为N,数组a[1-1000]每种出现可能性N/1000,理论上N/1000>1000^i(i为数组a的大小)，即N>1000^1001为最佳测试次数，能够保证遍历所有情形至少一次。对于a[1]-a[699]   数组之和b>c次数为C[a[i]]=0
        a[700]                         C[a[700]]=1
    当i>700时  
        计算a[i]之和>c的平均值v，从而保证数组元素a[j]（1=<j<=i）取值在v附近，即部分数组元素序列组合之和为v，从而可寻找到满足条件最小集，据此可计算数组C[a[i]];
    概率D=(C[a[1]]+C[a[2]]+...+C[a[i]]+...+C[a[1000]])/N以上只是理论上的，没有实际计算意义。
      

  9.   

    补充C[a[i]]包括C[a[i-1....i-2....3.2.1]]特例，要减去这些重复项