UVa 100 3n+1 problem

gogdizzy

题意就是任何一个大于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];
5. uint CalcCyc( uint x )
6. {
7. uint count = 1;
8. while( x > 1 )
9. {
10. if( x<1000000 && tbl[x] ) { count += tbl[x] - 1; break; } // 利用前面结果
11. if( x & 1 ) x += x * 2 + 1 ;
12. else x >>= 1;
13. ++count;
14. }
15. return count;
16. }
18. uint FindMax( uint x, uint y )
19. {
20. if( y < x ){ x^=y; y^=x; x^=y;}
21. uint maxV = tbl[y], idx = y;
22. while( y > x ){
23. if( tbl[x] > maxV ) maxV = tbl[x], idx = x;
24. x++;
25. }
26. return idx;
27. }
29. int main()
30. {
31. uint i, j;
32. for( i = 1; i < 1000000; i++) tbl[i] = CalcCyc(i);
33. //for( i = 1; i < 150; i++) printf("%u %u\t",i, tbl[i]);
35. for(; ~scanf("%u%u",&i, &j );) printf("%u %u %u\n",i,j,FindMax(i,j));
36. return 0;
37. }

复制代码

qianyb

只用0.000s的区间是多大呢

gogdizzy

只用0.000s的区间是多大呢 qianyb 发表于 2010-2-5 17:28

多谢关注！ 测试数据我也不清楚，i，j的取值范围是1-1,000,000

northwolves

当时我做这道题是查表法：http://www.research.att.com/~njas/sequences/A006877

northwolves

按：http://www.research.att.com/~njas/sequences/b006877.txt 10^16内最长链发生在：7579309213675935

northwolves

感觉倒着来好一些。 http://mathworld.wolfram.com/CollatzProblem.html

无心人

7579309213675935？ 减3，除以2^i 减3，除以2^i 减3，除以2^i 减3，除以2^i ......

gogdizzy

现在知道了，这其实是RMQ问题，可以通过预处理，每次查询用O(1)时间。 http://community.topcoder.com/tc ... owestCommonAncestor