一道困扰了我很久的题目

noski

这是一种用计算机产生随机数模拟事件发生的数值算法。
每次取三个1-100的随机数，检验它们是否是等比数列。
这样取相当多次之后，比如100万次，结果的概率就会相当接近于理论值。

noski

呵呵，判断了N多条件，算出了精确解，就是0.073%。
计算方法：
第一步，计算有多少种可能组合，算上1 1 1这种相同数的，共有205种情况。如果不算是105种。
第二步，对于1-100的每一个数字N，在205种情况中查找包含N的组合数M。比如：
when N = 2
  1 2 4
  2 2 2
  2 4 8
  2 6 18
  2 8 32
  2 10 50
  2 12 72
  2 14 98
Total: M = 8
第三步，根据1-100的每个M值，计算概率。
P    =          ∑   ( (2 * Mi - 1) / 1000000 )
            (i=1~100)  
也就是说，取第一个数的概率是1%；取了第一个数之后，只有2M-1种可能取第二个数，概率是(2M-1)*1%；第三个数为1%（注：类似取2 4 1 和2 4 8这样的情况已算在第二个数中了）。由此得最后结果0.073%。

即，依次取三个数的100*100*100种可能性中，成等比数列的情况有730种。
如果不允许1 1 1这样的情况出现，那么可能情况数减100，为630种，分子成为100*99*98，结果为0.0649%。结果和7楼一样。

[ 本帖最后由 noski 于 2009-1-16 10:43 编辑 ]

beijiaoff

感觉这个没什么难度啊。。c罗说的不对么

第8个小笼包

不算公比为1的情况，的确是105种，但是这个结论能推广到N个数吗？

tyeken8

如果算111和222那么分母就不是100C3而是100^3

tyeken8

有多项式算法为什么要用蒙特卡罗算法？

shenheng

回： tyeken8
再写复杂一点的话，就可以去参加IOCCC大赛了，呵呵。a、b、c的取值范围还有很大的优化空间呢，如果三个值均不相同的话，a的最大值应该少于等于100/2/2=25吧，计算速度至少快几倍了。


int main(_){
    int a,b,c;
    for(a=0;a<=98;a++)
        for(b=a+1;b<=99;b++)
            for(c=b+1;c<=100;c++)
                if(b*b==a*c) _++;
    exit(printf("%d",_-1));
}

[ 本帖最后由 shenheng 于 2009-1-16 14:18 编辑 ]

R'cube

我的解答，这个就不水了

tyeken8

额，今天早上一边吃饭一边写的点东西而已，一点优化都没有，想写更短的也不是做不到的

cyz

都是很复杂的…………好痛苦 啊………………