2011年南海初中竞赛 奇怪数例

发布于 2019-04-17  897 次阅读


思路

模拟出结果就可以了
但是要记忆化,如果之前做过的话就直接用,不然会超时

#include <stdio.h>
using namespace std;
int f[3000005];
int main()
{
    int t=0,x,y,max=0,min=0x7fffffff;
    long long n;
    scanf("%d%d",&x,&y);

    for (int i=x;i<=y;i++)
    {
        t=0;
        n=i;
        if (n==1) 
        {
            t=1;
            if (t>max) max=t;
            if (t<min) min=t;
            continue;
        }
        do 
        {
            if (n<3000000)
            if (f[n]!=0)
            {
                t=f[n]+t;
                break;
            }
            if (n%2==1)
                n=n*3+1;
            else n=n/2;
            t++;
        }
        while (n>1);
        f[i]=t;
        t++;
        if (t>max) max=t;
        if (t<min) min=t;
    }
    printf("%d %d",min,max);
}