SRM DIV2 575 TheNumberGameDivTwo

SRM DIV2 575 TheNumberGameDivTwo

【题意】：两个人玩游戏，给定一个数，减去他的因子（除了1和他本身外）得到一个新数，两个人轮流玩游戏.最后谁无数可减即为失败。  

【算法】根据N/P分析：

1.标记出1-1000所有的质数，这都是必败点P

2.从小到大，如果不是质数，则根据N/P关系判断他是N还是P。

3.直到n为止。

一个P/N分析的例子http://blog.sina.com.cn/s/blog_87ad13a10100y3ay.html

【编码调试BUG】

1.49行，生成prime数组的时候，循环结束条件应该是i<=n/2，少考虑了等号的情况；

2.23行，j

【Java代码】来自菜鸟 

 1 import java.util.*;
 2 import java.util.regex.*;
 3 import java.text.*;
 4 import java.math.*;
 5 
 6 
 7 public class TheNumberGameDivTwo
 8 {
 9     boolean[] prime;
10     public String find(int n)
11     {
12         int i,j,temp;
13         boolean[] p = new boolean[n+1];
14         
15         getPrimes(n);
16         //init all primes to P
17         for(i=1;i<=n;i++)
18             p[i]=prime[i];
19         
20         for(i=1;i<=n;i++){
21             if(p[i])
22                 continue;
23             for(j=2;j){
24                 if(p[j]){
25                     temp=i-j;
26                     if(i%temp==0)
27                         break;//p[i] is N
28                 }
29             }
30             if(j==i+1)
31                 p[i]=true;//p[i] is P
32         }
33         if(p[n])
34             return "Brus";
35         else
36             return "John";
37     }
38     
39     public void getPrimes(int n){
40         prime = new boolean[n+1];
41         int i,j;
42         
43         for(i=1;i<=n;i++)
44             prime[i]=true;
45         
46         prime[0]=prime[1]=false;
47         
48         for(i=2;i<=n/2;i++){
49             if(!prime[i])
50                 continue;
51             for(j=i+i;j<=n;){
52                 prime[j]=false;
53                 j+=i;
54             }
55         }        
56     }
57 }
58 //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

【改进版1】

【算法】

1.从小到大，则根据N/P关系判断他是N还是P（类似动态规划的填表）。

2.直到n为止。

【分析】

1.无需求出prime，因为算法可以保证所有的prime都为P。

 1 import java.util.*;
 2 import java.util.regex.*;
 3 import java.text.*;
 4 import java.math.*;
 5 
 6 
 7 public class TheNumberGameDivTwo
 8 {
 9     public String find(int n)
10     {
11         int i,j;
12         boolean[] p = new boolean[n+1];
13         
14         p[1]=true;
15         for(i=2;i<=n;i++){
16             for(j=2;j){
17                 if(i%j==0){
18                     if(p[i-j]==true){
19                         p[i]=false;
20                         break;
21                     }
22                 }
23             }
24             if(j==i)
25                 p[i]=true;
26 
27         }
28         if(p[n])
29             return "Brus";
30         else
31             return "John";
32     }
33     
34 
35 }
36 //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

【改进版2】实现时有点小区别，算法不变

 1 import java.util.*;
 2 import java.util.regex.*;
 3 import java.text.*;
 4 import java.math.*;
 5 
 6 
 7 public class TheNumberGameDivTwo
 8 {
 9     public String find(int n)
10     {
11         int i,j;
12         boolean[] p = new boolean[n+1];
13         
14         
15         for(i=1;i<=n;i++){
16             for(j=i/2;j){
17                 if(p[j]){
18                     if(i%(i-j)==0)
19                         break;//p[i] is N
20                 }
21             }
22             if(j==i-1)
23                 p[i]=true;//p[i] is P
24         }
25         if(p[n])
26             return "Brus";
27         else
28             return "John";
29     }
30 }
31 //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

【Java代码】来自大神

【分析】

1.大神采用的是动态规划的递归实现。

2.P问题对应memo[i]=0,N问题对应memo[i]=1。

3.divisors(n)方法用于获取n的所有除数。

【学习】

1.Arrays.fill()这个方法不错啊，有点像C里的memset。

import java.util.*; public class TheNumberGameDivTwo { ArrayList divisors(int n) { ArrayList res = new ArrayList(); for (int i = 2; i * i <= n; i++) { if (n % i == 0) { res.add(i); if (!res.contains(n / i)) res.add(n / i); } } return res; } int[] memo; public int can(int n) { if (n == 1 || n == 2 || n == 3) return 0; if (memo[n] != -1) return memo[n]; int res = 0; ArrayList divs = divisors(n); for (int i = 0; i < divs.size(); i++) { res |= can(n - (int)(divs.get(i))) ^ 1; } return memo[n] = res; } public String find(int n) { memo = new int[n + 2]; Arrays.fill(memo, -1); return can(n) > 0 ? "John" : "Brus"; } } // Powered by FileEdit
// Powered by moj 4.17 [modified TZTester]
// Powered by CodeProcessor

【C++代码】来自大神

【分析】

1.大神也是DP的递归实现。

2.代码好简洁，好帅气！

#include
#include<string>
#include

【总结】

1.N/P属于博弈论范畴，应该用DP实现。

转载于:https://www.cnblogs.com/wang3/p/3219730.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！