4

スピードアップのためにメモ化を伴う再帰関数を実装していました。プログラムのポイントは次のとおりです。

私は（赤と黒のカードの数が同じである）カードのデッキをシャッフルし、それらを表向きに配り始めます。カードの後で「やめる」と言うことができます。その時点で、私はあなたに赤のカードが配られるごとに1ドルを支払い、あなたは黒のカードが配られるごとに1ドルを支払います。あなたの最適な戦略は何ですか、そしてあなたはこのゲームをプレイするためにいくら払うでしょうか？

私の再帰関数は次のとおりです。

double Game::Value_of_game(double number_of_red_cards, double number_of_black_cards)
{
    double value, key;


    if(number_of_red_cards == 0)
    {
    Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), number_of_black_cards));
    return number_of_black_cards;
    }
    else if(number_of_black_cards == 0)
    {
    Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), 0));
    return 0;
    }

    card_iter = Card_values.find(Key_hash_table(number_of_red_cards, number_of_black_cards));
    if(card_iter != Card_values.end())
    {
        cout << endl << "Debug: [" << number_of_red_cards << ", " << number_of_black_cards << "] and value = " << card_iter->second << endl;
    return card_iter->second; 
    }

    else 
    {
    number_of_total_cards = number_of_red_cards + number_of_black_cards;
        prob_red_card = number_of_red_cards/number_of_total_cards;
        prob_black_card = number_of_black_cards/number_of_total_cards;

    value = max(((prob_red_card*Value_of_game(number_of_red_cards - 1, number_of_black_cards)) + 
             (prob_black_card*Value_of_game(number_of_red_cards, number_of_black_cards - 1))), 
             (number_of_black_cards - number_of_red_cards));
    cout << "Check: value = " << value << endl;

    Card_values.insert(Card_values.begin(), pair<double, double> (Key_hash_table(number_of_red_cards, number_of_black_cards), value));

        card_iter = Card_values.find(Key_hash_table(number_of_red_cards , number_of_black_cards ));
        if(card_iter != Card_values.end());
        return card_iter->second;
     } 
}

double Game::Key_hash_table(double number_of_red_cards, double number_of_black_cards)
{
    double key = number_of_red_cards + (number_of_black_cards*91);
    return key; 
}

3番目のifステートメントは、コードの「メモ化」部分であり、必要なすべての値を格納します。マップに保持されている値はマトリックスと考えることができます。これらの値は、特定の#redカードと#blackカードに対応します。本当に厄介なのは、合計8枚のカード（黒4枚と赤4枚）のコードを実行すると、間違った答えが返ってくるということです。しかし、10枚のカードのコードを実行すると、私の答えは間違っていますが、4つの黒と4つの赤の答えは正しいです（8枚のカード）！同じことが12枚のカードにも言えます。12枚のカードでは間違った答えが返ってきますが、10枚のカードでは正解です。コードにバグがありますが、わかりません。

4

1 に答える 1

3

誰も実際にこの質問に答えて答えませんでした。それで、私はそれを試してみますが、nneonneoは実際にあなたの問題の可能性のある原因に彼または彼女の指を置きます。

この場合、おそらく実際には問題ではないが、親指のように突き出ている最初の問題...あなたはdouble主に整数として扱う値を保持するために使用しています。この場合、ほとんどのシステムで、これはおそらく問題ありません。しかし、一般的な習慣として、それは非常に悪いです。特に、adoubleが0に正確に等しいかどうかをチェックするためです。ほとんどのシステムでは、ほとんどのコンパイラで、doubleは、加算に制限している限り、かなり大きなサイズまでの整数値を完全な精度で保持できる可能性があります。 、他の整数を減算および乗算するか、整数になりすまして新しい値を取得します。

しかし、それはあなたが見ているエラーの原因ではない可能性があります、それは臭いコードのためにすべての優れたプログラマーの警報ベルを鳴らすだけです。修正する必要があります。本当に2倍にする必要があるのは、赤または黒の相対確率を計算するときだけです。

そして、それはおそらくあなたの問題であるということに私をもたらします。コードには次の2つのステートメントがあります。

number_of_total_cards = number_of_red_cards + number_of_black_cards;
prob_red_card = number_of_red_cards/number_of_total_cards;
prob_black_card = number_of_black_cards/number_of_total_cards;

もちろん、これは次のように読む必要があります。

number_of_total_cards = number_of_red_cards + number_of_black_cards;
prob_red_card = number_of_red_cards/double(number_of_total_cards);
prob_black_card = number_of_black_cards/double(number_of_total_cards);

あなたは優れたプログラマーであり、それらの変数を整数として宣言しているからです。

おそらくprob_red_card、prob_black_cardはタイプの変数ですdouble。しかし、それらはあなたが私たちに示すコードのどこにも宣言されていません。つまり、宣言されている場所やタイプに関係なく、の再帰呼び出しツリー内のすべてのサブ呼び出しで効果的に共有する必要がありますGame::Value_of_game。

これはほぼ間違いなくあなたが望むものではありません。これらの変数がどのような値を持ち、関数の再帰呼び出しツリーで特定の呼び出し中にそれらの値が何を表すかについて推論することは非常に困難です。アルゴリズムを扱いやすく分析するには、実際にはローカル変数である必要があります。幸いなことに、それらは特定のステートメントのelse句内でのみ使用されているようです。ifしたがって、最初に値が割り当てられたときに宣言できます。おそらく、このコードは次のようになります。

unsigned const int number_of_total_cards = number_of_red_cards + number_of_black_cards;
const double prob_red_card = number_of_red_cards/double(number_of_total_cards);
const double prob_black_card = number_of_black_cards/double(number_of_total_cards);

私もそれらを宣言することに注意してくださいconst。変数の存続期間中に変更されるとは思わない値の変数をとして宣言することをお勧めしますconst。誤って間違ったコードを書いたときにコンパイラに通知するように依頼することで、より正しいコードを書くのに役立ちます。また、コンパイラがより良いコードを生成するのにも役立ちますが、この場合、コードを簡単に分析しても、コードは存続期間中に変更されず、constとして扱うことができるため、ほとんどの適切なオプティマイザは基本的constにコード最適化の目的は、それでも、誤って非定数の方法で使用した場合にコンパイラーに通知させるという利点はありません。

于 2012-10-07T07:09:39.413 に答える