13

次の形式の簡単な方程式があるとします。

7x + 4y = n

ここで、nは私たちが選択し、x、y、nはすべて正の整数です。これは私たちに与えられる唯一の方程式です。可能な解決策の中で、xが最小である解決策（x、y）が必要です。例えば

7x + 4y = 14, then (2, 0) is the solution
7x + 4y = 15, then (1, 2) is the solution
7x + 4y = 32, then (4, 1) and (0, 8) are the possible solutions,
of which (0, 8) is the correct solution

最短の実行時間で計算するアルゴリズムを設計したいと思います。私が念頭に置いている現在のアルゴリズムは次のようになります。

Given an input n
Calculate max(x) = n/7
for i = 0 to max(x)
    If the equation 7*i + 4*y = n holds
        return value of i and y
    else
        continue

このアルゴリズムは、最悪の場合の動作で最大O（n）の実行時間を有する可能性があると私は推測します。解を計算するためのより良いアルゴリズムはありますか？

4

4 に答える 4

7

より一般的な問題を考えてみましょう

  • 2つの互いに素な正の整数aとb、が与えられた正の整数について、が最小になるような非負の整数nのペアを見つけます。（存在する場合。存在する必要はありません。たとえば、非負の解はありません。）(x,y)a*x + b*y = nx7*x + 4*y = 5xy

解決策を考えれば、今のところ非否定性を無視する

a*x0 + b*y0 = n

すべての解は、(x0 - k*b, y0 + k*a)ある整数の形式を持っていkます。したがって、xモジュロbとyモジュロの剰余aは解の不変量であり、次のようになります。

a*x ≡ n (mod b), and b*y ≡ n (mod a)

したがって、方程式を解く必要がありa*x ≡ n (mod b)ます。もう1つは次のとおりです。

を含む整数0 < cとしa*c ≡ 1 (mod b)ます。a/bたとえば、拡張ユークリッドアルゴリズム、または（同等に） O（log b）ステップの連分数展開によってそれを見つけることができます。どちらのアルゴリズムも、当然c < b、そのプロパティを使用して一意のアルゴリズムを生成します。

その場合、の最小候補xはモジュロの剰余x0です。n*cb

この問題には、非負の解があり、がの場合に限り、非負xとの解に現れる最小の非負です。yx0*a <= nx0xxy

もちろん、7や4のような小さいa場合b、ブルートフォースはaモジュロの逆数を計算するよりも遅くはありませんb。

于 2012-05-03T14:05:28.960 に答える
6

我々は持っています

7(x-4)+4(y+7)=7x+4y

したがって、（x、y）が解である場合、（x-4、y + 7）も解です。したがって、解がある場合は、x<4の解があります。そのため、一定時間で実行されるx=0..3のみをテストする必要があります。

これは、ax + by = nの形式の任意の方程式に拡張でき、x=0..b-1をテストするだけで済みます。

于 2012-05-03T13:45:08.063 に答える
2

C本の数値レシピのシンプレックス法をチェックすることをお勧めします。Cコードを擬似コードのように簡単に扱い、Javaバージョンを作成できます。必要なシンプレックスのバージョンは、正の値のみを扱う「制約付きシンプレックス」です。この本はオンラインで無料で入手できます。セクション10.8から始めて、先に読んでください。

于 2012-05-03T14:05:04.873 に答える
1

の上） ：

y=n/4;
while((n-4y)%7!=0 && y!=0){
 y--;
}
x=(n-4y)/7;
于 2012-05-03T13:55:57.580 に答える