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; 
}

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

4

1 回答 1

3

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

在这种情况下，第一个问题可能实际上不是问题，但像拇指酸痛一样突出......您double用来保存一个您主要视为整数的值。在这种情况下，在大多数系统上，这可能没问题。但作为一般做法，这是非常糟糕的。特别是因为您检查 adouble是否完全等于 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。

这几乎肯定不是你想要的。在函数的递归调用树中的任何给定调用期间，很难推断这些变量具有什么值以及这些值代表什么。它们确实必须是局部变量才能使算法易于分析。幸运的是，它们似乎只在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 回答