5

試験の準備中に試験の質問に出くわしましたが、行き詰まっています。質問は：

正の整数Xのセットが与えられた場合に、方程式x 5 + xy --y 2 = y3がxとyの両方がXに属する解を持つかどうかを決定するアルゴリズムを設計します。

プログラミングは必要ありません。アルゴリズムの設計だけです。誰かが彼らのアイデアを共有してもらえますか？

ブルートフォースは受け入れられません

4

4 に答える 4

2

擬似コード:

result = false
foreach (x in X) {
    foreach (y in X) {
        if (x^5 + x*y - y^2 == y^3) result = true
    }
}

これは予想以上に洗練されたものですか？もしそうなら、次のような高次項を利用することができますx^5:

Sort X as a list from least to greatest.
result = false
foreach (y in X) {
    v = y*y*(y+1)
    foreach (x in X) {
        x2 = x*x
        u = x2*x2 + x*y - v
        if (u == 0) {
            result = true
            goto [DONE]
        }
        if (u > 0) goto [NEXT]
    }
    [NEXT]
}
[DONE]
于 2012-04-25T02:37:23.613 に答える
2

（本当に！）大きな入力の場合、次のことができます。

  1. リストを並べ替えます。
  2. 式を使用して、各数値の 3 次方程式を解きます。ここで、各数を とxすると、方程式は の 3 次方程式になりy、公式が適用されます。ただし、この式には非常に時間がかかる場合があり、精度の問題を回避するために、答えをプラグインして確認することができます。次に、ソートされたリスト (O(logn)) に対してバイナリ検索を実行します。

これは漸近的に O(nlogn) になりますが、一定の係数は恐ろしく、大きなああによってうまく隠されています (まあ、プログラムをコーディングするのではなく、質問に答えているのであれば)。もちろん、ハッシュ化が許可されている場合 (通常は面接の場合ですが、試験の場合は必ずしもそうではありません)、これは O(n) になる可能性があります。

于 2012-04-25T02:39:44.093 に答える
2

x の関数として y を解く: http://www.wolframalpha.com/input/?i=x%5E5%2B+xy+-+y%5E2+-+y%5E3

y(x) := INSERT_EQUATION_HERE
any((y in setX) for y in y(x) for x in setX)

これには、O(|X|)、つまり線形の時間がかかります。

または、関数またはリスト操作で言語を使用していない場合はany、ソリューションをもう少し冗長にする必要があります。

for x in setX:
    possibleYs = solveForY(x)
    for y in possibleYs:
        if y in setX:
            return SOLUTION:(x,y)
return NO_SOLUTION

上で示したように、実際に 2D 多項式を解く必要はありません。代わりに、セット内の各 x を考慮することができます。これは x を修正し、y の多項式を与えます。次に、その多項式を一定の時間で解きます。たとえば、x=0 の場合、y^2==y^3 の 3 つの解が見つかります。x=1 の場合、2-y^2==y^3 の 3 つの解を見つけます。x=-0.52 の場合、等々。解はhttp://en.wikipedia.org/wiki/です。 Cubic_function#General_formula_of_roots

問題のより一般的なバージョン:

任意の多項式を考慮する場合、このメソッドは次の場合に O(1) 効率しか提供できないことに注意してください: min(max_x_degree, max_y_degree)<5. これは、ガロア理論で証明されているように、特定の閉じた形式の解を持つ多項式のみが次数 4 以下の多項式であるためです。この問題では、次数が最も高い変数を定数に変えることができます。

これは、min(max_x_degree, max_y_degree)<5 の場合、他の方法で O(1) 効率が得られなかったということではありません。

変数の数を増やすと、さらに興味深いものになります。

于 2012-04-25T02:40:56.137 に答える
0

セット X がそれほど大きくない場合、2D マトリックスを構築することによって、単純なブルート フォース アルゴリズムが機能する可能性があります。

于 2012-04-25T02:41:34.930 に答える