海賊の金貨問題とコードの実現
5人の海賊A、B、C、D、Eが100枚の金貨を奪った.彼らは順番に案を提出した.まずAが分配案を提出し、それから5人が採決し、半数以上の同意案が可決された.そうしないと、彼は海に投げ込まれてサメに餌をやる.自分の収益が同じ場合、より多くの人を殺すことを選択します.最後に彼らの分配案はどうですか.
私の推理プロセス:
この問題を押すと、5人から直接始めると、「海賊は十分頭が良く、収益が最大化し、できるだけ人を殺す」という論理的な泥沼に陥り、考えを整理することはできないが、逆押すと簡単になる.
プログラマーとして、このような問題は必然的にコード実装でより一般的な解決策を得る必要があります.次に、私の実装を示します.現在は1つのスキームを見つけることしかサポートされていません.
import java.util.HashSet;
import java.util.Set;
/**
* :
*
* M N , :
* , , , , ,
* M , , , 。
*
* :
*/
public class PiratePuzzle {
//
private int coinCount = 100;
//
private int pirateCount = 5;
public PiratePuzzle(int coinCount, int pirateCount) {
this.coinCount = coinCount;
this.pirateCount = pirateCount;
}
public int[] resolvePuzzle() {
return getDistribution(pirateCount);
}
/**
* , ,
*
* @param currPirateCountTotal
* @return
*/
private int[] getDistribution(int currPirateCountTotal) {
if (currPirateCountTotal == 1) {
return new int[]{coinCount};
} else {
int minsufficient[] = getDistribution(currPirateCountTotal - 1);
// System.out.println("
" + (currPirateCountTotal - 1) + " :");
// for (int goldCount : minsufficient) {
// System.out.print(goldCount + ", ");
// }
return getDistributionByMin(minsufficient);
}
}
/**
*
*
* @param othersMinDistribution
* @return
*/
private int[] getDistributionByMin(int[] othersMinDistribution) {
//
int countToatal = (othersMinDistribution.length + 1) / 2 + 1;
int finalResolve[] = new int[othersMinDistribution.length + 1];
int others[] = findBestSolution(othersMinDistribution, countToatal - 1);
int othersSum = 0;
for (int i = 0; i < others.length; i++) {
finalResolve[i + 1] = others[i];
othersSum += others[i];
}
finalResolve[0] = coinCount - othersSum;
return finalResolve;
}
/**
* , , +1
* : ,
*
* @param array
* @param count
* @return +1
*/
private int[] findBestSolution(int array[], int count) {
int minTest = 0;
int found = 0;
Set indexSet = new HashSet<>();//
while (found < count) {
for (int j = array.length - 1; j >= 0; j--) {
if (minTest == array[j]) {
found++;
indexSet.add(j);
}
if (found == count) {
break;
}
}
minTest++;
}
// 0
for (int i = 0; i < array.length; i++) {
if (!indexSet.contains(i)) {
array[i] = 0;
} else if (array[i] < coinCount) {
array[i] += 1;
}
}
return array;
}
public static void main(String[] args) {
PiratePuzzle pp = new PiratePuzzle(10, 25);
int solution[] = pp.resolvePuzzle();
if (solution[0] < 0) {
System.out.println("
, !!!");
} else {
System.out.println("
" + (solution.length) + " :");
for (int goldCount : solution) {
System.out.print(goldCount + ", ");
}
}
}
}