海賊の金貨問題とコードの実現

4543 ワード

興味深い質問を見ました
5人の海賊A、B、C、D、Eが100枚の金貨を奪った.彼らは順番に案を提出した.まずAが分配案を提出し、それから5人が採決し、半数以上の同意案が可決された.そうしないと、彼は海に投げ込まれてサメに餌をやる.自分の収益が同じ場合、より多くの人を殺すことを選択します.最後に彼らの分配案はどうですか.
私の推理プロセス:
この問題を押すと、5人から直接始めると、「海賊は十分頭が良く、収益が最大化し、できるだけ人を殺す」という論理的な泥沼に陥り、考えを整理することはできないが、逆押すと簡単になる.
  • 海賊D、E:Dが2人しか残っていないと仮定すると、自分が1枚も持っていなくても、Eは反対票を投じて彼を殺す.Eは十分に残忍で、それから100金貨を得るからだ.割当シナリオ:0-100
  • 3個のC、D、E:DはどうしてもCが殺されないことを保証しなければならない.そうしないと、2つしか残っていないとき、自分も必ず死ぬに違いない.だから、彼は金貨を1枚受け取っても分けられない.割当シナリオ:100-0-0
  • B、C、D、E:CはいつもBを投げたいと思っています.彼を投げたら自分で100金貨を手に入れることができます.Dなら、もしBを投げたら、自分は金貨を手に入れられないと思って、もし自分が1元を手に入れたら、Bを投げないと思っています.Eは、Bが死ぬと、自分は0元しか得られないので、Bが1元さえ分かれば、彼を守ると思っています.割当シナリオ:98-0-1-1
  • 個のA、B、C、D、E:B:必ずAが死ぬことを望んでいます.C:もしAが死んだら、自分で0元を得ることができます.だから、彼に1元をあげてから、彼の投票D、E:Aが死んだら、彼らは一人一人が1元を得ることができます.Aは彼ら2人の中の1枚の投票を得なければなりません(C 1元をあげるほうがお得ですから)、彼らの中の1つに2元をあげます.もう1つはあげません.割り当てスキーム:97-0-1-2-0または97-0-1-0-2
  • 问题补充:もし海贼の数量が固定しないならば、金货の数量も固定しないで、甚だしきに至っては金货は海贼より更に少なくて、どのように分けますか?
    プログラマーとして、このような問題は必然的にコード実装でより一般的な解決策を得る必要があります.次に、私の実装を示します.現在は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 + ", "); } } } }