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方式使用它們，它仍然不會帶給您編譯器的好處。