1.博弈論原理

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

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

2.解決方法

下面介紹分析此類(lèi)題目的通用方法：P/N分析：

P點(diǎn)： 即必?cái)↑c(diǎn)，某玩家位于此點(diǎn)，只要對(duì)方無(wú)失誤，則必?cái)。?/p>

N點(diǎn)： 即必勝點(diǎn)，某玩家位于此點(diǎn)，只要自己無(wú)失誤，則必勝。

三個(gè)定理：

? ? 一、 所有終結(jié)點(diǎn)都是必?cái)↑c(diǎn)P（上游戲中，輪到誰(shuí)拿牌，還剩0張牌的時(shí)候，此人就輸了，因?yàn)闊o(wú)牌可取）；

??? 二、所有一步能走到必?cái)↑c(diǎn)P的就是N點(diǎn)；

??? 三、通過(guò)一步操作只能到N點(diǎn)的就是P點(diǎn)；

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

題目鏈接：農(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é)及計(jì)劃

明天的計(jì)劃：開(kāi)始圖論之旅，圖論看Z君的博客。

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

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