找回密码
 欢迎注册
查看: 8556|回复: 7

[原创] UVa 100 3n+1 problem

[复制链接]
发表于 2010-2-5 16:39:00 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
题意就是任何一个大于1的整数x都可以通过变换

while(x != 1){
如果是奇数,那么x=3x+1;
否则x=x/2;
}

最后得到1.设循环次数为A_x

题目要求是任给两个数i,j,计算区间中A的最大值。

我的做法是先将所有的A计算出来,存成表,然后每次i,j,就从表的区间内顺序查找最大值。

我的表没做任何处理,就是线性查找。用时0.465s。

后来将生成表的方式改进,利用前面结果,用时0.060s

我看有人用时0.000s,想问问应该如何提高速度呢?是否有数学公式能够简化计算呢?
  1. #include <stdio.h>
  2. typedef   unsigned int        uint;
  3. uint tbl[1000000];

  4. uint CalcCyc( uint x )
  5. {
  6.         uint count = 1;
  7.         while( x > 1 )
  8.         {
  9.                 if( x<1000000 && tbl[x] ) { count += tbl[x] - 1; break; }  // 利用前面结果
  10.                 if( x & 1 ) x += x * 2 + 1 ;
  11.                 else x >>= 1;
  12.                 ++count;
  13.         }
  14.         return count;
  15. }

  16. uint FindMax( uint x, uint y )
  17. {
  18.         if( y < x ){ x^=y; y^=x; x^=y;}
  19.         uint maxV = tbl[y], idx = y;
  20.         while( y > x ){
  21.                 if( tbl[x] > maxV ) maxV = tbl[x], idx = x;
  22.                 x++;
  23.         }
  24.         return idx;
  25. }

  26. int main()
  27. {
  28.         uint i, j;
  29.         for( i = 1; i < 1000000; i++) tbl[i] = CalcCyc(i);
  30.         //for( i = 1; i < 150; i++) printf("%u %u\t",i, tbl[i]);

  31.         for(; ~scanf("%u%u",&i, &j );) printf("%u %u %u\n",i,j,FindMax(i,j));
  32.         return 0;
  33. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-2-5 17:28:46 | 显示全部楼层
只用0.000s的区间是多大呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-2-5 17:36:58 | 显示全部楼层
只用0.000s的区间是多大呢
qianyb 发表于 2010-2-5 17:28



多谢关注!

测试数据我也不清楚,i,j的取值范围是1-1,000,000
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-2-5 23:02:49 | 显示全部楼层
当时我做这道题是查表法:http://www.research.att.com/~njas/sequences/A006877
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-2-5 23:05:13 | 显示全部楼层
按:http://www.research.att.com/~njas/sequences/b006877.txt
10^16内最长链发生在:7579309213675935
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-2-6 00:23:30 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-2-11 22:30:43 | 显示全部楼层
7579309213675935?
减3,除以2^i
减3,除以2^i
减3,除以2^i
减3,除以2^i
......
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-6-24 10:40:43 | 显示全部楼层
现在知道了,这其实是RMQ问题,可以通过预处理,每次查询用O(1)时间。
http://community.topcoder.com/tc ... owestCommonAncestor
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 17:35 , Processed in 0.044547 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表