Remembrance C ++ Recursion

Question

I implemented a recursive function with memoization to speed up. The program item is as follows:

I shuffle the deck of cards (with an equal number of red and black cards) and start to handle them face up. After any card, you can say “stop,” after which I pay you $ 1 for each red card, and you pay me $ 1 for each black card. What is your optimal strategy and how much will you pay for playing this game?

My recursive function is as follows:

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

The third if statement is part of the "memoization" code; it stores all the necessary values. The values ​​stored on the card can be considered as a matrix, these values ​​will correspond to certain cards #red and #black. What is really terrible is that when I execute the code for 8 cards in total (4 black and white and 4 red), I get the wrong answer. But when I execute the code for 10 cards, my answer is wrong, but now my answer is for 4 black and 4 red correct (8 cards)! The same can be said for 12 cards, where I get the wrong answer for 12 cards, but the correct answer for 10 cards, etc. There are some errors in the code, however I cannot figure it out.

Answer 1

No one actually answered this question with an answer. Therefore, I will give it a try, although nneonneo actually put his or her finger on the probable source of your problem.

The first problem, which is probably not really the problem in this case, but sticks out like a sore finger ... you use double to store the value that you basically consider as a whole. In this case, on most systems this is probably OK. But, as a general practice, this is very bad. In particular, because you check whether the double value corresponds to 0. Probably, it will, like most systems, most compilers, double can store integer values ​​to fairly large sizes with full accuracy, if you restrict yourself to add, subtract and multiply other integers or duplicate disguise as integers to get a new value.

But, most likely, this is not the source of the error you see, it simply disables all good programmer sound alarms for the smelly code. It must be fixed. The only time you really need them to double is when you calculate the relative probability of red or black.

And that brings me to what is probably your problem. You have two statements in your code:

 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; 

which, of course, should read:

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

because you were a good programmer and declared these variables as integers.

prob_red_card and prob_black_card are double variables. But they are not declared anywhere in the code that you show us. This means that no matter where they were declared or what their types were, they should be effectively used by all subzones in the recursive call tree for Game::Value_of_game .

This is almost certainly not what you want. It is very difficult to understand what values ​​these variables have and what these values ​​represent during any given call in the recursive call tree for your function. They really need to be local variables so that the algorithm can be convenient for analysis. Fortunately, they seem to be used only in the else clause of a specific if . Thus, they can be declared when they are initially assigned values. This code should probably be read:

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

Note that I also declare them const . It is good practice to declare any variable whose value you do not expect to change as a const throughout the lifetime of the variable. This helps you write code that is more correct by asking the compiler to tell you when you accidentally wrote the wrong code. It can also help the compiler generate better code, although in this case even a trivial analysis of the code shows that they do not change during their lifetime and can be considered as const, so most worthy optimizers essentially put const in for you in order to optimize the code, although it still won’t give you an advantage if the compiler tells you if you accidentally use them in a non-constant way.