p292

发表于 | 分类于 |

LeetCode P292 Nim Game 题解

1.题目：

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

题意：

你和你的朋友互相拿地上的石头，你先动手，每个人一次只能拿1-3个，拿到最后那一个石头的胜利。

2.解题思路:

将对方置于3+1的困境是最好的战略
即留给对方的石头是4的整数倍必赢

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
package leetcode;

import java.util.Scanner;


/**
 * 
 * @author ZhangMengRou
 *
 */
public class p292 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String a = in.nextLine();

		boolean ans = canWinNim(Integer.parseInt(a));
		System.out.print(ans);
	}

	public static boolean canWinNim(int n) {

		if (n % 4 == 0) {
			return false;
		} else {
			return true;
		}

	}

}

4.一些总结：~