Poj 1067 取石子游戏(NIM,威佐夫博奕)
2024-09-04 16:58:46
一、Description
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
Input
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。
Output
输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。
二、题解
这一题上手的没什么头绪,只能列举一些基本的例子,几乎看不出公式。后来,发现《编程之美》上有这个题目11.1~11.3三小节讲的都是关于“拈”NIM的游戏分析。Nim游戏是博弈论中最经典的模型之一,它又有着十分简单的规则和无比优美的结论. Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG)。Nim的一个变种就是威佐夫博奕。
这里有一种O(n)的解法列举出(1,1)~(10,10)的情况。然后去除安全局面,找到全部的不安全局面。发现了以下规律:一般而言,第n组的不安全局面(an,bn)可以由以下定义得到:
二、题解
这一题上手的没什么头绪,只能列举一些基本的例子,几乎看不出公式。后来,发现《编程之美》上有这个题目11.1~11.3三小节讲的都是关于“拈”NIM的游戏分析。Nim游戏是博弈论中最经典的模型之一,它又有着十分简单的规则和无比优美的结论. Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG)。Nim的一个变种就是威佐夫博奕。
这里有一种O(n)的解法列举出(1,1)~(10,10)的情况。然后去除安全局面,找到全部的不安全局面。发现了以下规律:一般而言,第n组的不安全局面(an,bn)可以由以下定义得到:
- a1=1,a2=2;
- 若a1,b2,...,an-1,bn-1已经求得,则定义an为未出现在这2n-2个数中的最小整数;
- bn=an+n;
因此,我们可以根据上述定义,从第一个不安全局面(1,2)出发,依次向上推理,直到推理出 足够的不安全局面来判定一个随机给定的状态下,先取者是否能够取胜。
import java.util.ArrayList;
import java.util.Scanner; public class Main {
public static ArrayList<Integer> a1=new ArrayList<Integer>();
public static boolean nim(int x,int y){
//speical case
if(x == y){
return true;
}
//swap the number
if(x > y){
int t=x;
x=y;
y=t;
}
//basic cases
if(x==1 && y==2){
return false;
}
a1.add(2);
int n=1;
int delta=1;
int addition=0; while(x > n){
//find the next n
while(a1.indexOf(++n)!=-1);
delta++;
a1.add(n+delta);
addition++; if(a1.size()>2 && addition > 100){
//因为数组中保存着n从1开始的不安全局面,所以在数组元素上个数超过100是删除无用的不安全局面
//使数组保持在一个较小的规模,以降低后面IndexOf()函数调用的时间复度。
shrinkArray(a1,n);
addition=0;
}
} if((x != n) || (a1.indexOf(y) == -1)){
return true;
}else{
return false;
}
} public static void shrinkArray(ArrayList<Integer> a1,int n){
for(int i=0;i<a1.size();i++){
if((int)a1.indexOf(i)>n){
for(int j=0;j<i;j++){
a1.remove(j);
}
return;
}
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int x,y;
while(sc.hasNext()){
x=sc.nextInt();
y=sc.nextInt();
if(nim(x,y)){
System.out.println("1");
}else{
System.out.println("0");
}
}
}
}
提交后发现超时了,于是用了后面介绍的时间复杂度为O(1)的解法:
我们看看能否找出不安全局面的规律,最好有一个通用的公式可以表示。所有不安全局面的两个数合起来就是所有正整数的集合,且没有重复的元素,而且所有不安全局面的两个数之差的绝对值合起来也是相同情况。我们可以用一个通项公式能计算出所有不安全局面,即:
- an=[ a * n ],bn=[ b * n ],( [ ] 表示对一个数向下取整 )
- a = ( 1 + sqrt( 5 )) / 2;
- b = ( 3 + sqrt( 5 )) / 2;(证明略)
import java.util.ArrayList;
import java.util.Scanner; public class Main {
static ArrayList<Integer> a1=new ArrayList<Integer>();
public static boolean nim(int x,int y){
double a,b;
a=(1 + Math.sqrt(5)) / 2;
b=(3 + Math.sqrt(5)) / 2;
if(x == y){
return true;
}
if(x > y){
int t=x;
x=y;
y=t;
}
return (x!=(long)Math.floor((y-x)*a));
} public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int x,y;
while(sc.hasNext()){
x=sc.nextInt();
y=sc.nextInt();
if(nim(x,y)){
System.out.println("1");
}else{
System.out.println("0");
}
}
}
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- Linux 系统命令
- sp_configure错误:不支持对系统目录进行即席更新。
- Cocos2d-x 3.2 学习笔记(五)Sprite Node
- target file里面的每个string字段的双引号怎么去掉
- vsftpd增加ssl安全验证
- UITextField输入中文限制
- (转)Windows驱动编程基础教程
- [Query Intent] segmenting-search-intent
- Linux下相关查找文件命令(find locate which whereis type)
- struts2,hibernate,spring整合笔记(1)
- javascript 下拉列表 自己主动取值 无需value
- Merge Into 用法
- 表单提交音乐文件(php)
- 大数据平台常见异常-zookeeper
- 使用Python编的猜数字小游戏
- INSERT INTO SELECT
- mysql游标中使用临时表
- 使用json通过telegraf生成metrics(摘自telegraf github文档)
- cgred不能自动将pid放入tasks
- app已损坏,打不开。你应该将它移到废纸篓。
热门文章
- They&#39;re much closer in spirit to how our brains work than feedforward networks.
- Android笔记之AsyncTask
- 解决IntelliJ IDEA无法读取配置文件的问题(转发:https://www.cnblogs.com/Sinte-Beuve/p/5730572.html)
- 使用基本 SQL 命令
- Shiro:学习笔记(1)——身份验证
- iOS swift 常量 &;&; 宏定义
- ubuntu中文语言环境下把系统中文文件夹更改回英文文件夹
- 【leetcode】Word Break
- 3D卡片折叠动画自定义下拉框
- springmvc的优化