一件衣服需要5粒纽扣_一件衣服需要5粒纽扣[通俗易懂]

public class button {
	public static void main(String[] args) {
		test01();
//		test02();
	}

	/**
	 * 
	 * @param sum 题目中的总数
	 * @param y	成功集合，如果进行一次取值后的余数在该集合中，就可能会赢
	 * @param n	失败集合，如果进行一次取值后的余数在该集合中，就一定会输
	 * @param option 题目中可以取出的数集合
	 * @return	最终答案
	 */
	public static int backtrack(Integer sum, Set<Integer> y, Set<Integer> n, Set<Integer> option) {
		for (int i = 0; i <= sum; i++) {
			if (validate2(i, n, option)) {
				y.add(i);
			} else {
				n.add(i);
			}
		}
		for (Integer temp_option : option) {
			int test_result = sum - temp_option;
			for (Integer temp_y : y) {
				if (test_result == temp_y) {
					return temp_option;
				}
			}
		}
		return 0;
	}

	/**
	 * 
	 * @param a 待测试的数值
	 * @param n	失败集合，如果进行一次取值后的余数在该集合中，就一定会输
	 * @param option 题目中可以取出的数集合
	 * @return	如果必赢，则返回true，否则返回false
	 */
	public static boolean validate2(Integer a, Set<Integer> n, Set<Integer> option) {
		int validate = 0;
		for (Integer temp_option : option) {
			int result = a - temp_option;
			if (result >= 0) {
				for (Integer temp_n : n) {
					if (result == temp_n) {
						validate++; // 对面输了，我赢了
					}
				}
			} else {
				validate++;
			}
		}
		if (validate >= 3) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 *  共有16颗纽扣，两个人轮流从中取1或3或6粒，
	 *  谁取到最后一粒算赢，问保证一定获胜的策略是什么?
	 */
	public static void test01() {
		 int sum = 16;
		 int x = 0;
		 int a = 1;
		 int b = 3;
		 int c = 6;
		 Set<Integer> n = new HashSet<>();
		 Set<Integer> y = new HashSet<>();
		 Set<Integer> option = new HashSet<>();
		 y.add(x);
		 n.add(a);
		 n.add(b);
		 n.add(c);
		 option.add(a);
		 option.add(b);
		 option.add(c);
		 int daan = backtrack(sum, y, n, option);
		 System.out.println("最终答案是：" + daan);
	}

	/**
	 *  有102颗纽扣,两个人轮流从中取几粒,每人至少取1粒,最多取4粒,
	 * 	谁取最后一粒就算谁输.问保证一定获胜的策略是什么?
	 */
	public static void test02() {
		int sum = 102;
		int x = 0;
		int a = 1;
		int b = 2;
		int c = 3;
		int d = 4;
		Set<Integer> n = new HashSet<>();
		Set<Integer> y = new HashSet<>();
		Set<Integer> option = new HashSet<>();
		y.add(x);
		y.add(b);
		y.add(c);
		y.add(d);
		n.add(a);
		n.add(b);
		n.add(c);
		n.add(d);
		option.add(a);
		option.add(b);
		option.add(c);
		option.add(d);
		int daan = backtrack(sum, y, n, option);
		System.out.println("最终答案是：" + daan);
	}
}

结果：

今天的文章一件衣服需要5粒纽扣_一件衣服需要5粒纽扣[通俗易懂]分享到此就结束了，感谢您的阅读。