1、我们首先以一堆为例： 假设现在只有一堆石子，你的最佳选择是将所有石子全部拿走，那么你就赢了。

2、如果是两堆：假设现在有两堆石子且数量不相同，那么你的最佳选择是取走多的那堆石子中多出来的那几个，使得两堆石子数量相同，这样，不管另一个怎么取，你都可以在另一堆中和他取相同的个数，这样的局面你就是必胜。比如有两堆石子，第一堆有3个，第二堆有5个，这时候你要拿走第二堆的三个，然后两堆就都变成了3个，这时你的对手无论怎么操作，你都可以“学”他，比如他在第一堆拿走两个，你就在第二堆拿走两个，这样你就是稳赢的

3、如果是三堆 ，我们用（a，b，c）表示某种局势，首 先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是 （0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一
下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情型。
从中我们要明白两个理论：

一个状态是必败状态当且仅当它的所有后继都是必胜状态
一个状态是必胜状态当且仅当它至少有一个后继是必败状态

有了这两个规则，就可以用递推的方法判断整个状态图的每一个结点都是必胜还是必败状态。

也就是当Nim和！= 0时，先手胜利，否则失败

计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示这种运算。这种运算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2加的结果：

0 =二进制00 （注意不进位）

对于奇异局势（0，n，n）也一样，结果也是0。

任何奇异局势（a，b，c）都有a（+）b（+）c =0。

如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只要将 c 变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将c 变为a（+）b，只要从 c中减去 c-（a（+）b）即可。也就是取走（a（+）b）个石子。这里我们要了解异或运算的一个特点 a（+）c（+）c = a

9.3 利用空瓶换饮料，最多喝几瓶

问题：1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶？
拿走3瓶，换回1瓶，相当于减少2瓶。但是最后剩下4瓶的时候例外，这时只能换1瓶。所以我们计算1000减2能减多少次，直到剩下4.（，996/2=498）所以1000减2能减498次直到剩下4瓶，最后剩下的4瓶还可以换一瓶，所以总共是=1499瓶。


• 1000瓶饮料，3个空瓶子能换1瓶饮料，最多可以喝几瓶？
• 第一种思维：可以考虑成dp思路
• 初始情况，3个瓶子时将发生一次交换，因此视为特殊情况
• 之后每增加两个瓶子又可以再换一瓶
• (i - (i - 2))，即为当前增加的2瓶饮料（写成这样便于理解）
• 1即为增加了2个空瓶，之后又可以换一瓶饮料

• 特殊情况：从上面的分析中，留下2个瓶子
• 剩下998个瓶子相当于每消耗2个瓶子即可获得一瓶，即为499瓶
• 最后剩下的2个瓶子无法再进行兑换，因此总共为1000 + 499 = 1499
• 第二种思维：利用借瓶子的思想
• 因为兑换一瓶饮料需要三个空瓶，这瓶饮料如果是找老板借来的，那么喝完后这个空瓶将会还给他，同时需要附赠给他另外两个空瓶，即每消耗手里两个空瓶就获得一瓶饮料
• 但是值得注意的是，上面只是一种假设，实际情况老板是不会借给你的，因此我们至少需要保留2个空瓶，这样可以在998个瓶子剩下一个瓶子时，对其进行补足为3个空瓶，从而兑换一瓶新饮料
• 此时使用998个瓶子进行上述的兑换，将获得499瓶饮料
• 之前留下的两个瓶子正好无法兑换，最终获得饮料为1000 + 499 = 1499瓶

问题：有8个数，11-22-33-44，将其排列，要求结果满足：两个1之间有一个数，两个2之间有两个数，两个3之间有三个数，两个4之间有四个数。问这个结果是多少？

10.2 给定随机函数，生成别的随机数

问题：给定生成1到5的随机数Rand5()，如何得到生成1到7的随机数函数Rand7()？
思路 ：由大的生成小的容易，比如由Rand7()生成Rand5()，所以我们先构造一个大于7的随机数生成函数。 记住下面这个式子：

• 可以看作是在数轴上撒豆子。N是跨度/步长，是RandN()生成的数的范围长度，
• RandN()-1的目的是生成0到N-1的数，是跳数。后面+RandN()的目的是填满中间的空隙

11.1 乒乓球重量问题：8个乒乓球，其中一个重，有一个秤，问至少几次能够找出重的那个乒乓球

2次，分成3堆，3，3，2。
①称3和3，如果一样重，代表重的在2。
①称3和3，不一样重，重的在3里面重的那堆。
②3个里面随便取2个，一样重，第三个重，不一样重，重的那个就是。

11.2 盐重量问题：有7克、2克砝码各一个，天平一只，如何只用这些物品五次内将140克的盐分成50、90克各一份？

第一次：先分成70和70
第二次：通过7和2砝码将70分成9和61
第三次：通过9克盐和2砝码将61分成50和11

11.3 有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？

天平一边放三个砝码，哪边轻就在哪边，一样重就在剩下的三个砝码中；
现在已经锁定了三个砝码，天平一边放一个，哪边轻是哪个，一样重就是剩下的那个；

11.4 十组砝码每组十个，每个砝码都是10g重，但是现在其中有一组砝码每个都只有9g重，现有一个能显示克数的秤，最少称几次能找到轻的那组？

11.5 药丸问题：有20瓶药丸，其中19瓶装有1克/粒的药丸，余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次；

• 从药瓶#1取出一粒药丸，从药瓶#2取出两粒，从药瓶#3取出三粒，依此类推。
• 如果每粒药丸均重1克，则称得总重量为210克（1 + 2 + … + 20 = 20 * 21 / 2 = 210），“多出来的”重量必定来自每粒多0.1克的药丸。
• 药瓶的编号可由算式(weight - 210) / 0.1 得出。因此，若这堆药丸称得重量为211.3克，则药瓶#13装有较重的药丸。

11.6 药丸问题：你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了？

从第一盒中取出一颗，第二盒中取出2 颗，第三盒中取出三颗。
依次类推，称其总量。减去10，多的数字就是药丸罐子序号。

12.1 在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分那个开关控制那一盏灯？

打开一个开关，过10分钟后关掉开关，并打开另一个开关。进屋确认可知：

• 亮的灯是由第二次打开的开关控制；
• 摸上去发热的不发亮的灯是由第一次打开的开关控制
• 剩下的第三盏灯是由未操作过的开关控制。

12.2一个圆环上有 100 个灯泡，灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。设计一种算法，对于任意初始状态，使所有灯泡全亮。

步骤一：将灯泡变为全亮或只剩一个为暗
从 1 循环到 98 ，遇到暗的则按它下一个，使之变亮。循环完毕，1 ~ 98 必然全亮。99 和 100可能为亮亮、暗亮、亮暗、暗暗四种状态。

• 若为亮亮，皆大欢喜，满足题目要求
• 暗亮、亮暗，达到只剩一个为暗的状态；
• 若为暗暗。则按下编号 100 的灯泡，使编号 99 、100 变为亮，编号 1 的灯泡变为暗，从而达到只剩一个为暗的状态。

步骤二：将灯泡变为全暗
由于灯泡环形摆放，我们指定暗的灯泡编号为 1 ，将剩下 99 个亮着的灯泡每 3 个为一组。按下每组中间的灯泡后，使得所有灯泡变为暗。
步骤三：将灯泡变为全亮
将所有灯泡按一下，灯泡变为全亮;
对于 N 个灯泡的任意初始状态 ( N > 3 ) ，能否经过若干次操作使得所有灯泡全亮？
答案：N 个灯泡做分类讨论。

• N = 3*k+1一定可以。方法与上述步骤相同，在步骤二中可以将3k个亮的灯泡分为k组。
• N = 3*k+2一定可以。将上述步骤一目标状态的只剩一个为暗改成剩两个相邻为暗，其余 3 * k 个灯泡分组按即可。因为，对于任意只剩一个为暗的状态，按下该灯泡左右任意一个就可以变成剩两个相邻为暗的状态！
• N = 3*k不一定。如果经过上述步骤一可以将灯泡变成全亮的状态则有解；否则，无解。（该结论有待证明）

对于这道题，以下两个状态可以相互转化
大家可以琢磨下，对理解这道题会有帮助。

• 全暗 <=> 全亮。全暗和全亮状态可以相互转化，方法就是将每个灯泡按一次。这样每个灯泡都被改变了 3 次状态，使得全暗变为全亮，全亮也可变为全暗。
• 剩一个为暗 <=> 剩两个相邻为暗。剩一个为暗时，按下该灯泡左右任意一个，就变成了剩两个相邻为暗的状态；剩两个相邻为暗时，按下第二个暗，便可变成了剩一个为暗的状态。

问题：有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人是蓝眼睛的，只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛？
有多少个蓝眼睛的人就会花多少天。

假设岛上所有人都是聪明的，蓝眼睛的人四处观察之后，发现没有人是蓝眼睛的。但他知道至少有一人是蓝眼睛的，于是就能推导出自己一定是蓝眼睛的。因此，他会搭乘当晚的飞机离开。 两个蓝眼睛的人看到对方，并不确定c是1还是2，但是由上一种情况，他们知道，如果c = 1，那个蓝眼睛的人第一晚就会离岛。因此，发现另一个蓝眼睛的人仍在岛上，他一定能推断出c = 2，也就意味着他自己也是蓝眼睛的。于是，两个蓝眼睛的人都会在第二晚离岛。 逐步提高c时，我们可以看出上述逻辑仍旧适用。如果c = 3，那么，这三个人会立即意识到有2到3人是蓝眼睛的。如果有两人是蓝眼睛的，那么这两人会在第二晚离岛。因此，如果过了第二晚另外两人还在岛上，每个蓝眼睛的人都能推断出c = 3，因此这三人都有蓝眼睛。他们会在第三晚离岛。
不论c为什么值，都可以套用这个模式。所以，如果有c人是蓝眼睛的，则所有蓝眼睛的人要用c晚才能离岛，且都在同一晚离开。

问题：有50家人家，每家一条狗。有一天警察通知，50条狗当中有病狗，行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病，而不能看自己家的狗，如果判断出自己家的狗病了，就必须当天一枪打死自己家的狗。结果，第一天没有枪响，第二天没有枪响，第三天开始一阵枪响，问：一共死了几条狗？
死了3条（第 几天枪响就有几条）。
从有一条不正常的狗开始，显然第一天将会听到一声枪响。这里的要点是你只需站在那条不正常狗的主人的角度考虑。有两条的话思路继续，只考虑有两条不正常狗的人，其余人无需考虑。通过第一天他们了解了对方的信息。第二天杀死自己的狗。换句话说每个人需要一天的时间证明自己的狗是正常的。有三条的话，同样只考虑那三个人，其中每一个人需要两天的时间证明自己的狗是正常的狗。

问题：一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
答案：有三个人戴黑帽。
假设有N个人戴黑帽，当N＝1时，戴黑帽的人看见别人都为白则能肯定自己为黑。于是第一次关灯就应该有声。可以断定N＞1。对于每个戴黑帽的人来说，他能看见N-1顶黑帽，并由此假定自己为白。但等待N-1次还没有人打自己以后，每个戴黑人都能知道自己也是黑的了。所以第N次关灯就有N个人打自己。