6

3n1 + 4n2 + 5n3 = 456のような方程式の解があるかどうかを判断する方法を探してい ます。ここで、n1、n2、n3は正の整数です。

またはより一般的に：方程式k1n1 + k2n2 + k3n3 ... = mを解くゼロまたは正の整数n1、n2、n3 ...があります。ここで、k1、k2、k3 ...およびmは既知の正の整数です。

解決策を見つける必要はありません。解決策が存在するかどうかを判断するためだけです。

編集：

このアルゴリズムの実用化について：

通信ライブラリでは、メッセージを処理する前に、特定のメッセージがそのサイズに応じて有効かどうかを判断したいと思います。例：メッセージに0個以上の3バイト要素、0個以上の4バイト要素、および0個以上の5バイト要素が含まれていることを知っています。456バイトのメッセージを受信しましたが、内容をさらに調べる前に、その有効性を確認したいと思います。もちろん、メッセージのヘッダーには各タイプの要素の数が含まれていますが、.のようなものを渡すことによって、通信ライブラリレベルで最初の検査を行いたいと思いpair<MsgType,vector<3,4,5>>ます。

4

7 に答える 7

16

あなたは正規表現かどうか尋ねています

（xxx | xxxxx | xxxxx）*

xx ... xに一致します。ここで、xは456回発生します。

これがO（n + a ^ 2）の解です。ここで、aは左側の数値の最小値（この場合は3）です。

あなたの番号が6、7、15であると仮定します。6x + 7y+15zの形式で表現できる番号を「利用可能」と呼びます。指定された番号が利用可能かどうかを確認する必要があります。

あなたがいくつかの数nを得ることができれば、確かにあなたはn + 6、n + 12、n + 18を得ることができるでしょう-一般的に、すべてのk>=0に対してn+6k。いくつかの数nを取得できない場合、n-6も確実に使用できません（（n-6）を取得できれば、（n-6）+ 6 = nが使用可能になります）。これは、n-12を意味します。 n-18、n-6kも利用できません。

15が使用可能であるが、9は使用できないと判断したとします。私たちの場合、15 = 6 * 0 + 7 * 0 + 15 * 1ですが、9を取得することはできません。したがって、以前の推論では、すべてのk>=0に対して15+6kが使用可能であり、すべてのk>=0に対して9-6kは使用できません。6で割った数が余りとして3になる場合（3、9、15、21、...）、すぐに答えることができます。数<= 9は使用できず、数>=15は使用できます。

6による除算のすべての可能な余り（つまり、0、1、2、3、4、5）について、使用可能な最小の数を決定するだけで十分です。（残りの3のこの数が15であることを示しました）。

方法：頂点0、1、2、3、4、5でグラフを作成します。与えられたすべての数kについて（7,15-6は無視します）xから（x + k）mod 6にエッジを追加します。それに重み（x + k）divを与えます。6。初期値として0を使用してダイクストラのアルゴリズムを使用します。ノード。アルゴリズムによって検出された距離は、まさに私たちが探している数値になります。

私たちの場合（6,7,15）、数値7は0-> 1（重み1）、1-> 2（重み1）、2-> 3（重み1）、...、5->を生成します。 0（重み1）および数値15は、0-> 3（重み2）、1-> 4（重み2）、...、5-> 1（重み2）を示します。0から3までの最短経路には1つのエッジがあり、その重みは2です。したがって、6 * 2 + 3 = 15は、余りとして3を与える最小の数値です。6 * 1 + 3 = 9は使用できません（以前は手動で確認しました）。

そして、正規表現との関係は何ですか？さて、すべての正規表現には同等の有限オートマトンがあり、私はそれらの1つを構築しました。

複数のクエリが許可されているこの問題は、ポーランドのオリンピックで発生し、私は解決策を翻訳しました。さて、コンピュータサイエンスは実際のプログラマーには役に立たないと言う人を聞いたら、彼に顔を向けてください。

于 2009-09-24T13:19:32.013 に答える
3

これによると、{n1, n2, n3, ...} の最大公約数が m の約数でない場合、解はありません。このページでは {n1, n2} のみの例を示していますが、これはより大きなシステムにも拡張されています。新しい問題は、最大公約数を見つけるためのアルゴリズムを作成することですが、元の問題に照らして考えると、それは些細なことです。

したがって、アルゴリズムの一部は gcf({n1,n2,...}) を見つけて、それが m の因数であるかどうかを確認します。そうでない場合、解決策は存在しません。これは解決策が存在することを完全に示しているわけではありませんが、解決策が存在しないことをすぐに示すことができます。これは依然として有用です。

于 2009-09-23T19:06:03.307 に答える
2

整数制約のある不等式のシステムについて話しているように見えます。現実はあなたがこのシステムのために解決しているということです：

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

そして、n1、n2、n3が整数であるという追加の制約。これは線形計画問題です。残念ながら、整数制約を使用してこのようなシステムを解く一般的なケースはNP完全です。ただし、それを解決するアルゴリズムはたくさんあります。

于 2009-09-23T18:58:35.733 に答える
2

これは、n>3 で解決されていないフロベニウス コイン問題に関連しています。

于 2009-09-24T11:48:58.233 に答える
1

これが2つの数字の場合のことです。私はそれをスケーリングする方法をまだ理解していません：

2つの互いに素な整数xとyが与えられるとax+by=c、すべてに対して正の整数aとbが存在します。c>=(x-1)(y-1)

基本的に、これは機能します。なぜなら、と仮定するとx<y、すべての整数mod xを（0、y、2y、3y、...、（x-1）y）で表すことができるからです。ここで、xの正の倍数を追加することにより、[（x-1）（y-1）、（x-1）y]の間のすべての整数に到達できます。これは、（x-1）（y- 1）および（x-1）y-1は以前に表現されていました。

  1. GCD（x、y）。cが倍数でない場合は、falseを返します。
  2. GCD（x、y）> 1の場合、x、y、cをGCDで除算します
  3. c>（x-1）（y-1）の場合、trueを返します
  4. それ以外のブルートフォース

そして力任せに：

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false
于 2009-09-23T23:46:44.387 に答える
1

ブルートフォースアプローチ（疑似コード）：

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

http://mail.python.org/pipermail/python-list/2000-April/031714.htmlも参照してください。

編集:通信ライブラリでは、すぐに機能する必要があるため、これは意味がありません。OPのアプリケーションでは、おそらく何らかのハッシュを使用するでしょうが、彼のアプローチは興味深いようです。

于 2009-09-23T19:01:49.237 に答える
1

一般的な状況を扱っていないため、次の情報は関係ないかもしれませんが...

3*n1 + 4*n2 + 5*n3問題が、与えられた正の整数 K が非負の整数 n1、n2、n3の sum として形成できるかどうかを判断することである場合、 K >= 3 の場合、答えは「はい」です。

Rosen の有名な教科書Discrete Mathematics and its Applications、p. 第 6 版の 287 は、誘導を使用して、「12 セント以上の郵便料金はすべて、4 セントと 5 セントの切手だけで作成できる」ことを証明しています。

基本的なステップは、12 セントの郵便料金は 3 つの 4 セント切手で形成できるということです。

誘導ステップでは、4 セント スタンプを使用して P(k) が真である場合、4 セント スタンプを 5 セント スタンプに置き換えるだけで、P(k+1) が真であることを示すことができます。4 セント スタンプを使用せずに P(k) が真である場合、k>=12 であるため、合計を計算するには少なくとも 3 つの 5 セント スタンプが必要であり、3 つの 5 セント スタンプは 4 つの 4 セント スタンプに置き換えることができます。 k+1を達成するためのスタンプ。

この問題に対して上記のソリューションを拡張するには、さらにいくつかのケースを検討するだけで済みます。

于 2009-09-25T19:30:25.760 に答える