11.13 Recursion: The pirate game problem

 

We can invoke function recursively to solve the pirate game problem.
The problem is like this:
Five pirates have a treasure of 100 gold coins. They decide to split the coins using schemes through drawing lot. Pirate No. 1 proposes how to share the coins, and all pirates (including pirate No.1) vote for or against it. If half or more of the pirates vote for it, the coins will be shared that way. Otherwise, pirate No.1 is thrown overboard. And the process is repeated among the remaining pirates.

imagepng

If there are two pirates remaining, Pirate No. 5 will vote against any schemes proposed by pirate No. 4 and take the 100 gold coins alone. Considering this, pirate No. 4 will vote for the scheme pirate No. 3 proposes anyway so that he can survive. Knowing the mind of pirate No. 4, the greedy pirate No. 3 will be sure to propose a scheme of [100,0,0]. The similar calculation also happens to pirate No. 2 and pirate No. 1.
We can still use func(c,…) function to perform the recursive operation.

SPL script:

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 If there are two pirates remaining, the last pirate takes the coins all alone.
B3 Use func() function to perform a recursive calculation to find the scheme the remaining pirates adopt if my proposition is denied.
B4-C4 Sort the scheme, and find the number of pirates, besides me, who need to vote in favor of my proposal.
B5-C5 Get the support of the most easily bribed pirates by allocating one more coin to each of them.
C6 Subtract the allocated coins from the total and I get all the remaining coins.
C7 The other pirates receive nothing.
B8 Return the coins I have and the modified scheme to get the best scheme for me.
A9 Execute func() function where 5 pirates and the 100 gold coins are parameters.

Execution result:

Member
97
0
1
2
0