验证骰子组合

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.

我正在努力验证分数。我目前拥有的代码能够验证最多。我错过了什么？

我一直在寻找一些递归解决方案，但它们似乎不是我要找的，因为我必须 return 一个布尔值。

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(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() 或 for --i 会采取更大的步骤。

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

这里的代码可以写的更好

Answer 2

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

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;
}

您可以从这个link了解bit-masking：https://discuss.codechef.com/t/a-small-tutorial-on-bitmasking/11811/3

验证骰子组合

Validate combination of dice

java

algorithm

validation

android

dice