ksandeep.v2
BAN USERLet us define a function is_first_player_winner() which returns 1 if the first player can control the game and force a win. This function returns 0 if the first player cannot do so, and consequently the second player wins.
Now, we can think of a recursive solution. If we want to find out if the first player can force a win for a given value if "N", we can consider all possible combinations of the first two moves.
We can divide N by the product of the first two moves and then apply the same function recursively to check if player 1 can force a win (Optimal substructure).
Based on the answer of these sub-problems, we can check if player 1 can force a win or not.
// Recursive Solution
int is_first_player_winner (int n)
{
/* Returns 1 if Player_1 can control and win the game
Returns 0 if the Player_1 cannot control and win the game */
if ( n <= 1 )
{
// should not reach here
// exit
}
if (n > 2 && n <= 9)
return 1; // first player wins
if (n > 9 && n <= 18)
return 0; // first player cannot win
/* Consider the first two moves in the game
They can be one of the following: (2,2), (2,9), (9,2), (9,9) */
// case 2,2
int win_2_2 = is_first_player_winner (ceil((float)n/4));
// case 2,9 or 9,2
int win_2_9 = is_first_player_winner (ceil((float)n/18));
// case 9,9
int win_9_9 = is_first_player_winner (ceil((float)n/81));
if ((win_2_2 && win_2_9) || (win_9_9 && win_2_9))
return 1;
else
return 0;
}
Random( ) - generates either a 0 or a 1.
- ksandeep.v2 January 31, 2012
What is the general rule? The pre-processing time is accounted for in the algorithm's complexity ? Or it is treated as a one-time overhead ?
- ksandeep.v2 September 25, 2012