求助乙個量水博弈問題，先手是否必勝？

1樓：唐瑜

題目並未要求要7毫公升在乙個杯子裡。

先量7毫公升很容易，把11毫公升的倒入自己2毫公升的杯子，就有乙個5毫公升的滿杯和乙個2毫公升的滿杯，加起來就是7毫公升了。

2樓：王晟宇

開乙個11維陣列記錄狀態，前5維表示先手人的5個杯子內的水量，後5維表示後手人的5個杯子內的水量，最後一維儲存當前輪到誰來倒水（0是先手人，1是後手人）。

先把1步可贏的所有狀態都標記（比如[2][0][5][0][9] [0][3][5][0][8] [0]這個狀態就標記掉）

已經贏了的狀態也標記掉（比如[2][3][5][0][8] [2][0][5][0][7] [1]）

然後看有沒有狀態，它所能到達的狀態都已經被標記掉。經過暴力搜尋發現沒有找到這狀態。也就是說不管我目前處於什麼狀態，我都會有一種走法使得對手無法走一步就贏。

因此雙方都無法贏，最終平局。

#include

using namespace std;

int f_min(int x,int y)

for(i=0;i<=lim[loc];i++)

}bool next_all_win(int a)

}return 1;

}bool dfs2(int loc,int sum)

for(i=0;i<=lim[loc];i++)

return 0;

}int main()

3樓：李巨集訓

用x->y 表示把x毫公升的杯子的水倒進y毫公升的杯子（直到x空或者y滿）。然後a表示先手的杯子，b表示後手的杯子。

沒人干擾下，最快的步驟應該是2步：a11->a2,a11->b2, 這個時候a11中是7毫公升。如果受到b的干擾，比如b把自己的b2杯子先裝滿不讓你用，則是3步獲勝：

比如： a11 ->a 2, a2->a8, a11->a2 (這個時候11毫公升的杯子中是7毫公升的水)或者a11->a2,a2->a8,a5->a8(8毫公升的杯子中是7毫公升的水），細節如下：

基本的理論是b必須防守：如果只進攻不防守，則a必勝，並且是2至3步獲勝。b就必須防守，b防守的策略只能是把自己杯子的水倒進a的杯子來干擾他，不然一定會輸。

（這個干擾的過程可能也會幫自己量出7毫公升，即防守的同時幫助進攻，但是b的總步數顯然不會少於3步）。

下面是我想到的一種應該是最常見的情況：

遊戲開始：

1，a第一步可以這樣：a11->a2（這應該是最好的開局，如果a不這樣，a走任意其他步驟至少3步才能獲勝，b就會用這一招來取勝或者求和）

2，下一步該b了，b必須防守了，不然a下一步a11-b2就贏了。只有兩種方法：往a11中加水或者把b2杯子加滿，但是如果把b2杯子加滿，會導致自己有乙個b5或者b11杯子差2毫公升，a只需要把a11的杯子中的水將b5或者b11加滿，然後a就贏了。

所以只能選擇往a11中加水來干擾他。所以b只能是b5->a11,或者b11->a11.假設選b11->a11.

3，現在的情況是：

a:2/2,0/3,5/5,0/8,11/11

b:0/2,0/3,5/5,0/8,9/11

會發現現在情況剛好反過來了，b變得進攻了，因為a下一步肯定贏不了，而b下一步就可以贏：b11->b2,。可以參考第2步來看，發現a只有三種走法：

a2->b11,a5->b11或者a11->b11,如果選a2->b11就回到開局了，如果是a11->b11,就完全回到第二步了然後就直接和局了，所以就只考慮a5->b11.

4,現在的情況是：

a:2/2,0/3,3/5,0/8,11/11

b:0/2,0/3,5/5,0/8,11/11

b會發現，可以用b11->b2來造成很大威脅，然後a又開始防守了………………

最終會發現，利用兩次11->2是最簡單有效的方法，如果a不利用，b就會用這個方法，而利用這個方法就會最終導致在23步中描述的那樣的和局。因為存在11->2,11->2這種殺手鐗，所以總能有一方感覺自己處於弱勢而用這一招求和。所以我覺得最終的結果應該是和局。