•  
  • Archives for 博弈论 (11)

【POJ1067】取石子游戏 ||【NYOJ161】(威佐夫博奕(Wythoff Game))

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

威佐夫博奕(Wythoff Game):有两堆各若干个物品,两个人轮流从某一堆或同
时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

这种情况下是颇为复杂的。我们用(ak,bk)(ak ≤ bk ,k=0,1,2,…,n)表示
两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们
称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,
10)、(8,13)、(9,15)、(11,18)、(12,20)。
(more...)

【POJ1704】Georgia and Bob (staircase Nem 变形题)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

poj的discuss里边说的题解十分到位:

这道题目可以对应一个Staircase NIM问题,只需要把两个棋子之间的间隔以及第一个棋子与左边界的间隔看作一堆石子,
则一次操作一定是从一对石子中取出若干移到右边相邻的一堆中。这就是标准的Staircase-NIM问题。
具体的做法是:将所有奇数位置上的石子个数做XOR,结果为0说明BOB胜,否则说明GEORGIA胜,Not Sure显然是不会出现的。 (more...)

【POJ2975】Nim (博弈)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

n堆石子,然后问如果必胜的话有多少种移动方法(一步)。
因为答案最多只有n,令ans=a1^a2^...^an,如果需要构造出异或值为0的数,
而且由于只能操作一堆石子,所以对于某堆石子ai,现在对于ans^ai,就是除了ai以外其他的石子
的异或值,如果ans^ai< =ai,那么对于ai的话,是可以减小到ans^ai的值,然后使得所有数 的异或值为0,也即转移到了必败态。 (more...)

博弈论总结

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

以下是我从网上收集的关于组合博弈的资料汇总:

有一种很有意思的游戏,就是有物体若干堆,可以是火柴棍或是围棋子等等均可。两个
人轮流从堆中取物体若干,规定最后取光物体者取胜。这是我国民间很古老的一个游戏
,别看这游戏极其简单,却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够
取胜。
(more...)

【HDU1536】S-Nim (博弈,SG函数)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日
#include<cstdio>    
#include<algorithm>    
using namespace std;    
#define N 100+10    
int knum,mnum,lnum;    
int ans[N],si[N],hi[N],sg[10010];    
int mex(int x)//求x的sg值(可作为模版应用)  
{    
    if(sg[x]!=-1) return sg[x];    
    bool vis[N];  
    memset(vis,false,sizeof(vis));    
    for(int i=0;i<knum;i++)    
    {    
        int temp=x-si[i];    
        if(temp<0) break;    
        sg[temp]=mex(temp);    
        vis[sg[temp]]=true;    
    }    
    for(int i=0;;i++)    
    {    
        if(!vis[i])    
        {    
            sg[x]=i; break;    
        }    
    }    
    return sg[x];    
}    
int main()    
{    
    while(scanf("%d",&knum) && knum)    
    {    
        for(int i=0;i<knum;i++) scanf("%d",&si[i]);    
        sort(si,si+knum);    
        memset(sg,-1,sizeof(sg));    
        sg[0]=0;    
        memset(ans,0,sizeof(ans));    
        scanf("%d",&mnum);    
        for(int i=0;i<mnum;i++)    
        {    
            scanf("%d",&lnum);    
            for(int j=0;j<lnum;j++)    
            {    
                scanf("%d",&hi[i]); ans[i]^=mex(hi[i]);//尼姆博弈  
            }    
        }    
        for(int i=0;i<mnum;i++)    
        {    
            if(ans[i]==0) printf("L");    
            else printf("W");    
        }    
        printf("\n");    
    }    
    return 0;    
}  

【HDU1097】John

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

有SG 定理:
对于任意的一个 Anti-SG 游戏,如果我们规定当局面中所有单一游戏的 SG 值为 0 时游戏
结束,则先手必胜当且仅当以下两个条件满足任意一个:
(1)游戏的 SG 函数不为 0,且游戏中某个单一游戏的 SG 函数大于1。
(2)游戏的 SG 函数为 0,且游戏中没有单一游戏的 SG 函数大于 1。 (more...)

【poj2348】Euclid's Game

Categories: 数据结构和算法
Tags:
Comments: No Comments
Published on: 2011 年 04 月 11 日
  给两堆石子(题目中是数,配合一下上文这里说石子),两人依次取石子,规则是:
每次从石子数较多的那堆取(两堆石子数目相等时任选一堆),取的数目只能为石子少的
那一堆的正整数倍。最后取完一堆石子者胜。问给定情况下先手胜负情况。
    确实很像欧几里得,一看就想到递归了,似乎递归也不会太难,但是多列几项就会发
现一个熟悉的身影:斐波拉契数列。最后的结论是如果两个数相等,或者两数之比大于斐
波拉契数列相邻两项之比的极限((sqrt(5)+1)/2),则先手胜,否则后手胜。
当然这道题也能用欧几里得来做,不过相比这个就麻烦不少

(more...)

[POJ1082]Calendar Game & HDU1079 Calendar Game

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

解题思路
博弈论题目可以用寻找必败状态的方法解决。
第一个必败状态是2001.11.04。由此可以推出其他任何时间的状态。对于除2001.11.04外的其他任何时间,present状态是由能移动到的下两个next状态决定的(当然有些时间只有一个next状态),比如1924.12.19的状态是由1924.12.20和1925.01.19两个状态决定。如果两个next状态中有一个必败状态,则present状态为必胜状态;如果两个next状态都为必胜状态,则present状态为必败状态。 (more...)

NYOJ137 取石子(三) ([PKU][POJ][1740][A New Stone Game楼教主真男人8题)

Categories: 数据结构和算法
Tags:
Comments: No Comments
Published on: 2011 年 04 月 08 日

http://acm.nyist.net/JudgeOnline/problem.php?pid=137
(more...)

博弈论概述 (转自百度百科)

Tags:
Comments: No Comments
Published on: 2011 年 04 月 06 日

百科名片

博弈论(Game Theory),亦名“对策论”、“赛局理论”,属应用数学的一个分支, 目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。博弈论主要研究公式化了的激励结构间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。也是运筹学的一个重要学科。 博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。参见:行为生态学(behavioral ecology)

(more...)

5个海盗博弈(有的是10个海盗,N个海盗)

Categories: 数据结构和算法
Tags:
Comments: No Comments
Published on: 2011 年 04 月 06 日
先来看看此难题原先的形状。10名海盗抢得了窖藏的100块金子,并打算瓜分这些战利品。
这是一些讲民主的海盗(当然是他们自己特有的民主),他们的习惯是按下面的方式进行
分配:最厉害的一名海盗提出分配方案,然后所有的海盗(包括提出方案者本人)就此方
案进行表决。如果50%或更多的海盗赞同此方案,此方案就获得通过并据此分配战利品。否
则提出方案的海盗将被扔到海里,然后下一名最厉害的海盗又重复上述过程。
 (more...)
page 1 of 1
文章归档
日历
2017年十一月
« 七    
 1234
567891011
12131415161718
19202122232425
2627282930  
标签云
sina weibo
我的广告可能就是你的信息

Welcome , today is 星期日, 2017 年 11 月 19 日