1

簡単な質問です。問題は、次のような整数多項式を解くことです: x+y+z=num、および x、y、z の int 値は、次のようになるはずです: X1<=x<=X2, Y1<=y< =Y2, Z1<=z<=Z2 の場合、その式を満たす x、y、z の組み合わせがいくつあるかを調べます。これよりも効率的なアルゴリズムがあるかもしれません:

for(int i=X1;i<=X2;i++)
    for(int j=Y1;j<=Y2;j++)
        for(int k=Z1;k<=Z1;k++)
            if(i+j+z==num)
                print i,j,k;

私はコードを求めているのではなく、アイデアを求めています。役立つ情報を提供してくれる人に感謝します！

4

1 に答える 1

1

アルゴリズムは O((X2-X1)(Y2-Y1)(Z2-Z1)) 時間で実行されます。

より高速にするために、合計が num よりも大きいかどうかをチェックすることができます。大きい場合は、現在のループから飛び出して、次に大きいループをインクリメントすることができます。たとえば、Y ループは次のように読み取ることができます。

for(int j = Y1; j <= Y2; j++){
    if(i + j > num){
          j = Y2;
          continue;
    }
    for ( int k = Z1;...){...}
}

これにより、アルゴリズムが num より大きいいくつかの組み合わせをテストできなくなり、実行時間が改善されます。これまでに定義された変数のみを含め、3 つのループすべてに対してこれを実行できることに注意してください (k は 3 番目のループまで定義されていないため、この例では k をテストしません)。

于 2012-09-07T03:08:23.430 に答える