趣味数学编程题解之海盗分金问题
IT商界
题目：海盗分金问题
现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗提出分配方案，然后大家一人一票表决，如果有50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鲨鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。
我们先要对海盗们作一些假设。
(1)每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为海盗除了自己谁都不相信。
(2)一枚金币是不能被分割的，不可以你半枚我半枚。
(3)每个海盗当然不愿意自己被丢到海里去喂鲨鱼，这是最重要的。
(4)每个海盗当然希望自己能得到尽可能多的金币。
(5)每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。
(6)最后，每个海盗都很希望其他海盗被丢到海里去喂鲨鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鲨鱼。
现在，如果有10个海盗要分100枚金币，情况将会怎样？
问题分析
要解决这类问题，我们总是从最后的情形向前推，这样我们就知道在最后这一步中什么是好的和坏的决定。
以这个思路，先考虑只有两个海盗的情况(所有其他的海盗都已经被丢到海里去喂鲨鱼了)。设他们为P1和P2，其中P2比较凶猛。P2的最佳方案当然是：他自己得100枚金币，P1得0枚。投票时他自己的一票就足够50%了。
往前推一步。现在加一个更凶猛的海盗P3。P1知道──P3知道他知道──如果P3的方案被否决了，游戏就会只由P1和P2来继续，而P1就一枚金币也得不到。所以P3知道，只要给P1一点点甜头，P1就会同意他的方案(当然，如果不给P1一点甜头，反正什么也得不到，P1宁可投票让P3去喂鲨鱼)。所以P3的最佳方案是：P1得1枚，P2什么也得不到，P3得99枚。
P4的情况差不多。他只要得两票就可以了，给P2一枚金币就可以让他投票赞同这个方案，因为在接下来P3的方案中P2什么也得不到。P5也采用相同的推理方法只不过他要说服他的两个同伴，于是他给在P4方案中什么也得不到的P1和P3一枚金币，自己留下98枚。
依此类推，P10的最佳方案是：他自己得96枚，给每一个在P9方案中什么也得不到的P2、P4、P6和P8一枚金币。
下面是以上推理的一个表(Y表示同意，N表示反对)：
P1 P2
0 100
N Y
P1 P2 P3
1 0 99
Y N Y
P1 P2 P3 P4
0 1 0 99
N Y N Y
P1 P2 P3 P4 P5
1 0 1 0 98
Y N Y N Y
……
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
0 1 0 1 0 1 0 1 0 96
N Y N Y N Y N Y N Y
编程实现
有了上面的分析，我们的程序实质上就是对上述分析问题方法的模拟。
10个人，这自然可通过一个数组来实现，对于我们来说重要的是这10个人所分得的金子的数量。
上面的规律细看一下其实就是奇数次和偶数次的不同，以及同一次分配中第奇数号人的全同特点和偶数号人的全同特点。当然还不能忽略最后一个人，这个人不符合上面的特点。
所以我们的程序也就是循环和分支的组合。
语言、界面、源程序
(1)语言
程序通过Virual BASIC6.0语言来实现。
(2)界面
界面非常简单，建立一标准EXE工程，其caption设为“海盗分金”，并加入两个命令按钮cmdsplit和cmdexit，caption改为“分金”和“退出”，再在其中加入一个文本框，用来输出结果，其名称为txtlist，多行属性multiline设为true，并将其scrollbar(滚动条)设为2，也就是竖条的形式，一切OK。我们将代码加给cmdsplit_Click()即查找按钮的单击事件，将来运行时，我们只要用鼠标单击一下按钮，程序就执行了。
(3)源程序
Dim p(1 To 10) As Integer
Private Sub CmdExit_Click()’退出
Unload Me
End Sub
Private Sub Cmdsplit_Click()’分金按钮
Dim i, j As Integer
TxtList.Text = ""
For i = 2 To 10
'分金
For j = 1 To i
If i Mod 2 = 0 Then
If j Mod 2 <> 0 Then
p(j) = 0
Else
p(j) = 1
End If
If j = i Then p(j) = 100-(i/2)+1
Else
If j Mod 2 <> 0 Then
p(j) = 1
Else
p(j) = 0
End If
If j = i Then p(j) = 100-(i-1)/2
End If
Next j
'输出
For j = 1 To i
TxtList.Text = TxtList.Text+tr(p(j))
Next j
TxtList.Text = TxtList.Text+vbCr+vbLf
Next i
End Sub
(以上程序在VB6.0、Win2000下调试通过)
编后：的趣味数学编程题解的系列文章到此结束了。数学题虽然在实际的生活、工作中可能应用得并不广泛，但每一道题都给了在学编程和想学编程的朋友们很多提示和一些学习要点。山东的作者赵玉勇告诉小编，学编程很枯燥，但能找到有趣的方法对编程的学习其实很有帮助。在这个系列学习的过程中，很多热心的读者朋友为我们提出了许多宝贵的意见，也提出了很多题的另类解法。我们目前正在整理更优秀的解题思路，会在近期刊登出来，请多关注。