Memoization递归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语句是代码的“记忆化”的一部分，它存储了所有必要的值。保存在地图中的值可以被认为是矩阵，这些值将对应于某个#red cards和#black卡。实际上，当我执行总共8张牌的代码（4个黑色和4个红色）时，我得到的答案不正确。但是当我执行10张卡片的代码时，我的回答是错误的，但现在我的4个黑色和4个红色的答案是正确的（8张卡片）！对于12张牌也是如此，我得到了12张牌的错误答案，但对于10张牌的正确答案如此等等。代码中存在一些错误，但是，我无法弄清楚。

Answer 1

没有人真正回答这个问题的答案。所以我会试一试，虽然nneonneo实际上把他或她的手指放在你的问题的可能来源。

在这种情况下，第一个问题实际上可能不是问题，但伸出拇指疼痛......您正在使用double来保存您主要视为整数的值。在这种情况下，在大多数系统上，这可能是好的。但作为一般惯例，这是非常糟糕的。特别是因为你检查double是否等于0.在大多数系统上，对于大多数编译器来说，它可能是一样的，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代码优化的目的，尽管如此，如果您不小心以非const方式使用它们，它仍然不会带给您编译器的好处。