113383会出问题~

调试中~~~

注要是会有数据溢出现象~~~

[此贴子已经被作者于2017-3-12 22:44编辑过]

这代码可以通过那个测试~~

#include<stdio.h>
#include<conio.h>
int main()
{
    unsigned int n=0;
    int i=0;

    scanf("%u",&n);

    while (n!=1)
    {
        if (n%2==0)
            n/=2;
        else
            n=n*3+1;
        ++i;
        printf("%u %d\n",n,i);
        getch();
    }
    return 0;
}

可以改进一下~

用数组保存数据~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 5000000

int a[MAX]={0};

void initlize();

void print();

int Count(unsigned _int64 n);

int main()
{
     unsigned _int64 i=0;
     unsigned _int64 j=0;
     unsigned _int64 temp=0;

     unsigned _int64 p=0;
     unsigned _int64 maxnumber=0;

     int sum=0;
     int max=0;

     initlize();

    while(scanf("%I64d%I64d",&i,&j) == 2 && (i != 0 && j != 0))
    {
        if(i > j)//i比j大，交换一下
        {
            temp = i;
            i = j;
            j = temp;
        }

        sum = 0;
        max = 0;

        for(p = i; p <= j; p++)
        {
            sum =Count(p);

            if(sum > max)
            {
                max=sum;
                maxnumber = p;
            }

        }

        printf("Between %I64d and %I64d,", i, j);
        printf("%I64d generates the longest sequence of %d values.\n",maxnumber,max);
    }


    return 0;
}

void initlize()
{
    int i=0;
    unsigned _int64 j=0;

    int count=0;

    memset(a,0,sizeof(a));

    for (i=2;i<MAX;++i)
    {
        for (j=i,count=0;j!=1;++count)
        {
            if (j<MAX&&a[j]!=0)
            {
                a[i]=a[j]+count;

                break;
            }

            if ((j&1)==0)
                j>>=1;
            else
                j=j*3+1;

        }


        if (a[i]==0)
            a[i]=count;
    }
}

int Count(unsigned _int64 n)
{
    int i=0;

    if (n<MAX)
        return a[n];

    while(n>=MAX)
    {
        if((n&1)==0)
            n>>=1;
        else
            n = n*3 + 1;
        i++;
    }

    return i+a[n];
}

[此贴子已经被作者于2017-3-13 00:31编辑过]

漂亮，有些计算重复了，给你改了改。

#include <stdio.h>

#define M 1000001

int ss[M] = {0};

int fun(long long n)
{
    if (1 == n || n < M && ss[n]) return ss[n];

    int tmp = n % 2 ? fun(n * 3 + 1) : fun(n / 2);

    if (n < M) ss[n] = tmp + 1;

    return tmp + 1;
}

int main()
{
    int l, h, v, s, tmp;

    for (int i = 1; i < M; ++i) fun(i);

    while (2 == scanf("%d%d", &l, &h) && l && h)
    {
        s = 0, v = l;
        if (l > h) tmp = l, l = h, h = tmp;
        for (int i = l; i <= h; ++i) if (s < ss[i]) s = ss[i], v = i;
        printf("Between %d and %d, %d generates the longest sequence of %d values.\n", l, h, v, s);
    }
    return 0;


    return 0;
}

[此贴子已经被作者于2017-3-13 10:11编辑过]

收到的鲜花

• 九转星河 于 2017-03-13 11:44 送鲜花  10朵   附言：好文章

路过学习下

不好意思，我觉得改来改去在算法复杂度上似乎没有减少。九版的改法不过是把小于5000000的数提前算了，但如果是个小数字呢，这不反而提高了复杂度？
azz老大也不过是把循环改为了递归,计数改为反向，实际循环次数并没有减少，不知道还会不会超时。
我说实话，大家不要见怪!

a版的方法采取递归尽量避免了重复计算~执行效率较高~这个可以肯定~可以考虑边读取测试数据边建表~建表做功省不了~但边计算测试数据边建表这样可以提高表的利用率~


上楼试过运行程序没有？~a版的算法建表速度远远小于1s~难道你以为真的和for (p=i;p<l;++p)这样的非数组循环遍历效率等效的么？~所以如果数据不是大于1000000~那该算法每次执行运算就可以远远小于1s~我也是实话实说~

[此贴子已经被作者于2017-3-13 12:52编辑过]

哦，刚才我看错了，azz版也和你一样，是提前把1000001以内的数算出来存到数组ss[M]中
和原作者比，多了这么一个大的循环。
for (int i = 1; i < M; ++i) fun(i);
你输入100以内的两个数和原作者比比，谁的运算速度快。

数据太小~几乎都为0s~~~~~~测试不出来~

你说得对，你们的方法可以避免重复计算。不过我认为这样的算法更好：
比如我算10－99之间的数，先计算10，那么就要把10存入数组，再算11，就把11存入数组，边算边添加数组元素。
后面计算的数计算到已存在的数组元素就直接加，也许这样是最好的算法。

[此贴子已经被作者于2017-3-13 13:05编辑过]