Make writing a habit together! This is the 10th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I. Problem description

You play Nim with your friend, two people:

  • There is a pile of stones on the table.
  • You take turns playing your own rounds, you being the first.
  • In each round, the person in turn removes one to three stones.
  • Whoever removes the last stone is the winner.

Let’s say you’re doing the optimal solution every step of the way. Write a function to determine if you can win the game with a given number of stones n. Return true if you can win; Otherwise, return false.

Title link: Nim games

Two, the title requirements

The sample

Input: n = 4 Output: false Description: The following are possible results: 1. Remove 1 stone. Your friend removed three stones, including the last one. Your friend has won. 2. Remove two stones. Your friend removes 2 stones, including the last one. Your friend has won. 3. You remove 3 stones. Your friend removed the last stone. Your friend has won. Of all the outcomes, your friend wins.Copy the code

inspection

1. Mathematical ideas, game theory 2Copy the code

Third, problem analysis

I wanted it recursively at first, but I ran out of time, so I switched to dynamic programming.

1 true
2 true
3 true
4 false  
5 true
6 true
7 true
8 false  
9 true
10 true
Copy the code

The first three states are defined, and from the fourth, there are three possible states: -1, -2, -3, and we just need to take the inverse of those three states.

class Solution {
public:
    bool canWinNim(int n) {
        int i,dp[n+1];// Dynamic programming
        if(n<4)// The first three initializes
            return true;
        dp[1]=dp[2]=dp[3] =1;// The variable is initialized
        for(i=4; i<=n; i++)// loop judgment
        {
            if(! dp[i- 1) | |! dp[i2 -) | |! dp[i- 3])// Relationship induction
                dp[i]=1;
            else
                dp[i]=0;
        }
        return dp[n]==1;// Output the result}};Copy the code

Data is too large, timeout, look at 😂.

The summarized rules are as follows:

1 true
2 true
3 true
4 false  X
5 true
6 true
7 true
8 false  X
9 true
10 true
11 true
12 false  X
13 true
14 true
15 true
16 false  X
17 true
18 true
19 true
20 false  X
Copy the code

Print false as long as it is a multiple of 4, and true for the rest.

Mental process: too deep recursion → DP timeout → summing up the law.

Four, coding implementation

class Solution {
public:
    bool canWinNim(int n) {
        if(n%4= =0)/ / law
            return false;
        else
            return true; }};Copy the code

V. Test results