11.13 函数递归:海盗分金问题

 

递归调用函数解决海盗分金问题。
海盗分金问题:
5 个海盗抢得 100 枚金币,他们按抽签的顺序依次提方案:首先由 1 号提出分配方案,然后 5 人表决,投票要超过半数同意方案才被通过,否则他将被扔入大海喂鲨鱼,依此类推。

imagepng

当只有两个海盗时,海盗 5 会否决海盗 4 的任何方案,独吞 100 金币。所以海盗 4 为了保命,会无条件同意海盗 3 方案。知道了海盗 4 的想法,贪婪的海盗 3 一定会给出 [100,0,0] 的分配方案。依此类推。
使用 func(c,…) 函数进行递归运算。

脚本:

A B C D
1 func
2 if(A1==2) return [-1,B1]
3 =func(A1,A1-1,B1)
4 =B3.psort() =A1/2
5 for B4.len() if (B5<=C4) =B3(B4(B5))+=1
6 >B1-=D5
7 else >B3(B4(B5))=0
8 return B1 | B3
9 =func(A1,5,100)

B2-C2 只有 2 个海盗时, 最后一个海盗全拿
B3 使用 func() 函数,递归计算自己被否决后,剩下海盗会采用的方案
B4-C4 对该方案排序, 计算除了自己还需要几个海盗支持
B5-C5 争取分配最少的海盗们支持,多给 1 金币
C6 总金币里扣除分配的金币,剩下是自己的
C7 剩下的海盗分配 0 金币
B8 返回自己剩下的金币和修改后的方案,就是自己的分配方案。
A9 执行 func() 函数,参数是 5 个海盗,100 个金币

运行结果:

Member
97
0
1
2
0