我正在 Android 中構建一個名為 Thirty Throws 的應用程序，但我完全無法進行驗證。在 Thirty Throws 中，您的骰子得分為 4、5、6、7、8、9、10、11、12 和 6。每回合包含 3 次擲骰，用戶可以在每次擲骰之間選擇他希望保留的骰子。示例說用戶擲出了 4,4,3,5,1,5 那么他可以選擇分數(shù) 11 因為 4 + 4 +3 = 11 和 5 + 1 + 5 = 11 或者如果用戶擲出了 2,2 ,2 他可以選擇 6。我正在努力驗證分數(shù)。我目前擁有的代碼能夠驗證最多。我錯過了什么？我一直在尋找一些遞歸解決方案，但它們似乎不是我正在尋找的，因為我必須返回一個布爾值。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;}
2 回答
長風秋雁
TA貢獻1757條經(jīng)驗 獲得超7個贊
您應該從任何位置獲取所有可能的數(shù)字。因此，為了獲得所有可能的結果，您可以使用這些數(shù)字的排列來序列化這些數(shù)字。另一種方法是使用帶遞歸的位掩碼。這是您的問題的解決方案。（基于位掩碼和遞歸）。
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
斯蒂芬大帝
TA貢獻1827條經(jīng)驗 獲得超8個贊
確實有一些遞歸解決方案。
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個骰子值。
這里的代碼可以寫得更好。
添加回答
舉報
0/150
提交
取消