22

私はこれを尋ねる宿題の問題に取り組んでいます:

数の有限集合と目標数を求めて、基本的な数学演算 (add、sub、mult、div) を使用し、集合内の各数値を 1 回だけ使用して、その集合を使用して目標数を計算できるかどうかを調べます(したがって、セットを使い果たす)。これは再帰で行う必要があります。

たとえば、私がセットを持っている場合

{1, 2, 3, 4}

ターゲット 10 なら、

((3 * 4) - 2)/1 = 10. 

アルゴリズムを疑似コードで表現しようとしていますが、今のところあまり進んでいません。私はグラフが進むべき道だと思っていますが、これについては間違いなく助けていただければ幸いです。ありがとう。

4

7 に答える 7

5

これは最速の解決策ではなく、有益な解決策です。

  • 後置記法ですべての方程式を再帰的に生成します
  • また、後置記法から中置記法への変換も提供します
  • 実際の算術計算は行われないため、独自に実装する必要があります
    • ゼロ除算に注意

4 つのオペランド、4 つの可能な演算子を使用すると、すべて 7680 = 5 * 4 が生成されます。* 4^3 の可能な表現。

  • 5はカタロニア語(3)です。Catalan(N) は、N+1 オペランドを括弧で囲む方法の数です。
  • 4!4つのオペランドは置換可能であるため
  • 4^3 は、3 人のオペレーターがそれぞれ 4 つの選択肢を持っているためです。

N オペランドの式の数は [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...] であるため、これは間違いなくうまくスケーリングしません。

一般に、オペランドがあり、可能性から選択した演算子n+1を挿入する必要がある場合、可能性のある方程式があります。nk(2n)!/n! k^n

幸運を!

import java.util.*;

public class Expressions {
    static String operators = "+-/*";

    static String translate(String postfix) {
        Stack<String> expr = new Stack<String>();
        Scanner sc = new Scanner(postfix);
        while (sc.hasNext()) {
            String t = sc.next();
            if (operators.indexOf(t) == -1) {
                expr.push(t);
            } else {
                expr.push("(" + expr.pop() + t + expr.pop() + ")");
            }
        }
        return expr.pop();
    }

    static void brute(Integer[] numbers, int stackHeight, String eq) {
        if (stackHeight >= 2) {
            for (char op : operators.toCharArray()) {
                brute(numbers, stackHeight - 1, eq + " " + op);
            }
        }
        boolean allUsedUp = true;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != null) {
                allUsedUp = false;
                Integer n = numbers[i];
                numbers[i] = null;
                brute(numbers, stackHeight + 1, eq + " " + n);
                numbers[i] = n;
            }
        }
        if (allUsedUp && stackHeight == 1) {
            System.out.println(eq + " === " + translate(eq));
        }
    }
    static void expression(Integer... numbers) {
        brute(numbers, 0, "");
    }

    public static void main(String args[]) {
        expression(1, 2, 3, 4);
    }
}
于 2010-03-07T02:54:12.213 に答える
4

ええと、あなたは効率について言及していないので、本当に力ずくの解決策を投稿し、必要に応じて最適化できるようにします。括弧を使用できるため、逆ポーランド記法を使用して力ずくで簡単に実行できます。

まず、セットに n 個の数値がある場合、正確に n - 1 個の演算子を使用する必要があります。したがって、解は、{{your given set}, {*, /, +, -}} からの 2n - 1 シンボルのシーケンスによって与えられます。

st = a stack of length 2n - 1
n = numbers in your set
a = your set, to which you add *, /, +, -
v[i] = 1 if the NUMBER i has been used before, 0 otherwise

void go(int k)
{
  if ( k > 2n - 1 ) 
  {
    // eval st as described on Wikipedia. 
    // Careful though, it might not be valid, so you'll have to check that it is   
    // if it evals to your target value great, you can build your target from the given numbers. Otherwise, go on.

    return;
  }

  for ( each symbol x in a )
    if ( x isn't a number or x is a number but v[x] isn't 1 )
    {
      st[k] = x;
      if ( x is a number )
        v[x] = 1;

      go(k + 1);
    }
}
于 2010-03-06T12:56:27.523 に答える
3

一般的に言って、再帰的に何かをする必要があるときは、「底」から始めて、上に向かって考えることが役立ちます。考えてみてください。n個Sの数値のセットと4つの演算のセットがあります。セットで動作する再帰関数を呼び出しましょう{a,b,c,...}{+,-,*,/}F(S)

  • nが1の場合、F(S)その数になります。
  • nが2の場合、次のF(S)8つになります。
    • S(2つの選択肢)から左側の番号を選択してください
    • 次に、適用する操作を選択します(4つの選択肢)
    • 右側の番号は、セットに残っているものになります
  • これで、 n =2の場合 から一般化できます。
    • 左側のオペランドとなる番号xを選択します( n個の選択肢)S
    • 適用する操作を選択してください
    • あなたの右手の番号はF(S-x)

ここから持っていきましょう。:)

編集:マークは正当な批判を提起します。上記の方法では、すべてが完全に得られるわけではありません。その問題を解決するには、少し異なる方法でそれについて考える必要があります。

  • 各ステップで、最初に操作(4つの選択肢)を選択し、次に
  • S左側と右側のオペランドについて、2つのセットに分割します。
  • F両方のパーティションに再帰的に適用します

ただし、セットのすべてのパーティションを2つの部分に分割すること自体は簡単ではありません。

于 2010-03-06T12:53:44.210 に答える
2

この問題に対処する方法についての最良の手がかりは、教師/教授が再帰を使用することを望んでいるという事実です。つまり、これは数学の問題ではなく、検索の問題です。

あまりにも多くを与えないように (これは結局宿題です)、演算子、数値、および残りの数値を含むリストを使用して、再帰関数の呼び出しを生成する必要があります。再帰関数はリストから数値を抽出し、渡された操作を使用して、渡された数値 (現在の合計) と結合します。現在の合計を取得し、リストの残りの項目を使用して自分自身を再度呼び出します (呼び出し内でリストを反復する必要がありますが、呼び出しのシーケンスは深さ優先です)。検索の前の段階で成功した場合を除き、4 つの演算子のそれぞれについてこれを 1 回実行します。

スタックの代わりにリストを使用するようにこれを更新しました

操作の結果がターゲット番号であり、リストが空の場合、一連の操作 (成功したリーフへのパスをたどったもの) が正常に見つかりました - 成功フラグを設定して巻き戻します。演算子はリストにも呼び出しにも含まれていないことに注意してください。関数自体は常に 4 つすべてを反復処理します。成功したリーフから演算子シーケンスを「巻き戻し」てシーケンスを取得するメカニズムは、現在の演算子と、再帰呼び出しによって返された値の前に追加された番号を返すことです(成功で停止するため、そのうちの1つだけが成功します-明らかに、 、使用するものです)。いずれも成功しなかった場合、何を返すかは重要ではありません。

更新ダニエルが投稿したような式を考慮する必要がある場合、これははるかに困難です。数字とグループ化には組み合わせ論があります(優先順位が変わるため、グループ化とグループ化がなくても / と - は順序に依存するため、数字)。もちろん、演算の組み合わせ論もあります。(4 + 3) * 2 と 4 + (3 * 2) の違いを管理するのは難しいです。これは、グループ化が演算子や数値のように再帰的でないためです (これは、(深さ優先) 再帰呼び出し)。

于 2010-03-06T13:27:44.997 に答える
2

開始するための Python コードを次に示します。冗長性についてあまり心配することなく、すべての可能な式を出力するだけです。単に式を出力するのではなく、式を評価してターゲット番号と比較するように変更する必要があります。

基本的な考え方は次のとおりです: 数値の集合 S が与えられた場合、 S を 2 つの部分集合に分割leftし、すべての可能な方法 (順序や要素の順序やandrightは気にしません) で、とが両方とも空でないようにします。これらのパーティションのそれぞれについて、要素を(再帰的に!) 結合するすべての方法を見つけ、同様に を見つけ、2 つの結果の値を可能なすべての演算子と結合します。セットに要素が 1 つしかない場合、再帰は底をつきます。この場合、可能な値は 1 つだけです。leftrightleftrightleftright

Python を知らなくても、このexpressions関数はかなり簡単に理解できるはずです。このsplittings関数にはいくつかの Python の奇妙な点が含まれていますが、リストのすべてのパーティションをl左と右の部分に分けているだけです。

def splittings(l):
    n = len(l)
    for i in xrange(2**n):
        left = [e for b, e in enumerate(l) if i & 2**b]
        right = [e for b, e in enumerate(l) if not i & 2**b]
        yield left, right

def expressions(l):
    if len(l) == 1:
        yield l[0]
    else:    
        for left, right in splittings(l):
            if not left or not right:
                continue
            for el in expressions(left):
                for er in expressions(right):
                    for operator in '+-*/':
                        yield '(' + el + operator + er + ')'

for x in expressions('1234'):
    print x
于 2010-03-06T17:13:53.177 に答える
-1

プッシュコード:

Works(list, target)
for n in list
tmp=list.remove(n)
return Works(tmp,target+n) or Works(tmp,target-n) or Works(tmp, n-target) or ...

あとは基本ケースを入れればいいだけです。

于 2010-03-07T05:37:48.537 に答える