題目連結:
題目意譯:
你正在與你的一個朋友玩以下之拈(Nim)的遊戲:有一個石頭堆在桌子上,每次你們之一輪番地移除 1 到 3 顆石頭。移除最後一個石頭的人即為贏家。而你一定會是第一個先移除石頭的人。
你們兩個都相當地聰明,且對於本遊戲有最佳的策略。撰寫一個函式去判斷在給定石頭堆的石頭數下,你是否可以贏此遊戲。
範例測資:
範例:
輸入: 4
輸出: false
解釋: 如果堆裡有 4 個石頭,則你一定無法贏得此局遊戲;
不管你移除 1 、 2 或是 3 顆石頭,最後一顆石頭必定會由你的朋友移掉。
解題思維:
顯而易見地,當石頭數 = 1 、 2 或是 3 時,你必勝。
當石頭數 = 4 時,你不管拿 1 、 2 、 還是 3 顆石頭,都等價於石頭數 = 3 、 2 或是 1 且你的朋友擔任先手的狀況。因此,你必輸。
而石頭數 = 5 時,可以只拿 1 顆,使得整個遊戲等價於你的朋友為先手且石頭數為 4 。此時你的朋友必輸,因此你必贏。
同理石頭數 = 6 或 7 時,可以只拿 1 或 2 顆使得你自己必贏。
而到 8 顆石頭時,又變為必輸。
以此類推。因此可以看到當石頭數為 4 的倍數時,你必輸。其他情況下,則必贏。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。