8

整数は個々の数値を格納するために使用できますが、数式は格納できません。たとえば、次の式があるとします。

6x ^ 2 + 5x + 3

多項式をどのように保存しますか？独自のオブジェクトを作成することはできますが、メンバーデータを使用して多項式を表現する方法がわかりません。渡された引数を評価するだけでなく、式を操作する必要があるため、渡された引数を評価する関数を作成したくありません。

ベクトルは私の唯一の選択肢ですか、それとももっと適切な解決策がありますか？

4

8 に答える 8

8

単純だが効率の悪い方法は、係数のリストとして保存することです。たとえば、問題の多項式は次のようになります。

[6, 5, 3]

用語が欠落している場合は、その場所にゼロを入力してください。たとえば、多項式2x^3 - 4x + 7は次のように表されます。

[2, 0, -4, 7]

多項式の次数は、リストの長さから 1 を引いた値になります。この表現には重大な欠点が 1 つあります。スパース多項式の場合、リストには多数のゼロが含まれます。

スパース多項式の項リストのより合理的な表現は、非ゼロ項のリストです。ここで、各項は、項の次数とその次数の係数を含むリストです。多項式の次数は第 1 項の次数で与えられます。たとえば、多項式x^100+2x^2+1は次のリストで表されます。

[[100, 1], [2, 2], [0, 1]]

この表現がいかに有用であるかの例として、本SICPは、上記の多項式の 2 番目の表現を使用して、シンプルだが非常に効果的な記号代数システムを構築します。

于 2012-05-22T00:50:26.503 に答える
2

リストだけが選択肢ではありません。

指数を対応する係数にマッピングするマップ (辞書) を使用できます。

マップを使用すると、例は次のようになります

{2: 6, 1: 5, 0: 3}

(係数、指数) ペアのリストは非常に標準的です。多項式が密であることがわかっている場合、つまり、すべての指数位置が 0 から小さな最大指数までの範囲の小さな整数である場合は、オスカー ロペスが投稿したばかりのように、配列を使用できます。:)

于 2012-05-22T00:50:24.243 に答える
2

式を式ツリーとして表すことができます。たとえば、.NET Expression Treesを参照してください。

これにより、単純な多項式よりもはるかに複雑な式が可能になり、これらの式は複数の変数を使用することもできます。

.NET では、式ツリーをツリーとして操作し、関数として評価することができます。

        Expression<Func<double,double>> polynomial = x => (x * x + 2 * x - 1);
        double result = polynomial.Compile()(23.0);
于 2012-05-22T00:55:43.380 に答える
1

オブジェクト指向のアプローチでは、多項式は単項式の集合であり、単項式は係数と指数を一緒にカプセル化します。

このアプローチは、次のような多項式がある場合に機能します。

y(x) = x^1000 + 1

データ構造を多項式の順序に結び付けるアプローチは、この病的なケースでは非常に無駄になります。

于 2012-05-22T02:27:32.323 に答える
0

係数を配列またはベクトルに格納するだけです。たとえば、C ++では、整数係数のみを使用している場合は、を使用できます。std::vector<int>実数の場合は、を使用できますstd::vector<double>。次に、係数を順番にプッシュし、可変指数番号でアクセスします。

たとえば（これもC ++で）、5 * x ^ 3 + 9 * x-2を格納するには、次のようにします。

   std::vector<int> poly;
   poly.push_back(-2); // x^0, acceesed with poly[0]
   poly.push_back(9);  // x^1, accessed with poly[1]
   poly.push_back(0);  // x^2, etc
   poly.push_back(5);  // x^3, etc

大きくてまばらな多項式がある場合は、ベクトルの代わりにマップを使用することをお勧めします。サイズが固定されている場合は、ベクトルの代わりに固定長の配列を使用する可能性があります。

例としてC++を使用しましたが、これと同じスキームをどの言語でも使用できます。

于 2012-05-22T00:57:56.227 に答える
0

ベクトル/配列は当然の選択です。式のタイプに応じて、ある種のスパース ベクトル タイプを考慮することができます (カスタムメイド、つまり、式に 2 ～ 3 個のゼロ以外の係数 5x^100+x がある場合は、辞書またはリンク リストに基づく)。

いずれの場合も、後で実装を置き換えることができるため、カスタム クラス/インターフェイスを介して公開することは有益です。多くの式操作コードを作成する予定がある場合は、標準演算 (+、-、​​、等号) を提供することをお勧めします。

于 2012-05-22T00:50:45.130 に答える
0

逆ポーランド記法に変換することもできます:

6x^2 + 5x + 3 -> x 2 ^ 6 * x 5 * + 3 +

wherexと number はスタックに「プッシュ」され、演算 (^、*、+) はスタックから最上位の 2 つの値を取得し、それらを演算の結果に置き換えます。最後に、スタック上の結果の値を取得します。

この形式では、任意の複雑な式を簡単に計算できます。

この表現は、非リーフ ツリー ノードが操作と関数を表し、リーフ ノードが定数と変数を表す式のツリー表現にも近いです。

ツリーの良いところは、式の評価も簡単にできることと、記号微分などを行うことができることです。どちらも再帰的な性質を持っています。

于 2012-05-22T01:06:46.107 に答える
0

次の 2 つのものを保存する必要があります。

  1. 多項式の次数 (例: "3")
  2. 各係数を含むリスト (例: "{3, 0, 2}")

標準 C++ では、"std::vector<>" と "std::list<>" で両方を実行できます。

于 2012-05-22T00:52:13.757 に答える