-5

問題 : 数列を生成する次のアルゴリズムを考えてみましょう。整数 n で開始します。n が偶数の場合、2 で割ります。n が奇数の場合、3 を掛けて 1 を加算します。n の新しい値でこのプロセスを繰り返し、n = 1 で終了します。入力は、整数 i と i の一連のペアで構成されます。 j、1 行あたり 1 組の整数。すべての整数は 1,000,000 未満で 0 より大きくなります。入力整数 i と j の各ペアについて、i と j を入力に現れた順序で出力し、i と i を含む整数の最大サイクル長を出力します。 j. これら 3 つの数値は 1 つのスペースで区切られ、3 つの数値すべてが 1 行に表示され、入力の各行に対して 1 行の出力が表示されます。

サンプル入力:

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

in1を下回ることはまったくできないため、無限ループなどはありません（そのためには、すでに1である必要があります）。

よろしくお願いします

4

2 に答える 2

1

あなたが私に言ったように、それは単純なオーバーフローの問題でした。

max 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 に答える
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 に答える