解题思路
这是一个24点游戏求解问题。需要判断给定的4张牌是否能通过四则运算得到24点。
关键规则
-
输入规则：
- 输入4张牌，以空格分隔
- 2~10对应数值2~10
- J、Q、K、A分别为11、12、13、1
- 不含joker/JOKER
-
运算规则：
- 只能使用加(+)、减(-)、乘(*)、除(/)
- 运算顺序从左到右
- 除法要确保除数不为0
实现思路
-
预处理：
- 建立牌面到数值的映射
- 定义四则运算函数
-
求解过程：
- 生成所有可能的牌的排列
- 对每个排列尝试所有运算符组合
- 按照从左到右的顺序计算
- 找到结果为24的组合
代码
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;
class Solution {
private:
map<string, int> card_order = {
{"A",1}, {"2",2}, {"3",3}, {"4",4}, {"5",5}, {"6",6}, {"7",7},
{"8",8}, {"9",9}, {"10",10}, {"J",11}, {"Q",12}, {"K",13}
};
vector<string> opts = {"+", "-", "*", "/"};
double cal(double a1, double a2, int opt) {
if (opt == 0) return a1 + a2;
if (opt == 1) return a1 - a2;
if (opt == 2) return a1 * a2;
if (opt == 3) return a2 != 0 ? a1 / a2 : numeric_limits<double>::infinity();
return numeric_limits<double>::infinity();
}
public:
void solve24(vector<string>& cards) {
// 检查王牌
if (find(cards.begin(), cards.end(), "joker") != cards.end() ||
find(cards.begin(), cards.end(), "JOKER") != cards.end()) {
cout << "ERROR" << endl;
return;
}
// 生成排列
vector<string> nums = cards;
sort(nums.begin(), nums.end());
do {
for (int i = 0; i < 4; i++) {
double a = cal(card_order[nums[0]], card_order[nums[1]], i);
for (int j = 0; j < 4; j++) {
double b = cal(a, card_order[nums[2]], j);
for (int k = 0; k < 4; k++) {
double c = cal(b, card_order[nums[3]], k);
if (abs(c - 24) < 1e-10) {
cout << nums[0] << opts[i] << nums[1] << opts[j]
<< nums[2] << opts[k] << nums[3] << endl;
return;
}
}
}
}
} while (next_permutation(nums.begin(), nums.end()));
cout << "NONE" << endl;
}
};
int main() {
string card;
while (cin >> card) {
vector<string> cards;
cards.push_back(card);
for (int i = 0; i < 3; i++) {
cin >> card;
cards.push_back(card);
}
Solution sol;
sol.solve24(cards);
}
return 0;
}
import java.util.*;
public class Main {
static class Solution {
private Map<String, Integer> card_order = new HashMap<String, Integer>() {{
put("A",1); put("2",2); put("3",3); put("4",4); put("5",5);
put("6",6); put("7",7); put("8",8); put("9",9); put("10",10);
put("J",11); put("Q",12); put("K",13);
}};
private String[] opts = {"+", "-", "*", "/"};
private double cal(double a1, double a2, int opt) {
if (opt == 0) return a1 + a2;
if (opt == 1) return a1 - a2;
if (opt == 2) return a1 * a2;
if (opt == 3) return a2 != 0 ? a1 / a2 : Double.POSITIVE_INFINITY;
return Double.POSITIVE_INFINITY;
}
public void solve24(String[] cards) {
// 检查王牌
for (String card : cards)
if (card.equals("joker") || card.equals("JOKER")) {
System.out.println("ERROR");
return;
}
List<String[]> perms = new ArrayList<>();
generatePermutations(cards.clone(), 0, perms);
for (String[] nums : perms) {
for (int i = 0; i < 4; i++) {
double a = cal(card_order.get(nums[0]), card_order.get(nums[1]), i);
for (int j = 0; j < 4; j++) {
double b = cal(a, card_order.get(nums[2]), j);
for (int k = 0; k < 4; k++) {
double c = cal(b, card_order.get(nums[3]), k);
if (Math.abs(c - 24) < 1e-10) {
System.out.println(nums[0] + opts[i] + nums[1] + opts[j] +
nums[2] + opts[k] + nums[3]);
return;
}
}
}
}
}
System.out.println("NONE");
}
private void generatePermutations(String[] arr, int start, List<String[]> result) {
if (start == arr.length) {
result.add(arr.clone());
return;
}
for (int i = start; i < arr.length; i++) {
swap(arr, start, i);
generatePermutations(arr, start + 1, result);
swap(arr, start, i);
}
}
private void swap(String[] arr, int i, int j) {
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String[] cards = new String[4];
for (int i = 0; i < 4; i++)
cards[i] = sc.next();
Solution sol = new Solution();
sol.solve24(cards);
}
}
}
from itertools import permutations
card = ['A','2','3','4','5','6','7','8','9','10','J','Q','K']
order = range(1,14)
card_order = dict(zip(card,order))
opts = ["+", "-", "*", "/"]
def cal(a1,a2,opt):
if opt == 0: return a1+a2
elif opt == 1: return a1-a2
elif opt == 2: return a1*a2
elif opt == 3: return a1/a2 if a2 != 0 else float('inf')
def cal24(cards):
if "joker" in cards or "JOKER" in cards:
print("ERROR")
return
num_orders = permutations(cards, 4)
for nums in num_orders:
for i in range(4):
a = cal(card_order[nums[0]], card_order[nums[1]], i)
for j in range(4):
b = cal(a, card_order[nums[2]], j)
for k in range(4):
c = cal(b, card_order[nums[3]], k)
if abs(c - 24) < 1e-10:
print(f"{nums[0]}{opts[i]}{nums[1]}{opts[j]}{nums[2]}{opts[k]}{nums[3]}")
return
print("NONE")
return
while True:
try:
cards = input().split()
cal24(cards)
except:
break
算法及复杂度
算法分析
-
预处理：
- 建立牌面到数值的映射关系
- 定义四则运算函数
-
求解过程：
- 生成4个数的全排列
- 对每个排列尝试所有运算符组合
- 按照从左到右的顺序计算结果
复杂度分析
- 时间复杂度：
- 4!种数字排列
- 每个位置4种运算符选择
- 空间复杂度：
- 只需要常量额外空间
京公网安备 11010502036488号