1.博弈論原理

博弈論：是二人或多人在平等的對局中各自利用對方的策略變換自己的對抗策略，達到取勝目標(biāo)的理論。博弈論是研究互動決策的理論。博弈可以分析自己與對手的利弊關(guān)系，從而確立自己在博弈中的優(yōu)勢，因此有不少博弈理論，可以幫助對弈者分析局勢，從而采取相應(yīng)策略，最終達到取勝的目的。

初時不明就里，了解了原理后才發(fā)現(xiàn)和初一玩的報數(shù)原理一樣。兩個同學(xué)玩報數(shù)游戲，從一報道二十，加一或者加二，一直累加，最后加到二十那個人獲勝。

2.解決方法

下面介紹分析此類題目的通用方法：P/N分析：

P點： 即必敗點，某玩家位于此點，只要對方無失誤，則必??；

N點： 即必勝點，某玩家位于此點，只要自己無失誤，則必勝。

三個定理：

? ? 一、 所有終結(jié)點都是必敗點P（上游戲中，輪到誰拿牌，還剩0張牌的時候，此人就輸了，因為無牌可?。?；

??? 二、所有一步能走到必敗點P的就是N點；

??? 三、通過一步操作只能到N點的就是P點；

所有博弈論算法都是根據(jù)上面的三條原理推論出來的。(是不是從上面三條原理看不出什么東東~~我也是啊~)博弈論關(guān)鍵是從后面找出必敗點（終結(jié)點）的規(guī)律。其實在確定誰先誰后的時候利用博弈論原理就能確定誰勝誰負(fù)了，所以做題目旨在找出必敗點（終結(jié)點）的變化規(guī)律并用數(shù)字表示出來。

題目鏈接：農(nóng)大1212博弈論題目

第一種解法：

//fafu1212?博弈論
#include#includeconst?int?maxn?=?33;
__int64?p[maxn];
int?m,?n;

void?init()
{
	memset(p,?0,?sizeof(p));
	p[0]?=?0;
	p[1]?=?2;
	for(int?i?=?2;?i?<?maxn;?i++)
	{
		p[i]?=?2?*?p[i?-?1]?+?2;
	}
}
bool?search(int?cas)
{
	for(int?i?=?0;?i?<?maxn;?i++)
		if(p[i]?==?cas)
			return?false;
	return?true;
}
int?main()
{
	init();
	scanf("%d",?&m);
	while(m--)
	{
		scanf("%d",?&n);
		if(search(n))
			puts("Johvid");
		else?puts("Abby");
	}
	return?0;
}

第二種解法(神人之作)：

#includeint?cas,?n;
int?main()
{
????scanf("%d",?&cas);
????while(cas--)
????{
????????scanf("%d",?&n);
????????puts((n?+?1)?&?(n?+?2)??"Johvid"?:?"Abby");
????}
????return?0;
}

題目鏈接：杭電2147博弈論題目

解法：

#includeint?n,?m;

int?main()
{
	while(scanf("%d%d",?&n,?&m),?n?||?m)
	{
		puts((n?&?1)?&&?(m?&?1)??"What?a?pity!"?:?"Wonderful!");
	}
	return?0;
}

3.總結(jié)及計劃

明天的計劃：開始圖論之旅，圖論看Z君的博客。

今天的總結(jié)：一 . 看到Z君的博客上的省賽總結(jié)，做400+的題目，數(shù)學(xué)思維沒有提高的話，只是一個打醬油的。今后要兼顧數(shù)學(xué)思維。數(shù)學(xué)是一切科學(xué)的源頭！

二 . Z君在博客上提到的，該會的題目會，不該會的題目一直不會，我現(xiàn)在也陷入這種尷尬的局況了，就像學(xué)動態(tài)規(guī)劃時，看來兩三次都看不懂。各種無奈。~~~~但是~~~~真正的夕陽武士就是明知不可為而為之。這邊找了幾個原因：1. 不該會的一直學(xué)不會沒有人指導(dǎo)，自己懶。2. 沒有狠狠地訓(xùn)練幾題相關(guān)的題目。各個突破，自學(xué)最重要，圖論學(xué)完把動態(tài)規(guī)劃再用心學(xué)一遍，題目做個十幾道。