验证骰子组合

Question

我正在 Android 中构建一个名为 Thirty Throws 的应用程序，但我完全无法进行验证。在 Thirty Throws 中，您的骰子得分为 4、5、6、7、8、9、10、11、12 和 6。每回合包含 3 次掷骰，用户可以在每次掷骰之间选择他希望保留的骰子。示例说用户掷出了 4,4,3,5,1,5 那么他可以选择分数 11 因为 4 + 4 +3 = 11 和 5 + 1 + 5 = 11 或者如果用户掷出了 2,2 ,2 他可以选择 6。我正在努力验证分数。我目前拥有的代码能够验证最多。我错过了什么？我一直在寻找一些递归解决方案，但它们似乎不是我正在寻找的，因为我必须返回一个布尔值。public static boolean isValidResult(ArrayList<Integer> score, int selectedPoints){    ArrayList<Integer> notReadyNumbers = new ArrayList<>();    for (int i: score) {        if (i == selectedPoints) {            continue;        }        if (CalcSum(notReadyNumbers) + i == selectedPoints) {            notReadyNumbers.clear();        } else {            boolean isDone = false;            if (notReadyNumbers.size() > 0) {                for (int z: notReadyNumbers) {                    if (z + i == selectedPoints) {                        isDone = true;                    }                }            }            if (isDone) {                notReadyNumbers.clear();            } else {                notReadyNumbers.add(i);            }        }    }    return notReadyNumbers.size() == 0 ? true : false;}

Answer 1

您应该从任何位置获取所有可能的数字。因此，为了获得所有可能的结果，您可以使用这些数字的排列来序列化这些数字。另一种方法是使用带递归的位掩码。这是您的问题的解决方案。（基于位掩码和递归）。

public static boolean isValidResult(ArrayList<Integer> score, int selectedPoints)

{

    return canMakeValid(score, selectedPoints, 0, 0); // first 0 is for masking, second 0 is for summation.

}

public static boolean canMakeValid(ArrayList<Integer> score, int selectedPoints, int mask, int sum) 

{

    if(sum > selectedPoints) return false;

    sum %= selectedPoints;

    int sz = score.size();

    if(mask == ((1<<sz)-1)) {

        if(sum == 0) return true;

        return false;

    }

    boolean ret = false;

    for(int i = 0; i < sz; i++) {

        if((mask&(1<<i)) == 0) {

            ret = ret | canMakeValid(score, selectedPoints, mask | (1<<i), sum + score.get(i));

        }

    }

    return ret;

}

您可以从此链接了解位掩码：https://discuss.codechef.com/t/a-small-tutorial-on-bitmasking/11811/3

Answer 2

确实有一些递归解决方案。

public static boolean isValidResult(List<Integer> score, int selectedPoints) {

    score.sort();

    return isValidResultRec(score, selectedPoints, 0);

}

/**

 * @param scoreI the first position to consider to add or not add.

 */

private static boolean isValidResultRec(List<Integer> score, int selectedPoints, int scoreI) {

    while (!score.isEmpty() && scoreI < score.size()) {

        int index = Collections.binarySearch(score, selectedPoints);

        if (index >= 0) {

           return true;

        }

        // Now ~index is the insert position;

        // i >= ~index are values > selectedPoints.

        score = score.subList(~index, score.size());

        for (int i = scoreI; i < ~index; ++i) {

            int value = score[i]; // value < selectedPoints.

            score.remove(i); // Do step.

            if (isValidResultRec(score, selectedPoints - value, scoreI + 1) {

                return true;

            }

            score.add(i, value); // Undo step.

        }

    }

    return false;

}

这里使用排序；使用递减顺序、Comparator.reversed()或 afor --i将采取更大的步骤。

递归应该添加或不添加第 i个骰子值。

这里的代码可以写得更好。