-5

问题：考虑以下算法来生成数字序列。从整数 n 开始。如果 n 为偶数，则除以 2。如果 n 为奇数，则乘以 3 并加 1。使用新的 n 值重复此过程，当 n = 1 时终止。输入将由一系列整数对组成 i 和j，每行一对整数。所有整数都将小于 1,000,000 且大于 0。对于每对输入整数 i 和 j，按照它们在输入中出现的相同顺序输出 i、j，然后是介于 i 和包括 i 和j. 这三个数字应该用一个空格分隔，所有三个数字都在一行上，每行输入对应一行输出。

样本输入：

1 10

样本输出：

1 10 20

所以我写了这个：

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

struct line{int in1;int in2;int result;};

int cycle(int in);

int main(int argc, char *argv[]) {
    int cycle(int in);
    char c;
    int firstIn=0;
    struct line l[500] ;
    int pointer=0;

    while(2<3){
        l[pointer].in1=0;
        l[pointer].in2=0;
        scanf("%u %u",&l[pointer].in1,&l[pointer].in2);
        if(l[pointer].in1<1||l[pointer].in2<1){
            break;
        }

        int maxCyc=0;
        int j,m;
        int min,max;
        if(l[pointer].in1>l[pointer].in2){
            max=l[pointer].in1;
            min=l[pointer].in2;
        }
        else{
            max=l[pointer].in2;
            min=l[pointer].in1;
        }
        for(j=min;j<=max;j++){

            m = cycle(j);
            if(m>maxCyc)
                maxCyc=m;
        }
        l[pointer].result=maxCyc;
        printf("%d %d %d\n",l[pointer].in1,l[pointer].in2,l[pointer].result);
        pointer++;
    }
}

int cycle(int in){
    int cyc = 1;
    while(in>1){
        if(in%2==0){
            cyc++;
            in=in/2;
        }
        else{
            cyc++;
            in=in*3+1;
        }
    }
    return cyc;
}

它完全可以，但是当您更改while(in>1)循环方法时，while(in!=1)它会变得更慢。我的问题是为什么？！

时间while(in>1)：0.683 秒

当它的时候while(in!=1)：我等了超过 5 分钟还没有发生任何事情:)

输入：1 1000000

没有无限循环或其他东西，因为根本in不能低于 1（因为它必须已经是 1）。

此致

4

2 回答 2

1

当你cycle用输入值调用时113383，进程最终设置n为827370449，3*827370449+1为2482111348，大于最大值signed int，解释为-1812855948。所以你的第一个负数应该没有负数。

如果此过程最终设置n为 -2，则从那时起它将在 -2 和 -1 之间无限循环。可能还有其他我没有考虑过的循环。

如果您要使用 unsigned int，则有可能（我尚未检查）这最终也会溢出，这不会导致负值但会导致错误的值，从而使您的结果无效。

无论您使用哪种整数表示，最好在每个循环的顶部进行比较，其中n是您的整数类型的最大可能正值，以确保您不会溢出。(maximum-1)/3maximum

于 2014-07-16T12:09:23.307 回答
1

正如你告诉我的，这是一个简单的溢出问题，谢谢大家。

最大 int 值是2,147,483,647;所以当我更改int cycle(int in)为int cycle(long long int in)我的问题时解决了。

我还发现我的第一个答案while(in>1)是错误的。

当发生整数溢出时，该值将低于 0 。这就是while(in!=1)无限循环的原因。

我真的很累，我自己没有弄清楚。对此感到抱歉:)

于 2014-07-16T11:51:30.517 回答