“海盗分金币”的程序解法

今天同学跟我讲海盗分金币这道IQ题，突然想这应该可以用程序来解，所以就尝试了一下：

 

命题 写道

有5个海盗抢到100个金币，他们都很贪婪，但又很聪明理智，所以他们商量出了个方法来分配，先抽签产生12345号，然后按顺序提出一个分配方案，如果未能超过半数，他就要被扔到海里喂鲨鱼，请问该怎么分配那自己才能拿最多的金币。

 

import java.util.ArrayList;
import java.util.Collections;

public class PirateProblem
{
	private static final int ALLCOINS = 100;
	public static void main(String[] args)
	{
		for (int numPirate = 2; numPirate < 8; numPirate++)//输出2个到7个海盗的情况
		{
			System.out.print(numPirate+"个海盗时：");
			int[] finalResult = solve(numPirate);
			for (int each : finalResult)
			{
				System.out.print(each + ",");
			}
			System.out.println();//换行
		}
	}

	public static int[] solve(int n)//递归解决
	{
		int[] result = new int[n];
		if (n == 2)
		{
			result[0] = ALLCOINS;
			result[1] = 0;
			return result;
		}

		int[] preResult = solve(n - 1);//假设少一个人的时候的结果
		ArrayList<Pirate> pirateList = new ArrayList<Pirate>();
		for (int index = 0; index < preResult.length; index++)//存入list中方便排序
		{
			pirateList.add(new Pirate(index, preResult[index]));
		}
		Collections.sort(pirateList);//排序
		for (int index = 0; index < preResult.length; index++)
		{
			Pirate temp = pirateList.get(index);
			if (index < (n / 2))//争取半数人同意
			{
				preResult[temp.getNumber()] = preResult[temp.getNumber()] +1;
			}
			else//其余的人不管
			{
				preResult[temp.getNumber()] = 0;
			}
		}
		int coinsGotByFirstPirate=ALLCOINS;//初始化为总硬币个数
		for (int index = 0; index < preResult.length; index++)
		{
			result[index+1]=preResult[index];
			coinsGotByFirstPirate-=preResult[index];//减去以分配出去的硬币个数
		}
		result[0]=coinsGotByFirstPirate;//第0个海盗的就是第一个海盗
		return result;
	}
}

其中有一个Pirate类：

public class Pirate implements Comparable<Pirate>
{
	private Integer number;
	private Integer coins;
	
	public Pirate(int number, int coins)
	{
		super();
		this.number = number;
		this.coins = coins;
	}
	public Integer getCoins()
	{
		return coins;
	}
	public Integer getNumber()
	{
		return number;
	}
	@Override
	public int compareTo(Pirate pirate)
	{
		return this.coins.compareTo(pirate.getCoins());
	}
}

结果：

2个海盗时：100,0,
3个海盗时：99,0,1,
4个海盗时：97,0,1,2,
5个海盗时：97,0,1,2,0,
6个海盗时：96,0,1,2,0,1,
7个海盗时：96,0,1,2,0,1,0,