VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 16448|回复: 27

擂台第70期[考拉兹猜想]

[复制链接]
 楼主| 发表于 2011-3-27 23:32:04 | 显示全部楼层 |阅读模式
本帖最后由 八戒2 于 2011-3-28 00:02 编辑

擂台赛第70期(2011.3.27)
题目:考拉兹猜想
级别:初级
说明:
1、考拉兹猜想,又称为3n+1猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想,是指对於每一个正整数,如果它是奇数,则对它乘3再加1,如果它是偶数,则对它除以2,如此循环,最终都能够得到1;
2、不要求从数学上证明,请从1计算到100亿,查看是不是都符合考拉兹猜想;
3、结果一定是符合,比速度也没意思,就出给初学者玩吧。

请参赛者在跟贴中只附上可执行文件。定稿后将源代码发到
擂台专用信箱:vbarena@163.com
文件及源码文件名格式:用户名_第几期_第几组_版本.rar
截稿日期:2011.4.20

点评

我估计初学者还不知道怎么算超过42亿的数呢……  发表于 2011-4-14 12:47
玩的都不是初学  发表于 2011-4-11 21:32

评分

参与人数 1人气 +1 收起 理由
lunber + 1 我很赞同

查看全部评分

发表于 2011-3-28 00:00:48 | 显示全部楼层
本帖最后由 Igawk 于 2011-3-28 11:22 编辑

偶数只要验证2就行了,2\2 = 1
所有的偶数经若干次“除以2”,终将变成小于这个偶数的奇数。

评分

参与人数 1人气 +2 收起 理由
sunfrank + 2 我很赞同

查看全部评分

回复 支持 0 反对 1

使用道具 举报

发表于 2011-3-28 12:42:19 | 显示全部楼层
回复 Igawk 的帖子

所以只需要验证奇数,而且当算到一半发现这个数比初始的时候要小,就OK了……但是关键问题在于就算是小于100亿的数字,算到一半数字可能远远大于100亿,所以要小心数据类型……

点评

而且“乘3再加1”可以换成“乘3再加1再除以2”,这样可以少算一步,而且代码运算量不变……  发表于 2011-3-28 12:43
回复 支持 反对

使用道具 举报

发表于 2011-3-28 13:39:09 | 显示全部楼层
我先打一个酱油……当N=6亿左右的时候发现中间结果的最大值涨到了1E+18,怀疑再算下去要溢出了……大家谁的电脑速度快的帮我测试一下,如果算到一半弹出“溢出”的话就说明真的出问题了……

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

点评

你直接给出那个会膨胀到1E+18的数让大伙验证就行了  发表于 2011-3-30 00:18
回复 支持 反对

使用道具 举报

发表于 2011-3-28 14:59:58 | 显示全部楼层
另外网上介绍各种优化方法:http://en.wikipedia.org/wiki/Collatz_conjecture
回复 支持 反对

使用道具 举报

 楼主| 发表于 2011-3-28 15:10:38 | 显示全部楼层
本帖最后由 八戒2 于 2011-3-28 15:15 编辑

回复 acme_pjz 的帖子

我帮你测到71亿了,还没溢出

测到了100亿,弹出了ok。

点评

我用C++又写了一个,在课程实验的电脑上,100亿用了120秒,不过用OpenMP并行计算10秒就出来了(那台电脑有16核)  发表于 2011-3-28 19:19
回复 支持 反对

使用道具 举报

发表于 2011-3-30 18:43:33 | 显示全部楼层
回复 Igawk 的帖子
你直接给出那个会膨胀到1E+18的数让大伙验证就行了
呵呵,我没有记录取得最大值的时候那个初始数字是什么……不过改改程序就可以了……
回复 支持 反对

使用道具 举报

发表于 2011-3-31 10:54:17 | 显示全部楼层
本帖最后由 仙剑魔 于 2011-3-31 10:55 编辑

上大数模板就好了
(n*3+1)/2=(n*2+n+1)/2=n+(n+1)/2
我在考虑要不要拿我的C++大数模板来玩玩

点评

嵌汇编算重度作弊……我还用GPU来算呢……  发表于 2011-3-31 23:19
VB版本的也有哈,嵌了汇编更爽哈  发表于 2011-3-31 16:09
必须用VB来做……要是用C++的话,我直接用GMP(GNU多精度库)就可以了,反正Linux自带……而且(n*3+1)/2=n+(n>>1)+1我早就知道了……  发表于 2011-3-31 13:57
回复 支持 反对

使用道具 举报

发表于 2011-3-31 15:27:58 | 显示全部楼层
本帖最后由 sjh717142 于 2011-3-31 15:58 编辑

这东西……
回复 支持 反对

使用道具 举报

发表于 2011-3-31 22:38:53 | 显示全部楼层
咦,这个好像在哪见过,叫什么飞行数什么的。
筛法不知道行不行。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2020-9-21 10:54

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表