-5

プレーヤーが移動できなくなったかどうかを確認しようとしていますが、それを確認する方法がわかりません。タイルが 5 つ以下で、各タイルの値が 1 から 3 の間であるとします。タイルを調べて、合計が 10 になる可能性のある組み合わせがあるかどうかを確認したいと思います。3 のタイルが 3 つと 2 のタイルが 1 つある可能性があるため、合計を確認するだけでは簡単ではありません。これを理解しようとするのに何時間も....

考えられるすべての組み合わせを確認する方法についてのアイデアはありますか? 1 つの組み合わせが可能かどうかだけを確認する必要があります。見つかったらすぐに、ループを中断してチェックの数を減らします。

編集：それが役立つ場合は、ダウンロードすると、私が話していることをちょっと見ることができます. その数：アンドロイドの21。

このゲームの目的は、牌を 21 に追加することです。そのため、牌が数枚になると、すべての牌の合計が 21 を超えていても、数字の合計が正確に合わないため、21 の組み合わせを達成できないことがあります。 21. これを確認してユーザーに負けたことを伝えることができないため、問題が発生します。

それをチェックすることになると、どこから始めればいいのかさえわかりません。すべてのタイルを複数回ループできますが、ボード上にあるタイルの数だけ組み合わせることもできます。したがって、残っているタイルの数に達するまで、 3 、次に 4 、次に 5 の組み合わせをチェックする必要があります。これを正確に説明するのはちょっと難しい

今後の参考のための修正編集:

最初の質問が曖昧で申し訳ありません。私がここで尋ねた最初の質問でした...これは、問題と解決策のより良い説明です。記録のために以前のテキストを保持することにしました。

ゲームには多数の番号付きタイルがあり、削除するには最大 21 個まで追加する必要があります。21 を超えることはできません。正確でなければなりません。

私が確認したかったのは、正確に 21 を追加するために使用できるタイルの組み合わせがまだあるかどうかです。数字の 5 のタイルが 5 つあり、21 を超える可能性がありますが、これ以上削除することはできないため、基本的な合計チェックは機能しません。

解決

@mellamokbが答えたように、サブセット合計再帰を使用する必要がありました。基本的に、タイルをループし、各タイルで同じ関数を 2 回呼び出します。1 つの呼び出しは現在のタイルを追加し、もう 1 つの呼び出しは現在のタイルを追加せずに次の繰り返しに進みます。いずれかが true を返す場合、関数は true です。基本的に二分木。

コード

boolean validate(tiles, index, subtotal, total){
    if index >= tiles.length return false;
    if subtotal == total return true;
    return validate(tiles, index + 1, subtotal + tiles[index].number, total) || 
       validate(tiles, index + 1, subtotal, total);
}

で呼び出す

validate(tiles, 0, 0, 21)

それはそれについてです。

4

1 に答える 1

4

これは、サブセット和問題のバリエーションのように思えます。最も単純なアルゴリズムは O(2^n) で、たとえばビット フラグを使用して、考えられるすべてのサブセットの組み合わせを反復処理します。

for i = 0 to 2^n - 1
    set subtotal = 0
    for each bit in i
        if bit i is set, add ith element to subtotal
    check subtotal against desired total (i.e., 10)

または、代わりに再帰を使用します。

validate(set, index, subtotal, total)
    if index >= set.length return false;
    if subtotal == total return true;
    return validate(set, index + 1, subtotal + set[index], total) || 
           validate(set, index + 1, subtotal, total);

使用法：

validate(set, 0, 0, 10);
于 2012-08-20T22:23:27.000 に答える