0

1つのまったく役に立たない質問：私は数値ゲームを購入しました。それは2つの黒いサイコロと5つの色のサイコロでできています。2つの黒い数字は11から66までの2桁の数字を形成し、他の5つは使用できる数字であり、可能なすべての数式でそれらを組み合わせて、目標の数字を取得します。

たとえば、黒40 + 2：ターゲット42

色付き536 2 4、5 3 + 6 * 4 2 +-でターゲットを取得できます（ブラケットを回避するため、RPNを使用します）。

今、私はポケットコンピューターを使って、人々がゲームをプレイしている間に最良の答えを見つけたいと思っています。

私はまだ解決策についてあまり深く考えていなかったと言わなければなりません、私は引数の順列を見つけることに関する部分を探しました、しかしそれからどのようにそれから可能な表現を生成するのですか？これは、RPNを使用して、式の可能なすべての「形状」を列挙してから、空白に+-*/を入力します。

式の形を列挙することの問題を認識していません。

出力は次のようになります：..... xxxx .... x.xxx ... x..xxx ..x ... xxx .... xx.xx ... xxxx ..x..x .xx ... xx..xx ..xx.xx .... xxx.x ... x.xx.x ..x..xx.x ... xx.xx ..xxxx

..xx ... xx ... xxx..x ..x.xx..x ..x.xx..xは、2番目または3番目の演算子が1つのオペランドを見つけるため、無効です。

ハードコードされたリストを使用できますが、見た目は本当に醜いです。

4

2 に答える 2

7

あなたが探しているのは、サイズ5の完全な二分木の列挙です（そのようなオブジェクトの数は、5番目のカタラン数である14です）。カタラン数の標準的な再帰に基づいて、列挙は簡単です
http://upload.wikimedia.org/math/2/f/1/2f17435a71394ce667ab694b27341560.png
。各（i、5-i）について、i葉のあるすべての木、葉のあるすべての木5-i、および各セットからの1つの木の組み合わせごとに生成します。 、左の子が最初のセットに由来し、右の子が2番目のセットに由来するルートノードを作成して、新しいツリーを構築します。ツリーを使用したくない場合は、RPNを直接使用してください。

# Produces all possible RPN layouts with n values and n-1 binary operators,
# representing values as '#' and operators as '+'
def RPN(n):
  if n == 1:
    yield '#'
  for i in range(1,n):
    for left in RPN(i):
      for right in RPN(n - i):
        yield left + right + '+'

もちろん、単項演算子もあります。それらを許可すると、より複雑になります。

上記を直接適応させて、引数を直接挿入できることに注意してください。nを（i、ni）に分割する代わりに、n個の値のセットのすべてのパーティションを2つの空でないサブセットに分割します。（それ以外の場合は、一連の数値のすべての順列を見つけて、結果のRPN式にプラグインすることができます。）

次に、実行する必要のある「すべて」は、可能なすべての演算子シーケンスを挿入することです（+、-、*および/のみを許可する場合は、4 4 = 256の可能性があります）。

したがって、5つの数値が異なる場合、14*5になります。* 4 4 =430080テストする式。

于 2013-01-14T00:20:59.303 に答える
0

異なる桁ブロックの数を列挙する際の問題は、セットに適用できるパーティションの数ですhttp://en.wikipedia.org/wiki/Partition_of_a_set

于 2013-01-13T23:49:07.603 に答える