博弈

http://acm.hdu.edu.cn/showproblem.php?pid=2516

 1 斐波那契博弈
 2 判断这个数是不是斐波那契额数就可以，如果是，则后手必赢，如果不是可以分解成多个斐波那契数，则先手必赢
 3 
 4 
 5 import java.util.Scanner;
 6 
 7 public class Main{
 8     public static void main(String[] args) {
 9         Scanner cin = new Scanner(System.in);
10         long[]f = new long[50];
11         f[0] = 1;
12         f[1] = 1;
13         for(int i = 2;i<50;i++)
14             f[i] = f[i-1]+f[i-2];
15         int a;
16         while(true){
17             a = cin.nextInt();
18             if(a==0)
19                 break;
20             boolean flag = false;
21             for(int i = 0;i<50;i++)
22                 if(a==f[i]){
23                     flag = true;
24                     break;
25                 }
26             if(flag)
27                 System.out.println("Second win");
28             else 
29                 System.out.println("First win");
30         }
31     }
32 }

 1 /***
 2  * Wythoff博弈入门
 3  * 这个博弈关键是在与判断，m,n是不是奇异局势
 4  * 如果是奇异局势的话，那么先手必赢
 5  * 所谓奇异局势也就是说当j = m*(sqrt(5)-1)/2
 6  * 且 a == j*(sqrt(5)+1）/2
 7  * 如果m == a&&n ==a+j的话，这是一个奇异局势
 8  * 或则当a = (j+1)*(sqrt(5)+1)/2时
 9  *  m==a&&n==a+j+1时，也是奇异局势
10  */
11 import java.util.Scanner;
12 
13 public class Main {
14     public static void main(String[] args) {
15         Scanner cin = new Scanner(System.in);
16         int m, n;
17         double eps1 = (Math.sqrt(5) - 1) / 2;
18         double eps2 = (Math.sqrt(5) + 1) / 2;
19         while (cin.hasNext()) {
20             m = cin.nextInt();
21             n = cin.nextInt();
22             if (m > n) {
23                 int c = m;
24                 m = n;
25                 n = c;
26             }
27             int j = (int) (m * eps1);
28             int a = (int)(eps2 * j);
29             int b = (int)(eps2 * (j+1));
30             boolean flag = false;
31             if (m == a && n == a + j)
32                 flag = true;
33             if (m == b && n == b + j + 1)
34                 flag = true;
35             if (flag)
36                 System.out.println("0");
37             else
38                 System.out.println("1");
39         }
40     }
41 }