hdu 2516 斐波那契博弈

这个游戏叫做斐波那契博弈，顾名思义，当n是斐波那契数的时候必败，其他情况必胜。

证明见：http://blog.csdn.net/acm_cxlove/article/details/7835016

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 47;
 5 int f[N];
 6 
 7 void init()
 8 {
 9     f[0] = 1;
10     f[1] = 2;
11     for ( int i = 2; i < N; i++ )
12     {
13         f[i] = f[i - 1] + f[i - 2];
14     }
15 }
16 
17 bool win( int num )
18 {
19     for ( int i = 0; i < N; i++ )
20     {
21         if ( num == f[i] ) return false;
22     }
23     return true;
24 }
25 
26 int main ()
27 {
28     init();
29     int n;
30     while ( cin >> n, n )
31     {
32         if ( win(n) )
33         {
34             cout << "First win" << endl;
35         }
36         else
37         {
38             cout << "Second win" << endl;
39         }
40     }
41     return 0;
42 }