“This is the 20th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Fibonacci games

Introduction to the

There are nn objects in a pile, if there are two people. A and B take turns to select items from the pair. The first item can be 1-N −11\ SIM N-11-N −1. The number of items that the latter person can take ranges from 111 to 222 times that the former person can take.

Train of thought

If first, set the current item number to RRR.

When r≤3r\le 3r≤3, A cannot win and B wins.

When r=4r=4r=4, player A takes 111, and player B is left 333.

When r=5r=5r=5, if A takes 222 or more, B wins. If a takes 111 and B takes 111, then r equals 3r equals 3r equals 3, and B wins.

Based on the above process, it’s not hard to see that in order to win you have to make sure that the Fibonacci number is as good as possible.

In other words, first hand wins by satisfying NNN not Fibonacci number.

Algorithm template

First we need to be able to calculate Fibonacci numbers

  1. The recursive method
long long fib(int k){
    if(k<=1) return 1;
    else return fib(k- 1) +fib(k2 -);
}
Copy the code
  1. The recursive method
long long fib(int k){
    fib[0]=fib[1] =1;
    for(int i=2; i<=k; i++){ fib[i]=fib[i- 1]+fib[i2 -];
    }
    return fib[k];
}
Copy the code

The template

Because of the linear complexity of recursion, the Fibonacci game is implemented by recursion.

bool fibG(int n){// This returns whether the first player can win
	fib[0]=fib[1] =1;
	for(int i=2; fib[i2 -]<=n; i++){if(fib[i2 -]==n) return false;
		fib[i]=fib[i- 1]+fib[i2 -];
	}
	return true;
}
Copy the code

sample

hdu2516

In general, NNN represents the number of items, outputs which person can win when the First person takes the lead, outputs the winner (First win or Second win), and inputs 000 to indicate the end.

#include <iostream>
using namespace std;
int fib[1001]; 
bool fibG(int n){// This returns whether the first player can win
	fib[0]=fib[1] =1;
	for(int i=2; fib[i2 -]<=n; i++){if(fib[i2 -]==n) return false;
		fib[i]=fib[i- 1]+fib[i2 -];
	}
	return true;
}
int main(a){
	int n;
	while(cin>>n,n! =0) {if(fibG(n)) cout<<"First win\n";
		else cout<<"Second win\n";
	}
	return 0;
}
Copy the code

Try to promote

If the rule is that whoever finishes first loses, look at the strategy.

Since User A can pick 1 ~ N −11\ SIM N-11 ~ N −1, user A can pick N − 1n-1N −1 and leave 111 to user B, so user B must lose.