您的当前位置：首页【算法分析与设计】【第三周】679. 24 Game
【算法分析与设计】【第三周】679. 24 Game
来源：锐游网
题目来源：https://leetcode.com/problems/24-game/
周三刚复习了DFS，这周就做点有意思的题——求24点。相信求24点是大家的童年回忆，玩法也很简单：拿出一副完整的扑克牌，然后把花牌和10以上的牌全部清理掉，只剩下数字的牌A-9放在一起，代表1-9。分配好以后每人拿出2张牌出来，看谁先想到24点。加减乘除都可以，但是4张牌必须都用上。
这周的题目就是模拟这个游戏过程。值得一提的是，在本题中，诸如
-1-1-1-1这类表达式是非法的。可以进行括号运算，且
除法是小数除法。
思路：利用DFS。求24点也是DFS经典应用之一。把所有的数字放好，然后列举所有可能的运算。
以nums[4] = {4, 1, 7, 8}为例。
利用DFS先算一轮加法：
以nums[4] = {4, 1, 7, 8}为例。
利用DFS先算一轮加法：
画了一棵二叉树。
求得4+1+8+7！=24，于是回头，
接着画这棵二叉树。
打印所有nums[0]验证一下：
保证除法是小数除法也很容易：先处理一下传入的数组，把整型都转换为双精度型，便于小数除法运算。
bool dfs(double* nums, int numsSize) {
printf("%.1f ", nums[0]);
if(numsSize == 1) {
if(fabs(nums[0]-24)<1e-2) return true;
else return false;
}
double a,b;
for(int i = 0; i < numsSize; i++) {
for(int j = i+1; j < numsSize; j++) {
a = nums[i];
b = nums[j];
nums[j] = nums[numsSize-1];
nums[i] = a+b;
if(dfs(nums, numsSize-1)) return true;
nums[i] = a-b;
if(dfs(nums, numsSize-1)) return true;
nums[i] = b-a;
if(dfs(nums, numsSize-1)) return true;
nums[i] = a*b;
if(dfs(nums, numsSize-1)) return true;
//除法分母不为0
if(b != 0) nums[i] = a/b;
if(dfs(nums, numsSize-1)) return true;
if(a != 0) nums[i] = b/a;
if(dfs(nums, numsSize-1)) return true;
//回溯
nums[i]=a;
nums[j]=b;
}
}
return false;
}
bool judgePoint24(int* nums, int numsSize) {
double nums2double[numsSize]; // 保证除法是小数除法
for(int i = 0; i < numsSize; i++) {
nums2double[i] = *(nums+i);
}
if (dfs(nums2double, numsSize)) return true;
else return false;
}
参考：http:///qq_29963431/article/details/50826756
因篇幅问题不能全部显示，请点此查看更多更全内容