資訊專欄INFORMATION COLUMN
摘要：拿到最后一顆石頭的一方為剩方?，F(xiàn)給定一個石頭數(shù)量，判斷你最終是否能取得勝利。對方全拿，對方贏。因此，必輸無疑。當(dāng)剩下的石頭為的整數(shù)倍雙方都采取最優(yōu)策略時，先下手的一方為輸家。因此這個題目就很簡單了，只要判斷給定的數(shù)字是否是的整數(shù)倍即可。
D64 292. Nim Game 題目鏈接
292. Nim Game
題目分析假設(shè)你和朋友玩一個撿石頭的游戲，你和朋友輪流拿1~3顆石頭。拿到最后一顆石頭的一方為剩方。第一輪由你開始撿石頭。
同時假設(shè)你和你的朋友都足夠聰明，每次都能采取最優(yōu)策略。
現(xiàn)給定一個石頭數(shù)量，判斷你最終是否能取得勝利。
思路我們先從少一點開始推廣到n個石頭。
如果有1～3顆石頭，因為規(guī)定了是你開始、還假設(shè)會采取最優(yōu)策略，那么你是能獲勝的。也即，對方不會在拿走石頭后剩下1
假設(shè)有4顆石頭。
你拿1顆，會剩下3顆。對方全拿，對方贏。
你拿2顆，會剩下2顆。對方全拿，對方贏。
你拿3顆，會剩下1顆。對方全拿，對方贏。
即，怎么拿都是你輸。
假設(shè)有5顆石頭。
你拿1顆，會剩下4顆。
對方拿走1顆，剩下3顆給你，你全拿，你贏。
對方拿走2顆，剩下2顆給你，你全拿，你贏。
對方拿走3顆，剩下1顆給你，你全拿，你贏。
你拿2顆，會剩下3顆。對方全拿，對方贏。
你拿3顆，會剩下2顆。對方全拿，對方贏。
因此，這一輪你會選擇拿1顆，剩下4顆。
假設(shè)有6顆石頭。
你拿1顆，會剩下5顆。
對方拿走1顆，剩下4顆給你，參考一開始就只有4顆的情況，對方贏。
對方拿走2顆，剩下3顆給你，你全拿，你贏。
對方拿走3顆，剩下2顆給你，你全拿，你贏。
你拿2顆，會剩下4顆。
對方拿走1顆，剩下3顆給你，你全拿，你贏。
對方拿走2顆，剩下2顆給你，你全拿，你贏。
對方拿走3顆，剩下1顆給你，你全拿，你贏。
你拿3顆，會剩下3顆。對方全拿，對方贏。
因此，這一輪你會選擇拿2顆，剩下4顆。
假設(shè)有7顆石頭。
你拿1顆，會剩下6顆。
對方拿走1顆，剩下5顆給你，參考一開始就只有5顆的情況，你贏。
對方拿走2顆，剩下4顆給你，對方贏。
對方拿走3顆，剩下3顆給你，你全拿，你贏。
你拿2顆，會剩下5顆。
對方拿走1顆，剩下4顆給你，對方贏。
對方拿走2顆，剩下3顆給你，你全拿，你贏。
對方拿走3顆，剩下2顆給你，你全拿，你贏。
你拿3顆，會剩下4顆。
對方拿走1顆，剩下3顆給你，你全拿，你贏。
對方拿走2顆，剩下2顆給你，你全拿，你贏。
對方拿走3顆，剩下1顆給你，你全拿，你贏。
因此，這一輪你會選擇拿3顆，剩下4顆。
假設(shè)有8顆石頭。
你拿1顆，會剩下7顆。
對方拿走1顆，剩下6顆給你，參考一開始就只有6顆的情況，你贏。
對方拿走2顆，剩下5顆給你，參考一開始就只有5顆的情況，你贏。
對方拿走3顆，剩下4顆給你，對方贏。
你拿2顆，會剩下6顆。
對方拿走1顆，剩下5顆給你，你贏。
對方拿走2顆，剩下4顆給你，對方贏。
對方拿走3顆，剩下3顆給你，你全拿，你贏。
你拿3顆，會剩下5顆。
對方拿走1顆，剩下4顆給你，對方贏。
對方拿走2顆，剩下3顆給你，你全拿，你贏。
對方拿走3顆，剩下2顆給你，你全拿，你贏。
因此，必輸無疑。
我們可以得出規(guī)律。當(dāng)剩下的石頭為4的整數(shù)倍、雙方都采取最優(yōu)策略時，先下手的一方為輸家。
因此這個題目就很簡單了，只要判斷給定的數(shù)字是否是4的整數(shù)倍即可。
最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/31507.html
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：題目鏈接思路博弈論類型的題目?？偨Y(jié)規(guī)律得知，的倍數(shù)時，先走的必敗。算法復(fù)雜度時間空間代碼 題目鏈接：Nim Game 思路：博弈論類型的題目。我們知道，如果是1，2，3，則先走的必勝，4，則先走的必敗?？偨Y(jié)規(guī)律得知，4的倍數(shù)時，先走的必敗。 算法復(fù)雜度： 時間：O(n) 空間：O(1) 代碼： class Solution(object): def canWinNim(sel...
摘要：題目鏈接題目分析給定一個字符串?dāng)?shù)組，每一個字符串有以下形式數(shù)字。直接計算得分。。代表上一輪分?jǐn)?shù)無效。思路這題沒什么好說的了。用區(qū)分各種情況，進行相應(yīng)處理即可。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 682. Baseball Game 題目鏈接 682. Baseball Game 題目分析 給定一個字符串?dāng)?shù)組，每一個字符串有以下形式： 數(shù)字。直接計算得分。 +。代表本輪...
摘要：腦筋急轉(zhuǎn)彎復(fù)雜度時間空間思路這題往小說可以追溯到小學(xué)奧數(shù)或者腦筋急轉(zhuǎn)彎的書中，往大說可以深究到博弈論。代碼如果一開始就是的倍數(shù)，你就輸了，因為對方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
閱讀 2001·2023-04-25 16:19
閱讀 3116·2021-11-24 09:39
閱讀 837·2021-11-16 11:44
閱讀 1699·2019-08-29 12:52
閱讀 1147·2019-08-26 13:33
閱讀 1081·2019-08-26 10:26
閱讀 2209·2019-08-23 16:42
閱讀 2574·2019-08-23 14:37
