1

数値で構成される文字列を指定し、+ または - 記号を追加して式の値を 0 にします。式を返します。

例えば、

123 => 1 + 2 -3 = 0

173956 => 17 + 39 - 56 = 0

力ずくの方法以外に、この問題を解決する手がかりはありません。

何か提案はありますか？

4

2 に答える 2

1

これは検索の問題です。検索は解空間で実行する必要があります。「123」文字列から開始するとします。この時点で、「1」の後に + または - 記号を追加すると、「1 + 23」または「1 - 23」が得られます。すべてのバリアントは、次の文字の後に記号を追加することでさらに分割できます。その結果、すべての可能な記号の追加は、ツリーのような構造 (解空間) を形成します。アルゴリズムは、この構造で解を検索する必要があります。これには A* を使用できると思います。

Anders Kは、解空間の素敵な ASCII グラフを描画します。解を検索するだけで済みます。単純な幅優先探索や深さ優先探索でもできますが、解空間が大きいと遅くなると思います。

また、解空間の性質、例えば木のような構造を利用することで、より最適な具体的な解を見つけることができると思います。

于 2012-10-18T06:22:27.673 に答える
0

たとえば、ツリーとして構造化すると明らかになる再帰的アプローチを使用して、多くの方法で解決できます

例: 123

数字の後に 2 つの異なる記号がある可能性があるため(+|-) です。

        1
       / \
      +   -
     /     \
    2       2   
   / \     / \
  +   -   +   -
  |   |   |   |
  3   3   3   3
于 2012-10-18T06:21:51.460 に答える