问题 A: The 3n + 1 problem
时间限制: 1 Sec  内存限制: 16 MB
提交: 3488  解决: 741
[提交][状态][讨论版]
题目描述

计算机科学中的问题往往被归纳为某一类问题（如NP问题，无法解决问题，递归等）。在这道问题中你将分析一种算法，它对所有可能的输入结果是未知的。

考虑以下算法：
   1. 输入n
   2. 输出n
   3. 如果n=1然后停止
   4. 如果n是奇数： n <-- n*3+1
   5. 其他的情况：   n <-- n/2
   6. 转向 2

例如：对于输入22，输出将会是22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1。据推测，该算法对于任何整数将终止于1。尽管算法很简单，目前还不清楚这一猜想是否正确。但是对于所有整数n(0<n<1,000,000)，已经过验证（事实上，符合规律的数比这还要多）。

对于给定的n，是有可能计算出该算法共输出了多少个数的，包括结尾的1，这个数叫做n的周期长度。在上面的例子中，22的周期长度是16。对于任何两个数字i和j，求出在i和j之间的数中，周期长度最大的那个数的周期长度。

输入
输入将包括一系列的整数对i和j，每行一对整数。所有整数将少于1000000 且大于0。你应该处理i和j（包括i,j） 之间的所有整数。可以假设，任何操作不会溢出32位整数。
输出
对于每一个对输入整数i和j，输出为i、j和最大周期长度。这三个数用空格分开，三个数在同一行，每两个数之间有一个空格。

样例输入
1 10
100 200
201 210
900 1000
样例输出
1 10 20
100 200 125
201 210 89
900 1000 174
提示

应该把已经计算过的数的周期长度保存下来，超时的原因是已经计算过的周期长度的重复计算，




[i]运行不了
#include <stdio.h>
int main()
{
long int i,m,n,k,a,q,p,max;
int b[1000005];
while(scanf("%d %d",&n,&m)!=EOF)
{
   max=0;
  if(n>m)
  {
      q=n;
      n=m;
      m=q;
  }

 for(a=n;a<=m;a++)
  {   i=1;
      p=a;
      while(p!=1)
      {
       i++;
      if(p%2!=0)
         p=p*3+1;
      else
         p=p/2;
      }
    b[a]=i;
   }
   if(b[a]>max)
    max=b[a];

}
 printf("%d %d %d\n",n,m,max);
return 0;
}





时间超限
#include<stdio.h>
int func(int n)
{
    int count=1;
    while(n!=1)
    {
        if(n%2==0)
            n=n/2;
        else
            n=n*3+1;
        count++;
    }
    return count;
}
int main()
{
    int i,j,max,t;
    while(scanf("%d %d",&i,&j)!=EOF)
    {
       max=func(i);
    for(t=i+1;t<=j;t++)
    {
        if(max<func(t))
            max=func(t);
    }
    printf("%d %d %d\n",i,j,max);

    }
return 0;
}