0

次の方程式を解く必要があるとします。

ax + by = c

ここaで、b、 、cは既知の値でx、 、yは 0 から 10 までの自然数 (両端を含む) です。

の些細な解決策以外に、

for (x = 0; x <= 10; x++)
    for (y = 0; y <= 10; y++)
         if (a * x + b * y == c)
             printf("%d %d", x, y);

... この独立したシステムのすべてのソリューションを効率的に見つける方法はありますか?

4

3 に答える 3

3

あなたの場合、xとの間のy値しかとらないため、ブルート フォース アルゴリズムは実装に時間がかからないため、おそらく最良のオプションです。010

ただし、より広い範囲で積分解のすべてのペアを見つける必要が(x, y)ある場合は、この問題に取り組むための適切な数学的ツールを実際に適用する必要があります。

線形ディオファントス方程式を解こうとしており、 と の最大公約数dがaをb割るc場合にのみ積分解が存在することはよく知られています。

解決策が存在しない場合は、完了です。それ以外の場合は、最初に拡張ユークリッド アルゴリズムを適用して、方程式 の特定の解を見つける必要がありますax + by = d。

また、ベズーの恒等式によると、他のすべての積分解は次の形式になります。

http://upload.wikimedia.org/math/8/6/9/869734595b839cf44b8a1cb01607580f.png

はk任意の整数です。

ただし、 の解に関心があることに注意してください。ax + by = cのすべてのペアを(x, y)の係数でスケーリングする必要がありc / dます。

于 2015-02-25T06:26:34.187 に答える
0

x をループしてから y を計算するだけです。(x, y) は、y が整数で、0 から 10 の間の場合の解です。

C:

for (int x = 0; x <= 10; ++x) {
    double y = (double)(c - ax) / b;
    // If y is an integer, and it's between 0 and 10, then (x, y) is a solution
    BOOL isInteger = abs(floor(y) - y) < 0.001;
    if (isInteger && 0 <= y && y <= 10) {
        printf("%d %d", x, y);
    }
}
于 2015-02-25T05:52:07.453 に答える
0

が整数forかどうかを直接確認することで、2 番目のループを回避できます。(c-a*x)/b

編集:私のコードは、コメントで指摘された不注意な見落としのために、私が望んでいたよりもクリーンではありませんが、ネストされたforループよりも高速です。

int by;
for (x = 0; x <= 10; x++) {
    by = c-a*x;                         // this is b*y

    if(b==0) {                          // check for special case of b==0
        if (by==0) {
            printf("%d and any value for y", x);
        }
    } else {                            // b!=0 case
        y  = by/b;                  
        if (by%b==0 && 0<=y && y<=10) { // is y an integer between 0 and 10?
            printf("%d %d", x, by/b);
        }
    }
}
于 2015-02-25T05:51:51.513 に答える