论坛 › 算法交流 › UVa 100 3n+1 problem

gogdizzy 发表于 2010-2-5 16:39:00

UVa 100 3n+1 problem

题意就是任何一个大于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，想问问应该如何提高速度呢？是否有数学公式能够简化计算呢？#include <stdio.h>
typedef   unsigned int      uint;
uint tbl;

uint CalcCyc( uint x )
{
        uint count = 1;
        while( x > 1 )
        {
                if( x<1000000 && tbl ) { count += tbl - 1; break; }// 利用前面结果
                if( x & 1 ) x += x * 2 + 1 ;
                else x >>= 1;
                ++count;
        }
        return count;
}

uint FindMax( uint x, uint y )
{
        if( y < x ){ x^=y; y^=x; x^=y;}
        uint maxV = tbl, idx = y;
        while( y > x ){
                if( tbl > maxV ) maxV = tbl, idx = x;
                x++;
        }
        return idx;
}

int main()
{
        uint i, j;
        for( i = 1; i < 1000000; i++) tbl = CalcCyc(i);
        //for( i = 1; i < 150; i++) printf("%u %u\t",i, tbl);

        for(; ~scanf("%u%u",&i, &j );) printf("%u %u %u\n",i,j,FindMax(i,j));
        return 0;
}

qianyb 发表于 2010-2-5 17:28:46

只用0.000s的区间是多大呢

gogdizzy 发表于 2010-2-5 17:36:58

只用0.000s的区间是多大呢
qianyb 发表于 2010-2-5 17:28 http://bbs.emath.ac.cn/images/common/back.gif


多谢关注！

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

northwolves 发表于 2010-2-5 23:02:49

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

northwolves 发表于 2010-2-5 23:05:13

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

northwolves 发表于 2010-2-6 00:23:30

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

无心人 发表于 2010-2-11 22:30:43

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

gogdizzy 发表于 2013-6-24 10:40:43

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

查看完整版本: UVa 100 3n+1 problem