以下迭代序列定义在整数集合上：
 
n n/2 (当n是偶数时)
 n 3n + 1 (当n是奇数时)
 
应用以上规则，并且以数字13开始，我们得到以下序列：
 
13 40 20 10 5 16 8 4 2 1
 
可以看出这个以13开始以1结束的序列包含10个项。虽然还没有被证明（Collatz问题），但是人们认为在这个规则下，以任何数字开始都会以1结束。
 以哪个不超过100万的数字开始，能给得到最长的序列？
注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过100万的。

又是一个大数计算的，我写的程序直接按照题意求解，电脑算不出来了，求一个高效率的算法



#include <stdio.h>
int main()
{
    __int64 i;
    __int64 j=0;
    int count=0;
    int maxcount=0;
    for(i=3;i<1000000;i++)
    {
        count=0;
        while(1)
        {
            if(i/1==1&&i%1==0)
            {
                break;
            }
            if(i%2==0)
            {
                i/=2;
                ++count;
                continue;
            }
            if(i%2!=0)
            {
                i=3*i+1;
                ++count;
                continue;
            }
        }
        if(count>maxcount)
        {
            maxcount=count;
            j=i;
        }
    }
    printf("%I64d     %d\n",j,maxcount);
    return 0;
}


[ 本帖最后由 tompobing 于 2013-3-27 21:35 编辑 ]

你问题的规模好像都挺大的 你是不是在做什么专题的练习啊？

#include <iostream>
#define Max 1000000
using namespace std;

int f[Max];
long long q[1000];
    
int main()
{
    f[1]=1;
    for (int i=2; i<=1000000; i++)
    if (f[i]==0)
    {
        int end=1; q[1]=i;
        while (q[end]>=Max || f[q[end]]==0)
            {
                if (q[end]%2==0) q[end+1]=q[end]/2; else q[end+1]=q[end]*3+1;
                end++;
            }
            
        int temp=f[q[end]];
        for (int i=end-1; i>=1; i--)
        {
            temp++;
            if (q[i]<Max) f[q[i]]=temp;
        }
    }
    
    int j=1;
    for (int i=2; i<1000000; i++)
        if (f[i]>f[j]) j=i;
    cout<<j<<' '<<f[j]<<endl;
}

应该还是空间换时间吧
有一个事实：在某个数的计算序列中出现的数 他的序列肯定不会比这个数长 毕竟是子序列
所以可以考虑 储存100万个数在其他数的生成序列中的出现情况 出现过的就不用再统计了 最长的肯定不是他
好像跟那个质数的筛选法有点类似 也得用数组保存100万个二进制位

额·······

如果仅仅是计算最长序列长度，如下程序比较简单
#include <stdio.h>
#define N 1000000
main ()
{unsigned long n,m;
 int maxcnt=0,cnt,i;
 for(n=3;n<N;n++)
   {cnt=0;
    m=n;
    while(m!=1)
      {cnt++;
       if(m%2==0)
           m=m/2;
       else
         m=3*m+1;}
    if(cnt>maxcnt)
        maxcnt=cnt;}
 printf("%d\n",maxcnt);
}
云翔结果是524

貌似是程序写的有问题。。。

524
837799 2513398 1256699 3770098 1885049 5655148 2827574 1413787 4241362 2120681 6
362044 3181022 1590511 4771534 2385767 7157302 3578651 10735954 5367977 16103932
 8051966 4025983 12077950 6038975 18116926 9058463 27175390 13587695 40763086 20
381543 61144630 30572315 91716946 45858473 137575420 68787710 34393855 103181566
 51590783 154772350 77386175 232158526 116079263 348237790 174118895 522356686 2
61178343 783535030 391767515 1175302546 587651273 1762953820 881476910 440738455
 1322215366 661107683 1983323050 991661525 -1319982720 1487492288 743746144 3718
73072 185936536 92968268 46484134 23242067 69726202 34863101 104589304 52294652
26147326 13073663 39220990 19610495 58831486 29415743 88247230 44123615 13237084
6 66185423 198556270 99278135 297834406 148917203 446751610 223375805 670127416
335063708 167531854 83765927 251297782 125648891 376946674 188473337 565420012 2
82710006 141355003 424065010 212032505 636097516 318048758 159024379 477073138 2
38536569 715609708 357804854 178902427 536707282 268353641 805060924 402530462 2
01265231 603795694 301897847 905693542 452846771 1358540314 679270157 2037810472
 1018905236 509452618 254726309 764178928 382089464 191044732 95522366 47761183
143283550 71641775 214925326 107462663 322387990 161193995 483581986 241790993 7
25372980 362686490 181343245 544029736 272014868 136007434 68003717 204011152 10
2005576 51002788 25501394 12750697 38252092 19126046 9563023 28689070 14344535 4
3033606 21516803 64550410 32275205 96825616 48412808 24206404 12103202 6051601 1
8154804 9077402 4538701 13616104 6808052 3404026 1702013 5106040 2553020 1276510
 638255 1914766 957383 2872150 1436075 4308226 2154113 6462340 3231170 1615585 4
846756 2423378 1211689 3635068 1817534 908767 2726302 1363151 4089454 2044727 61
34182 3067091 9201274 4600637 13801912 6900956 3450478 1725239 5175718 2587859 7
763578 3881789 11645368 5822684 2911342 1455671 4367014 2183507 6550522 3275261
9825784 4912892 2456446 1228223 3684670 1842335 5527006 2763503 8290510 4145255
12435766 6217883 18653650 9326825 27980476 13990238 6995119 20985358 10492679 31
478038 15739019 47217058 23608529 70825588 35412794 17706397 53119192 26559596 1
3279798 6639899 19919698 9959849 29879548 14939774 7469887 22409662 11204831 336
14494 16807247 50421742 25210871 75632614 37816307 113448922 56724461 170173384
85086692 42543346 21271673 63815020 31907510 15953755 47861266 23930633 71791900
 35895950 17947975 53843926 26921963 80765890 40382945 121148836 60574418 302872
09 90861628 45430814 22715407 68146222 34073111 102219334 51109667 153329002 766
64501 229993504 114996752 57498376 28749188 14374594 7187297 21561892 10780946 5
390473 16171420 8085710 4042855 12128566 6064283 18192850 9096425 27289276 13644
638 6822319 20466958 10233479 30700438 15350219 46050658 23025329 69075988 34537
994 17268997 51806992 25903496 12951748 6475874 3237937 9713812 4856906 2428453
7285360 3642680 1821340 910670 455335 1366006 683003 2049010 1024505 3073516 153
6758 768379 2305138 1152569 3457708 1728854 864427 2593282 1296641 3889924 19449
62 972481 2917444 1458722 729361 2188084 1094042 547021 1641064 820532 410266 20
5133 615400 307700 153850 76925 230776 115388 57694 28847 86542 43271 129814 649
07 194722 97361 292084 146042 73021 219064 109532 54766 27383 82150 41075 123226
 61613 184840 92420 46210 23105 69316 34658 17329 51988 25994 12997 38992 19496
9748 4874 2437 7312 3656 1828 914 457 1372 686 343 1030 515 1546 773 2320 1160 5
80 290 145 436 218 109 328 164 82 41 124 62 31 94 47 142 71 214 107 322 161 484
242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 3
95 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1
276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 27
34 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 97
6 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 这是运行结果