c++ - 记忆化递归 C++

Question

我正在实现一个带内存的递归函数以提高速度。程序要点如下:

我洗一副纸牌(红色和黑色的数量相等牌)并开始正面朝上发牌。在任何卡片之后你可以说“停止”，此时我付给你 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; 
}

第三个 if 语句是代码的“内存”部分，它存储所有必要的值。保存在 map 中的值可以被认为是一个矩阵，这些值将对应于特定的#red 卡和#black 卡。真正奇怪的是，当我总共执行 8 张卡片(4 张黑色和 4 张红色)的代码时，我得到了一个错误的答案。但是当我执行 10 张牌的代码时，我的答案是错误的，但现在我的 4 黑 4 红答案是正确的(8 张牌)! 12 张牌也是如此，我得到 12 张牌的错误答案，但 10 张牌的正确答案，依此类推。代码中有一些错误，但是我无法弄清楚。

Answer 1

实际上没有人回答这个问题。所以我会试一试，虽然nneonneo实际上将他或她的手指放在您问题的可能根源上。

第一个问题在这种情况下可能实际上不是问题，但像拇指一样突出...您正在使用 double 来保存一个您通常将其视为整数的值。在这种情况下，在大多数系统上，这可能没问题。但作为一般做法，这是非常糟糕的。特别是因为您检查 double 是否恰好等于 0。在大多数系统上，对于大多数编译器，double 可能会以完美的精度保存相当大的整数值只要您将自己限制在加、减和乘以其他整数或伪装成整数的 double 以获得新值。

但是，这可能不是您所看到的错误的根源，它只是触发了每个优秀程序员对臭味代码的警钟。它应该是固定的。只有在计算红色或黑色的相对概率时，您才真正需要它们是双倍的。

这让我想到了可能是您的问题。您的代码中有这两个语句:

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 的递归调用树中的所有子调用有效地共享。

这几乎肯定不是您想要的。这使得推断这些变量具有什么值以及这些值在函数的递归调用树中的任何给定调用期间代表什么变得非常困难。它们确实必须是局部变量，以便算法易于分析。幸运的是，它们似乎只在特定 if 语句的 else 子句中使用。所以它们可以在初始赋值时声明。这段代码应该是这样的:

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 出于代码优化的目的，尽管如果您不小心以非常量方式使用它们，编译器仍然不会给您带来好处。