魔方吧·中文魔方俱乐部

标题: 一道困扰了我很久的题目 [打印本页]

作者: 第8个小笼包 时间: 2009-1-16 01:33:22 标题: 一道困扰了我很久的题目

从1~100这100个整数中任取3个数字，这3个数成等比数列的概率是多少呢？

作者: 方块 时间: 2009-1-16 02:00:18

好像比较复杂...期待答案...
我很费解啊...

作者: Cielo 时间: 2009-1-16 02:02:22

分母应该是 100C3 吧，然后分子是以下各数的和：
公比是2：首项可以是 1 到 25，——25
公比是3：首项可以是 1 到 11，——11
公比是4：首项可以是 1 到 6，——6
公比是5：首项可以是 1 到 4，——4
公比是6或7：首项可以是 1 到 2，——4
公比是8到10：首项只能是 1 。——3
公比是11或更多：不存在这样的组合。

不知道是不是这样算啊？

[ 本帖最后由 Cielo 于 2009-1-16 03:59 编辑 ]

作者: noski 时间: 2009-1-16 03:29:14

用蒙特卡罗方法吧，概率在0.073%附近，不是精确解。

作者: tyeken8 时间: 2009-1-16 08:09:28

蒙特卡罗算法是一类算法的总称吧？RP类问题解决方法的总称……
有50%以上得到正确结果的算法

作者: tyeken8 时间: 2009-1-16 08:17:26

105
---------
100C3

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

作者: tyeken8 时间: 2009-1-16 08:17:58

6.4935064935064935064935064935065e-4

作者: tyeken8 时间: 2009-1-16 08:30:25

额……没人鸟我了…………

作者: noski 时间: 2009-1-16 08:45:30 标题: 回复 6# 的帖子

如果出现1、1、1和2、2、2……这种也算是等比数列的，这样a要从1取到100。

作者: kexin_xiao 时间: 2009-1-16 09:03:50

4楼能公布一下具体的方法吗？我想学习一下，谢谢

作者: noski 时间: 2009-1-16 09:24:28 标题: 回复 10# 的帖子

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

作者: noski 时间: 2009-1-16 10:11:04

呵呵，判断了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 时间: 2009-1-16 10:28:29

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

作者: 第8个小笼包 时间: 2009-1-16 11:35:06 标题: 回复 12# 的帖子

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

作者: tyeken8 时间: 2009-1-16 12:10:22

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

作者: tyeken8 时间: 2009-1-16 12:26:44

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

作者: shenheng 时间: 2009-1-16 14:15:02 标题: 回复 6# 的帖子

回： 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 时间: 2009-1-16 14:36:44

我的解答，这个就不水了

附件: 解答.rar (2009-1-16 14:36:44, 5.69 KB) / 下载次数 1
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MzU4NDV8YzE2Y2I0NmJ8MTcyNzU4MDg4MHwwfDA%3D

作者: tyeken8 时间: 2009-1-16 17:00:53

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

作者: cyz 时间: 2009-1-16 17:14:50

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

作者: ursace 时间: 2009-1-17 02:03:35

100个数中取3个，不说能否重复则显然为不能重复

作者: R'cube 时间: 2009-1-17 02:45:02

其实真的是很简单的一道题啊

纯高中知识

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)