java - 保加利亚纸牌 Java

Question

我的 AP 计算机科学类(class)的以下作业将在几天后到期:

“在此作业中，您将为保加利亚纸牌游戏建模。游戏从 45 张纸牌开始。将它们随机分成若干堆，大小随机。例如，您可以从大小为 20、5、1 的纸牌开始, 9, 和 10. 在每一轮中，你从每堆中拿一张牌，用这些牌形成新的一堆。例如，示例起始配置将转换为大小为 19、4、8、10 和 5 的堆。当纸堆大小依次为 1、2、3、4、5、6、7、8 和 9 时，纸牌游戏结束。

在您的程序中，生成一个随机的起始配置并打印它。然后继续应用纸牌步骤并打印结果。当达到纸牌最终配置时停止。”

我想出了一个解决这个问题的程序，但问题是有时需要很长时间。其他时候它会像我预期的那样几乎立即解决它，但其他时候它可以迭代 18,000 次或更多。

根据 http://mancala.wikia.com/wiki/Bulgarian_Solitaire可以在 (k^2)-k 步或更短的时间内找到解决方案，在这种情况下 k 为 9。很多时候我肯定不会在 72 步或更少的时间内找到解决方案。我已经看了这个程序好几个小时了，弄乱了不同的东西，看看我是否可以让它更快，但我就是无法让它在足够多的迭代中工作。所以现在我来到 Stack Overflow 看看你们是否可以帮助我朝着正确的方向前进。

这是我的代码:

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

public class BulgarianSolitaire {

    ArrayList<Integer> cards = new ArrayList<Integer>();
    Random rand = new Random();
    boolean cont = true;
    boolean cont2 = true;

    public static void main(String[] args) {
        BulgarianSolitaire game = new BulgarianSolitaire();
    }

    public BulgarianSolitaire() {
        System.out.println("Started");
        int sum = 0;
        while (cont) {
            if (sum < 45) {
                cards.add(rand.nextInt(46 - sum));
            } else {
                cont = false;
            }

            sum = 0;
            for (int i = 0; i < cards.size(); i++) {
                sum += cards.get(i);
            }

            removeZeros(cards);

            System.out.println(cards);
        }

        System.out.println("Finished Generating Start");

        while (cont2) {
            solitaireStep();
            System.out.println(cards);
            if (checkCards()) {
                cont2 = false;
            }
        }

        Collections.sort(cards);
        System.out.println("Cards are sorted");
        System.out.println(cards);
    }

    public void removeZeros(ArrayList<Integer> list) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) == 0) {
                list.remove(j);
            }
        }
    }

    public void solitaireStep() {

        int numberRemoved = 0;

        for (int i = 0; i < cards.size(); i++) {
            int value = cards.get(i);
            cards.set(i, value - 1);
            removeZeros(cards);
            numberRemoved++;
        }

        cards.add(numberRemoved);
    }

    public boolean checkCards() {
        ArrayList<Integer> expectedCards = new ArrayList<Integer>();

        for (int i = 1; i < 10; i++) {
            expectedCards.add(i);
        }

        ArrayList<Integer> sortedCards = cards;
        Collections.sort(sortedCards);
        boolean equal = true;
        if (sortedCards.size() != expectedCards.size()) {
            equal = false;
        }

        for (int i = 0; i < sortedCards.size(); i++) {
            if (sortedCards.size() == expectedCards.size()) {
                if (sortedCards.get(i) != expectedCards.get(i)) {
                    equal = false;
                }
            }
        }

        return equal;
    }
}

所以我基本上首先生成一个介于 0 到 45 之间的随机数，然后将其添加到卡片列表中。然后我继续生成随机数，只要和小于45就放到列表中，这样生成的随机数在0到45之间——上一次迭代里面的数的和。列表中的零也会随着它的进行而被删除。

列表生成后，它将执行以下步骤:从列表中的每个数字中减去 1，删除零并添加一个等于减少的堆栈数的新值。它还会根据列表 {1, 2, 3, 4, 5, 6, 7, 8, 9} 检查卡片堆的有序版本，一旦找到匹配项，它就会将 boolean 值 cont2 设置为 false，这样它将停止执行单人纸牌游戏步骤。

就是这样。我感谢任何可以提供帮助的人。

Answer 1

您的缺陷在于您的removeZeros 方法。

public void removeZeros(ArrayList<Integer> list) {
    for (int j = 0; j < list.size(); j++) {
        if (list.get(j) == 0) {
            list.remove(j);
        }
    }
}

如果您删除 j 处的元素，则列表大小将减少 1。您也必须减少 j。

为此更改:

  public void removeZeros(ArrayList<Integer> list) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) == 0) {
                list.remove(j);
                j--;
            }
        }
    }

你的检查方法也太复杂了。

在您的单人纸牌步骤中，将所有应为零的值设置为零。

然后，在循环之外移除零(使用修改后的方法)。

然后，对数组进行排序。

然后，在您的检查方法中，由于数组已排序:

public boolean checkCards() {
    for(int i = 0; i < cards.size(); i++) {
        if(cards.get(i) != i + 1) {
            return false;
        }
    }
    return true;
}

简单多了。并且有效。