题目描述
问题描述：给出4个1-10的数字，通过加减乘除，得到数字为24就算胜利
输入：
4个1-10的数字。[数字允许重复，但每个数字仅允许使用一次，测试用例保证无异常数字]
输出：
true or false
输入描述:
输入4个int整数
输出描述:
返回能否得到24点，能输出true，不能输出false
示例1
输入
7 2 1 10输出
true算法实现
// 题意是可以使用括号，数字可以交换位置，不需要使用所有数字，得到24就行
// 如8*(1+1+1) 其实就是输入 1 1 1 8,县逐步将3个1相加，再乘8
// (9 + 10) * 9 / 7 = 24(含小数，题库为false，所以讲原本的int calValue该为double,递归结束条件1多加了小数判断)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define DIGIT_CNT 4 // 4个数字
#define OPERATOR_CNT 4 // 4个操作符
#define MAX_USE_CNT 3 // 最多使用3个操作符
#define TARGET_VALUE 24 // 得到24
enum OPERATOR_EM
{ADDITION = 0, // 加SUBTRACTION, // 减MULTIPLICATION, // 乘DIVISION // 除
};
// 4个数字最多使用3个操作符
void Fun(const std::vector<int>& num, int operatorCnt, double calValue, bool &isGet24)
{// 递归结束条件if ((calValue - int(calValue ) == 0) && calValue == TARGET_VALUE)// 1.得到目标值{isGet24 = true;return;}else if (operatorCnt >= MAX_USE_CNT)// 2.操作符用完{return;}// 循环使用4个操作符中的3个for (int operatorEm = ADDITION; operatorEm <= DIVISION; ++operatorEm){// operatorCnt += 1;// 操作符使用次数加1(不能写在这，会将状态带给下层case)switch (operatorEm){case ADDITION:Fun(num, operatorCnt + 1, calValue + num[operatorCnt + 1], isGet24);break;case SUBTRACTION:Fun(num, operatorCnt + 1, calValue - num[operatorCnt + 1], isGet24);break;case MULTIPLICATION:Fun(num, operatorCnt + 1, calValue * num[operatorCnt + 1], isGet24);break;case DIVISION:Fun(num, operatorCnt + 1, calValue / num[operatorCnt + 1], isGet24);break;}// 每次得到一个结果都再次判断是否结束if (isGet24) return;}
}
int main()
{std::vector<int> num;num.resize(DIGIT_CNT);while (std::cin >> num[0] >> num[1] >> num[2] >> num[3]){bool isGet24 = false;std::sort(num.begin(), num.end());do// do while是保证当前升序序列先执行{Fun(num, 0, num.front(),isGet24);// 当前操作符使用次数0,当前值为num序列的front()if (isGet24) break;} while (next_permutation(num.begin(), num.end()));if (isGet24)std::cout << "true" << std::endl;elsestd::cout << "false" << std::endl;}return 0;
}