博弈论是指研究多个个体或团队之间在特定条件制约下的对局中利用相关方的策略，而实施对应策略的学科。有时也称为对策论，或者赛局理论，是研究具备斗争或竞争性质现象的理论和方法，它是应用数学的一个分支，既是现代数学的一个新分支，也是运筹学的一个重要学科。目前在生物学、经济学、国际关系学、计算机科学、政治学、军事战略和其余不少学科都有普遍的应用。主要研究公式化了的激励结构（游戏或者博弈（Game））间的相互做用。php
咱们一般研究二人在平等的对局中各自如何利用对方的策略变换本身的对抗策略，达到取胜的目的。html
根据题目的意思，看它属于哪一种博弈，属于哪一种博弈的变形。 而后根据对应的博弈模型的解题策略来求解， 有时候并不必定可以直接看出它属于哪一种模型，那这个时候就能够经过判断本身每步可选的策略，对于本身每步走的，对当前局势的影响。而后推断出与之相对应的博弈模型。java
有n个物品，两我的轮流从这堆物品中取物，规定每次至少取一个，最多取 m个。最后取光者得胜。ios
假设n = m + 1，那么不管如何取，先取者必输。由于先取者不管取多少，后者一次性即可将剩余取完。app
胜利法则：若n%（m+1)不等于0，则先手必胜函数
若是 n=（m+1）r+s，（r 为任意天然数，s≤m),那么先取者要拿走 s 个物品，若是后取者拿走 k（≤m)个，那么先取者再拿走 m+1-k 个，结果剩下 （m+1）（r-1）个，之后保持这样的取法，那么先取者确定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。oop
#include <iostream>
using namespace std;
int main() {
int iCase;
cin >> iCase;
while (iCase--) {
int n, m;
cin >> n >> m;
if (n % (m + 1) == 0) cout << "lost" << endl;
else cout << "win" << endl;
}
return 0;
}
有两堆物品，一堆有a个物品，另外一堆有b个物品，两我的轮流取走一些石子，有两种取法：测试
1.从某堆中取走任意多个物品this
2.同时从两堆中取一样多的物品编码
规定每次至少取一个，多者不限，最后取光者得胜。
获胜法则：eqa = (1+sqrt(5.0))/2.0; 若a>b,swap(a,b); 若（b-a）*epa不等于a，先手必胜
这种状况下是颇为复杂的。咱们用（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）。
能够看出,a0=b0=0,ak 是未在前面出现过的最小天然数,而 bk= ak + k，奇异局势有以下三条性质：
两我的若是都采用正确操做，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
如何断定是不是奇异局势呢？
有以下公式： ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)
其中（1+√5）/2 = 1.618…,即为黄金分割数。所以,由 ak，bk 组成的矩形近似为黄金矩形，因为 2/（1+√5）=（√5-1）/2，能够先求出 j=[a（√5-1）/2]，若a=[ j（1+√5）/2]，那么 a = aj，bj = aj + j，若不等于，那么 a = aj+1，bj+1 = aj+1 + j + 1，若都不是，那么就不是奇异局势。而后再按照上述法则进行，必定会遇到奇异局势。
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9302 Accepted Submission(s): 5342
Problem Description
有两堆石子，数量任意，能够不一样。游戏开始由两我的轮流取石子。游戏规定，每次有两种不一样的取法，一是能够在任意的一堆中取走任意多的石子；二是能够在两堆中同时取走相同数量的石子。最后把石子所有取完者为胜者。如今给出初始的两堆石子的数目，若是轮到你先取，假设双方都采起最好的策略，问最后你是胜者仍是败者。
Input
输入包含若干行，表示若干种石子的初始状况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output
输出对应也有若干行，每行包含一个数字1或0，若是最后你是胜者，则为1，反之，则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0
Source
Recommend
LL | We have carefully selected several similar problems for you: 1404 1536 1517 1524 1729
#include <stdio.h>
#include <math.h>
int main()
{
int a,b,k;
double eqa = (1+sqrt(5.0))/2.0;
while( scanf("%d%d",&a,&b)!=EOF )
{
if( a > b )//交换a，b
{
a^=b;
b^=a;
a^=b;
}
k=b-a;
if( int( k*eqa )==a ) printf("0\n");
else printf("1\n");//先手必胜
}
return 0;
}
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3877 Accepted Submission(s): 2393
Problem Description
有两堆石子，数量任意，能够不一样。游戏开始由两我的轮流取石子。游戏规定，每次有两种不一样的取法，一是能够在任意的一堆中取走任意多的石子；二是能够在两堆中同时取走相同数量的石子。最后把石子所有取完者为胜者。如今给出初始的两堆石子的数目，若是轮到你先取，假设双方都采起最好的策略，问最后你是胜者仍是败者。若是你胜，你第1次怎样取子?
Input
输入包含若干行，表示若干种石子的初始状况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000，且a<=b。a=b=0退出。
Output
输出也有若干行，若是最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。若是在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的状况.
Sample Input
1 2
5 8
4 7
2 2
0 0
Sample Output
0
1
4 7
3 5
0
1
0 0
1 2
Author
Zhousc
Source
(a,b)奇异态先手必败，非奇异态先手必胜。先判断初始状态，若是为奇异态，则先手必败，不然，要输出先手第一次取石子后，两堆石子各剩下多少个，即由非奇异态转到奇异态。 作法是枚举全部的状态。好比测试数据中的 初始 5 8 是非奇异态，
则先手第一次取石子两堆可能剩下的状态有
一。两堆取相同的石子数
4 7
3 6
2 5
1 4
0 3
二。在第一堆里取
4 8
3 8
2 8
1 8
0 8
三。在第二堆里取
5 7
5 6
5 5
5 4
5 3
5 2
5 1
5 0
代码：
import java.util.*;
import java.math.*;
public class Main{
static int MAXN=(int)(1e6+10);
static boolean judge(int a,int b) {//判断奇异局势
double epa=(1+Math.sqrt(5.0))/2.0;
if(a>b) {
a^=b;
b^=a;
a^=b;
}
int k=b-a;
if((int)(k*epa)==a)//奇异局势
return true;
return false;
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
while(cin.hasNext()) {
int a=cin.nextInt();
int b=cin.nextInt();
if(a==0&&b==0) break;
if(judge(a,b)) {
System.out.println(0);
continue;
}
System.out.println(1);
int i=a,j=b;
while(i>=0&&j>=0) {
i--;j--;
if(judge(i,j))
System.out.println(i+" "+j);
}
i=a;j=b;
while(i>=0) {
i--;
if(judge(i,j))
System.out.println(i+" "+j);
}
if(a==b) continue;
i=a;j=b;
while(j>=0) {
j--;
if(judge(i,j))
System.out.println(j+" "+i);
}
}
cin.close();
}
}
（三）斐波那契博弈（Fibonacci Nim）
有一堆个数为 n 的石子，游戏双方轮流取石子，知足
1)先手不能在第一次把全部的石子取完；
2)以后每次能够取的石子数介于 1 到对手刚取的石子数的 2 倍之间（包含 1 和对手刚取的石子数的 2 倍）。
约定取走最后一个石子的人为赢家，求必败态。
这个和以前的 Wythoff’s Game 和取石子游戏 有一个很大的不一样点，就是游戏规则的动态化。以前的规则中，每次能够取的石子的策略集合是基本固定的，可是此次有规则 2：一方每次能够取的石子数依赖于对手刚才取的石子数。
胜利法则：先手胜当且 仅当 n 不是 Fibonacci 数。换句话说，必败态构成 Fibonacci 数列。
证实：
这里须要借助“Zeckendorf定理”（齐肯多夫定理）：任何正整数能够表示为若干个不连续的 Fibonacci 数之和。
FIB 数列的必败证实：
一、当 i=2 时，先手只能取 1 颗，显然必败，结论成立。
二、假设当 i<=k 时，结论成立。则当 i=k+1 时，f[i] = f[k]+f[k-1]。
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7842 Accepted Submission(s): 4734
Problem Description
1堆石子有n个,两人轮流取.先取者第1次能够取任意多个，但不能所有取完.之后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
Output
先取者负输出"Second win". 先取者胜输出"First win".
参看Sample Output.
Sample Input
2
13
10000
0
Sample Output
Second win
Second win
First win
Source
Recommend
lcy | We have carefully selected several similar problems for you: 2509 2512 1536 1907 1524
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int maxn=1e6+10;
int a[maxn];
int main()
{
int i;
a[0]=a[1]=1;
for(i=2;i<maxn;i++)
a[i]=a[i-1]+a[i-2];
int n;
while(scanf("%d",&n)!=EOF&&n){
bool flag=0;
for(int i=1;i<maxn;i++)
{
if(a[i]==n){
flag=1;break;
}
}
if(flag) printf("Second win\n");
else printf("First win\n");
}
return 0;
}
共 n 个石子，两我的按顺序依次取石子。先手不能所有取完，以后每人取的个数不能超过另外一我的上轮取的 K倍。 对于给定的 n, k， 先手是否有必胜的策略。
1.当 k=1 的时候 可知必败局面都是 2^i 将 n 分解成二进制，而后先手取掉最后一个 1，而后对方必然没法去掉更高的 1，而对方取完我方至少还能拿掉最后一 个 1 致使对方永远取不完。
2.当 k=2 的时候，必败局面都是斐波那契数列。利用“先手去掉最后一个 1，则后手必不能去掉更高阶的 1 致使取不完”的思想，斐波那契数列有一个很是好 的性质就是：任意一个整数能够写成斐波那契数列中的不相邻的项的和，因而将 n 写成这种形式，先取走最后一个 1，对方能取的数是这个数*2，小于高 2 位的 1，因此取不完。
3.当 K 取任意非0正值的时候， 想办法构造数列，将 n 写成数列中一些项的和，使得这些被取到的项的相邻两个倍数差距>k 那么每次去掉最后一个 1 仍是符合上面的条件。
设这个数列已经被构造了 i 项，第 i 项为 a[ i ]，前 i 项能够完美对 1..b[ i ] 编码使得每一个编码的任意两项倍数>K 那么有 a[ i+1 ] = b[ i ] + 1;这是显然的 由于 b[ i ] + 1 无法构造出来，只能新建一项表示。而后计算 b[ i+1] 既然要使用 a[ i+1 ] ，那么下一项最多只能是某个 a[ t ] 使得 a[ t ] * K < a[ i+1 ]， 因而b[ i ] = b[ t ] + a[ i+1 ] ，而后判断 n 是否在这个数列里面若是在，那么先手必败。不然不停的减掉数列 a 中的项构造出 n 的分解，最后一位就是了。
A simple stone game
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 631 | Accepted: 315 |
Description
After he has learned how to play Nim game, Mike begins to try another stone game which seems much easier.
The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k * m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game.
Input
The first line contains a integer t, indicating that there are t test cases following.(t<=20).
Each test case is a line consisting of two integer n and k.(2<=n<=108,1<=k<=105).
Output
For each test case, output one line starting with “Case N: ”, N is the case number. And then, if the first player can ensure a winning, print the minimum number of stones he should take in his first turn. Otherwise, print "lose". Please note that there is a blank following the colon.
Sample Input
5 16 1 11 1 32 2 34 2 19 3
Sample Output
Case 1: lose Case 2: 1 Case 3: 3 Case 4: lose Case 5: 4
Hint
When k = 1, the first player will definitely lose if the initial amount of stones is in the set {2, 4, 8, 16, 32, ...}. Let's call this kind of set “first-player-lose set”.
When k = 2, the first-player-lose set is {2, 3, 5, 8, 13, 21, 34, 57 ...} , which happens to be the Fibonacci sequence starting from 2.
Source
#include <stdio.h>
#define N 20000005
int a[N], b[N]; // a 为数列， b 保存 a[0...i] 能构造出的最大的数
int main()
{
int n, k;
int loop = 0, casei = 1;
scanf("%d",&loop);
while(loop --){
scanf("%d%d",&n,&k);
a[0] = b[0] = 1;
int i = 0, j = 0;
while(n > a[i]){ // 构建数列
i ++;
a[i] = b[i - 1] + 1;
while(a[j + 1] * k < a[i])
j ++;
if(k * a[j] < a[i])
b[i] = b[j] + a[i];
else
b[i] = a[i];
}
printf("Case %d: ", casei ++);
if(n == a[i])
printf("lose\n");
else{//win
int ans;
while(n){
if(n >= a[i]){ // 构成 n 的最小的数列中的数字，即为第一次要取的数字
n -= a[i];
ans = a[i];
}
i --;
}
printf("%d\n",ans);
}
}
return 0;
}