海盗分金问题
题目描述
有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(".\n"); 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:\n"); 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(".\n"); 94 } 95
96 printf("\n"); 97 printf("Please Enter gold and pirate number:\n"); 98 } 99 return 0; 100 }
决定下一步
本问题到此为止，暂时没有下一步动作。
总结
这个结论告诉我们：
（1）最先掌握分配权的人，看似最危险，胆小的人可能会担心所有人都不支持你，你就只能被杀死了。其实，他优先掌握了主动权，天下武功，唯快不破，掌握市场先机很重要。
（2）越快越好，但不能快过了头。100个金币，1000个海盗的话，最先出来分配的人必然死掉。同样的，20年前搞酒店搜索，率先占据了主动权，快得一塌糊涂那也没戏。
该题目源自：微博陈利人。
这是菜鸟我见这个问题分析的很透彻的一个帖子，感谢原作者。
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。