题目描述
有5个海盗1、2、3、4、5，得到100个金币，决定分掉，分法怪异：首先A提出分法，B~E表决，如果不过半数同意，就砍掉A的头。然后由B来分，C~E表决，如果不过半数同意，就砍掉B的头。依次类推，如果假设强盗都足够聪明，在不被砍掉头的同时获得最多金币。问：最后结果如何？
定义问题
5个海盗必须按照上述规则，找出最优分配方案，否则将被其他人扔下大海。
当前状态
正确分配方案还没出来，必须尽快找出最优解。
分析
典型的nim取子问题的变形，采用倒推方式即可找出最优解。
制定解决方案
倒推方法如下所示。
（1）如果只有海盗，如何分配？
（2）如果有两个海盗，如何分配？
（3）如果有n个海盗，每个海盗至少需要几个人同意？找出n-1个海盗情况下的分配方案中，需要收买多少海盗？最低需要多少金币？
实现解决方案
倒推方法实现如下表所示，每一行表示一张人数情况下的分配方案，即，最后一行给出5号海盗的分配方案。
注意：从表中可以看出聪明是大前提，当然残忍也是。nim取子游戏向来是君子游戏，没有这个前提的弧，后面的海盗不按套路出牌就不可能有最优解。
标准化解决方案
从上表不难看出规律，也即，自己拿尽可能多的金币，同时保证后面的人依次分配0、1交错的金币数。规范化命题如下：
*命题：假设对于n个聪明、残忍的海盗（n>=1），抢了Gold个金币，要进行分配，每个人都想分配足够多的金币，他们寸步不让。分配顺序是：n号海盗>n-1号海盗….1号海盗，即是：先由n号海盗决定如何分配，若分配不均，n号被杀死，n-1号海盗再决定如何分配，依次类推。在该规则下，n号海盗最佳分配方案应当如此（为简单，避免使用地板函数，按n为奇偶数分类讨论）：
不妨假设ones为得到1个金币好海盗，zeros为得到0个金币的海盗数。
（1）当n为奇数时，ones = zeros = (n – 1) / 2，分配方案为Gold-ones，0,1,…….,0,1
（2）当n为偶数时，ones = （n – 2) / 2, zeros = n / 2，分配方案为Gold – ones,0,1,……1,0
该命题从上述分析中的规律中得出，不是定理，更不是公理，作为标准化解决方案需要严格证明。
证明：
注释：使用跳跃数学归纳法证明，跳跃的step为2。
先证明n为奇数时命题是否成立。
当n = 1时，显然该命题成立
假设当n = m（m > 1）时命题成立，则分配方案为
Ones(m) = Zeros(m) = ( m – 1) / 2
Proposa(m) = Gold – Ones(m),0,1,……,0,1
= Gold – (m – 1) / 2, 0,1…..,0,1
当n = m + 1时，显然命题成立，理由如下
Ones(m + 1) = (m + 1 – 2) / 2 = (m – 1) / 2，Zeros(m + 1) = (m + 1) / 2
注意：
（a）m+1为偶数，计算ones和zeros需要换个公式
（b）对比n=m情形，仅仅是多了个0
Proposal(m + 1) = Gold – Ones(m + 1), 0, 1,…..,0, 1, 0
= Gold – (m – 1)/2,0, 1, ……., 0, 1, 0
对比Ones(m), Ones(m + 1), Zeros(m), Zero(m + 1)可以看出仅仅是在Proposal(m)序列后面添个0。这回导致Proposal(m + 1)与Proposal(m)两个序列中，0,1交错序列刚好错位，对应金币分配方案中则为：m+1号海盗分配方案就是把Proposal(m)中没有得到金币的人每个给1个金币实现自己金币最大化，同时保证同意的人数大于等于2.
综上所述，当n为奇数时，该命题成立。
再证明n为偶数时命题是否成立。
当n = 2，命题成立（大于的最小偶数只能2）
归纳方法同1.
综合1、2分析，该命题成立。
证毕。
该标准化解决方案用程序实现如下
说明：该程序考虑了金币数量远小于海盗数量时，最先出来分配的部分海盗都被杀死了。
1 #include <stdio.h>
2
3 const int g_first = 2;
4 const int g_zero = 0;
5 const int g_one = 1;
6
7 int print_proposal(int *gold, int *pirate, int *ones, int *zeros, int *status)
8 {
9 int ret = 1;
10 int number = 0;
11 int remain = *gold - *ones;
12 if (*pirate <= 0)
13 {
14 printf(".
");
15 return 0;
16 }
17 if (remain <= 0)
18 {
19 number = 0; /* not enough gold, killed by others, regenerate proposal */
20 ret = 1; /* conitnue */
21
22 /* regenerate proposal */
23 if (*pirate % 2 == 0)
24 {
25 *ones = (*pirate - 2) / 2;
26 *zeros = *pirate / 2;
27 }
28 else
29 {
30 *ones = *zeros = (*pirate - 1) / 2;
31 }
32 }
33 else if (*status == g_one)
34 {
35 number = 1;
36 *ones--;
37 *status = g_zero;
38 }
39 else if (*status == g_zero)
40 {
41 number = 0;
42 *zeros--;
43 *status = g_one;
44 }
45 else {
46 number = remain;
47 *status = g_zero;
48 }
49 if (*status != g_first && *ones <= 0 && *zeros <= 0)
50 {
51 ret = 0;
52 }
53
54 printf("%d ", number);
55 *pirate = *pirate - 1;
56
57 return ret;
58 }
59
60 int main()
61 {
62 int gold;
63 int pirate;
64 int ones;
65 int zeros;
66 int temp;
67 int status; /* process first, zero or one */
68 printf("Please Enter gold and pirate number:
");
69 while (scanf("%d %d", &gold, &pirate) == 2)
70 {
71 if (pirate < 1 || gold < 1)
72 {
73 break;
74 }
75 if (pirate % 2 == 0)
76 {
77 ones = (pirate - 2) / 2;
78 zeros = pirate / 2;
79 }
80 else
81 {
82 ones = zeros = (pirate - 1) / 2;
83 }
84
85 status = g_first;
86 printf("Proposal(%d, %d) is: ", gold, pirate);
87 temp = pirate;
88 while (print_proposal(&gold, &temp, &ones, &zeros, &status))
89 ;
90
91 if(pirate == 1)
92 {
93 printf(".
");
94 }
95
96 printf("
");
97 printf("Please Enter gold and pirate number:
");
98 }
99 return 0;
100 }
决定下一步
本问题到此为止，暂时没有下一步动作。
总结
这个结论告诉我们：
（1）最先掌握分配权的人，看似最危险，胆小的人可能会担心所有人都不支持你，你就只能被杀死了。其实，他优先掌握了主动权，天下武功，唯快不破，掌握市场先机很重要。
（2）越快越好，但不能快过了头。100个金币，1000个海盗的话，最先出来分配的人必然死掉。同样的，20年前搞酒店搜索，率先占据了主动权，快得一塌糊涂那也没戏。
该题目源自：微博陈利人。
这是菜鸟我见这个问题分析的很透彻的一个帖子，感谢原作者。