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

八戒2 · 发表于 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

Igawk · 发表于 2011-3-28 00:00:48

本帖最后由 Igawk 于 2011-3-28 11:22 编辑

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

acme_pjz · 发表于 2011-3-28 12:42:19

回复 Igawk 的帖子

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

acme_pjz · 发表于 2011-3-28 13:39:09

我先打一个酱油……当N=6亿左右的时候发现中间结果的最大值涨到了1E+18，怀疑再算下去要溢出了……大家谁的电脑速度快的帮我测试一下，如果算到一半弹出“溢出”的话就说明真的出问题了……

acme_pjz · 发表于 2011-3-28 14:59:58

另外网上介绍各种优化方法：http://en.wikipedia.org/wiki/Collatz_conjecture

八戒2 · 发表于 2011-3-28 15:10:38

本帖最后由八戒2 于 2011-3-28 15:15 编辑

回复 acme_pjz 的帖子

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

测到了100亿，弹出了ok。

acme_pjz · 发表于 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++大数模板来玩玩

sjh717142 · 发表于 2011-3-31 15:27:58

本帖最后由 sjh717142 于 2011-3-31 15:58 编辑

这东西……

shamying · 发表于 2011-3-31 22:38:53

咦，这个好像在哪见过，叫什么飞行数什么的。
筛法不知道行不行。

		自动登录	找回密码
密码			立即注册

VBGood网站全文搜索

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

点评

评分

评分

点评

本帖子中包含更多资源

点评

点评

点评