- 浏览: 620145 次
- 性别:
- 来自: 北京
最新评论
今天看到一个题在入门版.....
http://www.iteye.com/topic/728160
挪过来看看.
还是要接近3秒,cpu1.8G
2890,如果循环加上sysout要28000。。。
http://www.iteye.com/topic/728160
挪过来看看.
Crusader 写道
3x+1问题,它描述的是这样一个现象:
任取一个自然数,如果它是偶数,就把它除以2,如果它是奇数,就把它乘3再加上1。如此,就得到了一个新的自然数。再按照上述规则反复操作新产生的自然数,我们就会得到一串自然数,而最终得到的自然数序列将陷在4→2→1这个循环中。。。
如 5→16→8→4→2→1→4→2→1。。。
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1→4→2→1。。。
这个猜想目前还无法证明,只能穷举,最闲的人已经验证到100*2的50次方。。。
运行的时候,循环改小点,否则估计要运行1千万年左右,应该都活不到那么长吧...
任取一个自然数,如果它是偶数,就把它除以2,如果它是奇数,就把它乘3再加上1。如此,就得到了一个新的自然数。再按照上述规则反复操作新产生的自然数,我们就会得到一串自然数,而最终得到的自然数序列将陷在4→2→1这个循环中。。。
如 5→16→8→4→2→1→4→2→1。。。
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1→4→2→1。。。
这个猜想目前还无法证明,只能穷举,最闲的人已经验证到100*2的50次方。。。
运行的时候,循环改小点,否则估计要运行1千万年左右,应该都活不到那么长吧...
public class _3X1 { // 是否奇数 private static boolean isOdd(long i){ return (i&1L)==1L; } // 判断是否4 | 2 | 1 private static boolean is_4_2_1(long i){ return i==4 || i==2 || i==1; } // 判断是否2的次方,如果是,直接断定满足3x+1 private static boolean isPower2(long i){ int count = 0; while(i>0 && count<2){ i = i & (i-1L); count++; } return count==1; } // 满足3x+1猜想则返回true,否则死循环 public static boolean _3x1(long i){ int flag = 0; while(flag<3){ // 如果是奇数 if(isOdd(i)){ i = i*3L+1L; // 如果是偶数 }else{ i >>= 1; } if(is_4_2_1(i)){ flag++; }else{ flag=0; } } return true; } public static void main(String[] args) { for(long i=1; i<Long.MAX_VALUE; i++){ if(isPower2(i) || _3x1(i)){ System.out.println(i); } } } }
评论
6 楼
Crusader
2010-08-06
抛出异常的爱 写道
不加sysout
用时:1047
你可以试试你的机器上多少
用时:1047
你可以试试你的机器上多少
public class _3X1 { // 是否奇数 private static boolean isOdd(long i){ return (i&1L)==1L; } // 判断是否2的次方,如果是,直接断定满足3x+1 private static boolean isPower2(long i){ return 0 == (i & (i-1L)); } // 满足3x+1猜想则返回true,否则死循环 public static boolean _3x1(long i){ while(!isPower2(i)){ // 如果是奇数 if(isOdd(i)){ i += i>>1; i++; // 如果是偶数 }else{ i >>= 1; } } return true; } public static void main(String[] args) { long start = System.currentTimeMillis(); for(long i=1; i<1000000L; i++){ if(_3x1(i)){ //System.out.println(i); } } System.out.println(System.currentTimeMillis()-start); } }
还是要接近3秒,cpu1.8G
5 楼
抛出异常的爱
2010-08-06
不加sysout
用时:1047
你可以试试你的机器上多少
用时:1047
你可以试试你的机器上多少
public class _3X1 { // 是否奇数 private static boolean isOdd(long i){ return (i&1L)==1L; } // 判断是否2的次方,如果是,直接断定满足3x+1 private static boolean isPower2(long i){ return 0 == (i & (i-1L)); } // 满足3x+1猜想则返回true,否则死循环 public static boolean _3x1(long i){ while(!isPower2(i)){ // 如果是奇数 if(isOdd(i)){ i += i>>1; i++; // 如果是偶数 }else{ i >>= 1; } } return true; } public static void main(String[] args) { long start = System.currentTimeMillis(); for(long i=1; i<1000000L; i++){ if(_3x1(i)){ //System.out.println(i); } } System.out.println(System.currentTimeMillis()-start); } }
4 楼
Crusader
2010-08-06
public class _3X1 { // 是否奇数 private static boolean isOdd(long i){ return (i&1L)==1L; } // 判断是否4 | 2 | 1 private static boolean is_4_2_1(long i){ return i==4 || i==2 || i==1; } // 判断是否2的次方,如果是,直接断定满足3x+1 private static boolean isPower2(long i){ return 0 == (i & (i-1L)); } // 满足3x+1猜想则返回true,否则死循环 public static boolean _3x1(long i){ int flag = 0; while(flag<3){ // 如果是奇数 if(isOdd(i)){ i = i*3L+1L; // 如果是偶数 }else{ if(isPower2(i)) return true; i >>= 1; } if(is_4_2_1(i)){ flag++; }else{ flag=0; } } return true; } public static void main(String[] args) { long start = System.currentTimeMillis(); for(long i=1; i<1000000L; i++){ if(_3x1(i)){ //System.out.println(i); } } System.out.println(System.currentTimeMillis()-start); } }
2890,如果循环加上sysout要28000。。。
3 楼
抛出异常的爱
2010-08-05
增加cache版
10^6 使用时间4547
效率十倍左右
10^6 使用时间4547
效率十倍左右
import java.util.HashSet; import java.util.Set; import org.apache.commons.lang.StringUtils; public class ThreeXone { Set cache = new HashSet< Long>(); /** * @param args */ public static void main(String[] args) { ThreeXone x = new ThreeXone(); x.cache.add(1L); long start = System.currentTimeMillis(); for(int i = 0 ; i <100000 ;i++){ x.mySelf(i); } long end = System.currentTimeMillis(); System.out.println("使用时间"+(end - start) ); } long trimZero(long bin){ String str = Long.toBinaryString(bin); String result = StringUtils.substringBeforeLast(str, "1")+1; return Long.valueOf(result,2); } long funcOdd (long odd ){ odd += odd>>1; odd ++; return odd; } void mySelf(long bin ){ long result = 0; //System.out.print(bin+"->"); long odd = trimZero(bin); if(isInMap(odd)){ //System.out.println(); return; }else{ result = funcOdd(odd); mySelf(result); cache.add(bin); } } boolean isInMap(long odd) { return cache.contains(odd); } }
2 楼
抛出异常的爱
2010-08-05
大家如果想用int则录入值不能大于10^5
(会溢出)
(会溢出)
1 楼
抛出异常的爱
2010-08-05
10^5 速度2秒左右
10^6 速度39438
想法.
1,偶数除2等效于二进制去掉尾0
2.奇数乘3必为奇数 再+1必为偶数 等效为 2x + x +1 x左移1 + x +1
如果都除2等效为 x+ x右移1 +1
10^6 速度39438
想法.
1,偶数除2等效于二进制去掉尾0
2.奇数乘3必为奇数 再+1必为偶数 等效为 2x + x +1 x左移1 + x +1
如果都除2等效为 x+ x右移1 +1
import org.apache.commons.lang.StringUtils; public class ThreeXone { /** * @param args */ public static void main(String[] args) { ThreeXone x = new ThreeXone(); long start = System.currentTimeMillis(); for(int i = 0 ; i <10^6 ;i++){ x.mySelf(i); } long end = System.currentTimeMillis(); System.out.println(end - start ); } long trimZero(long bin){ String str = Long.toBinaryString(bin); String result = StringUtils.substringBeforeLast(str, "1")+1; return Long.valueOf(result,2); } long funcOdd (long odd ){ odd += odd>>1; odd ++; return odd; } void mySelf(long bin ){ long result = 0; //System.out.print(bin+"--"); long odd = trimZero(bin); if(odd==1){ //System.out.println(); return; }else{ result = funcOdd(odd); mySelf(result); } } }
发表评论
-
关于四维的问题
2016-04-22 14:14 1106知乎:为什么人类想象不出四维的空间? https://www. ... -
freemind 怎么处理成为word
2015-06-11 19:37 16写文章用freemind打了一个草稿. 先导出成为htm ... -
油猴对抗一般广告
2012-11-14 00:07 1837看小说 好多好多的广告是必然的.. 所以 去掉iframe 去 ... -
油猴对抗google抽疯
2012-10-23 16:25 1757http://www.iteye.com/topic/1127 ... -
今天想回又想这样回会不会很损
2010-12-07 11:51 2654http://www.iteye.com/topic/8337 ... -
转贴:如何在面试中发现优秀程序员
2010-09-30 10:09 3141http://www.aqee.net/2010/09/29/ ... -
百度大战QQ
2010-09-16 14:46 1761不知道怎么发新闻..... 百度正在内测 http://t.b ... -
牛X是种态度(答复: 对于水平一般的程序员,技术要深度还是广度)
2010-08-23 09:29 2589zlt2000 写道建议楼主应 ... -
哲学问题
2010-07-12 09:37 1081[url="http://www.iteye.com ... -
三人法则
2010-06-18 15:37 1268一个人只能去适应你所在的环境.当有三个人的时候.你就拥有改变环 ... -
各种被代表的不鸣真象的群棕
2010-06-02 17:32 1577昨天 今天 看了一个贴子被隐了 它不应该被隐 看见一个贴子 ... -
开始找工作,另帮同事一起找活干,有猎头可直接联系
2010-03-24 11:51 8362由于特别的原因开始找工作了 另:帮同事一起找工作。 同事们都 ... -
怎么样写项目描述
2010-03-24 03:05 3572引用 自助交易平台 设计并开发包括用户,平台帐户,仓储等模块 ... -
房子恶梦
2010-03-18 11:20 1635喜欢新技术 说 (11:10): http://ww ... -
电影宅帮个忙
2010-01-12 16:06 1564亲爱的电影达人 我在看这个短片时只能认出其中几部电影 ... -
汉经学,晋清谈
2009-11-30 09:05 1278在网络上比较有名的坛子都存在两种人. 1.经学:把大师的话当 ... -
恒河沙, 一年即一生
2009-10-14 09:21 1633每三个月跳槽一次.... 一年可了认识4*20左右的人 5-8 ... -
倒得精 连载<一>
2009-05-08 10:47 1107[原文] 上德不德,是以有德。下德不失德,是以無德。 上德, ... -
真孙子
2009-03-04 10:22 0孙子曰: 引用兵者, ... -
塔希里亚故事集II 出书了
2009-01-22 16:11 909最喜欢看的漫画 风格比剑风还好 如果以上算是软文的话. 那么 ...
相关推荐
一个有关3x+1问题的新等式,蒋愉,吴栋梁,本文在现有基础上继续探讨公开难题3x+1问题,并得到了一些新结果。在之前的研究中,我们已经发现了一些有趣的现象,其中包括一个�
本文证明了Collatz 3x+1问题的下列同高定理,给出无限多类型的长分别为3、4和15的同高连续正整数: (1)连续正整数C_t-1,C_t-2,C_t-3有相同的高,其中C_t=2~(46t+40)m+2~(64t+32); (2)连续正整数d_t-1,d_t-2,d_t-3和d_t-...
有关3x+1问题的一些新结果,蒋愉,吴栋梁,本文主要研究了公开的数学难题--3x+1问题。利用专业数学软件Mathematica 5.0,我们给出了一个较R.E.Crandall之前给出的更为完整和丰富的表格
分享一套关于酒店管理系统开发的教程——基于SpringBoot3.x+Vue3.x整合从0到1一步一步实现酒店管理系统,学完本课程,您将收获:增加项目实战经验;学习SpringBoot项目应用中遇到各种问题;学会使用前后端分离开发! ...
内容概要:通过对3x +1猜想值变换的模6特征分析,可把猜想值变换分为初始变换和内变换两种情形,并论证了内变换只存在三种变换类型,得到了猜想值变换增加或降低的数的特征. 适合人群:对数论猜想有兴趣的人员。 能学到...
指数为1的项略去指数1,如3x。 (3)多项式a和b相加,建立多项式a+b。 (4)多项式a和b相减,建立多项式a-b。 【测试数据】 (1)(2x+5x8-3.1x11)+(7-5x8+11x9) = (-3.1x11+11x9+2x+7) (2)(6x-3-x+4.4x2-1.2x9)-(-...
设有一元多项式Am(x)和Bn(x),Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm,Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn,请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。 分别采用顺序和链式存储结构实现;结果...
x年出生的母牛从第x+m年开始到第x+n年止(含, 1 )每年生小母牛一头,并在第x+p(n )年被淘汰。设第0年有刚出生的小母牛一头,求第k(k > 0)年存栏母牛多少头。 【输入形式】 从标准输入上顺序读入正整数m、n、p、k...
关于qx+1问题高度的探讨,蒋愉,吴栋梁,Collatz问题,也称为3x+1问题,从上个世纪开始就一直被众多学者所关注和研究。到目前为止,已经有了很多不错的结果。本文将主要探讨q
1) 问题描述 已知A(x)=a0+a1x+a2x2+……+anxn和B(x)=b0+b1x+b2x2+……+bmxm,并且在A(x)和B(x)中指数相差很多,求A(x)=A(x)*B(x)。 2) 基本要求 (1)设计存储结构表示一元多项式; (2)设计算法实现一元多项式乘法; ...
有趣的数论名题 作者:周从尧,余未 编著 出版时间:2012年版 内容简介 ...08 3x+1问题的计算程序 09 梅森数的分解程序 10 本书作者解决的费尔马直角三角形问题求解 11 FFT在大数乘法中的应用 参考文献
通常这个东西干脆就不用人名字命名了,免得发生争议,比如“3x+1问题”。扯远了。 个人认为KMP是最没有必要讲的东西,因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等...
特别是在处理形如:S(x) = 1+3x10000+2x20000的多项式时,就要用一长度为20001的线性表来 表示,表中仅有三个非零元素,这种对内存空间的浪费是应当避免的,但是如果只存储非零系数项 则显然必须同时存储相应的指数。...
输出格式:比如多项式A为:A(x)=c1xe1+c2xe2+…+ cmxem, 其中,ci和ei分别为第i项的系数和指数,且各项按指数的升幂排列, 即0≤e1…。多项式B,C类似输出。 注意:系数ci为负数以及系数和指数为1等情况的输出...
子集和问题判定是否存在 S 的一个子集 S1,使得 ∑x∈S1x=c ∑x∈S1x=c。试设计一个解子集和问题的回溯法。对于给定的正整数的集合 S={x1,x2,…,xn }S={x1,x2,…,xn }和正整数 c,编程计算 S 的一个子集S1,...
最佳答案: ∫ln(x+1)dx=∫ln(x+1)d(x+1)=(ln(x+1))(x+1)-∫(x+1) d(ln(x+1)) =(x+1)ln(x+1)-∫((x+1)/(x+1))dx=(x+1)ln(x+... https://www.zybang.com/questio... - 百度快照 不定积分求解ln(x-1)dx_百度作业帮 1个...
调研并寻找一种算法,求函数(式1)的最优解 f(x)=∑_(i=1)^(N-1)▒[100*(x_i^2-x_(i+1) )^2+(1-x_i )^2 ] (式1) x_i∈[-5.12,5.12]
问题描述:设用两个数组表示两个一元稀疏多项式A、B,实现两个一元稀疏多项式的处理。...(1) (2x+5x8-3.1x11)+(7-5x8+11x9) (2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15) (3)(x+x2+x3)+0 (4)(x+x3)-(-x-x-3)
一、802.1x协议起源于802.11协议,后者是标准的无线局域网协议,802.1x协议的主要目的是为了解决无线局域网用户的接入认证问题。现在已经开始被应用于一般的有线LAN的接入。为了对端口加以控制,以实现用户级的接入...
(3)(1 +x + x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) (4)(x+x3)+(-x-x3)=0 (5)(x+x100)+(x100 +x200)=(x+2x100+x200) (6)(x+x2+x3)+0=x+x2+x3 (7) 互换上述测试数据中的前后两个多项式 【实现提示】 用带表头结点的...