题目这是源自生活中的一个经典小游戏。任意选出四张纸牌上面有四个数字J对应11 Q对应12 K对应13进行加减乘除运算最终得到24。要求每个纸牌上的数字必须且只能使用一次可以进行分数运算。不能进行平方、幂运算。#include bits/stdc.h using namespace std; // 分数结构体 struct Frac { int num, den; Frac(int n 0, int d 1) { if (d 0) { n -n; d -d; } int g __gcd(abs(n), d); num n / g; den d / g; } }; // 分数四则运算 Frac add(Frac a, Frac b) { return Frac(a.num*b.den b.num*a.den, a.den*b.den); } Frac sub(Frac a, Frac b) { return Frac(a.num*b.den - b.num*a.den, a.den*b.den); } Frac mul(Frac a, Frac b) { return Frac(a.num*b.num, a.den*b.den); } Frac divv(Frac a, Frac b) { if (b.num 0) return Frac(0,1); return Frac(a.num*b.den, a.den*b.num); } int n 4; Frac a[4]; string expr[4]; // 存储每个数字对应的表达式 bool used[4]; bool found false; void dfs(int cnt) { if (found) return; if (cnt 1) { for (int i 0; i 4; i) { if (!used[i]) { if (a[i].num 24 a[i].den 1) { found true; cout 可以计算出 24表达式为 endl; cout expr[i] 24 endl; } return; } } } for (int i 0; i 4; i) { if (used[i]) continue; for (int j i1; j 4; j) { if (used[j]) continue; Frac ti a[i], tj a[j]; string si expr[i], sj expr[j]; used[j] true; // 1. a b a[i] add(ti, tj); expr[i] ( si sj ); dfs(cnt-1); // 2. a - b a[i] sub(ti, tj); expr[i] ( si - sj ); dfs(cnt-1); // 3. b - a a[i] sub(tj, ti); expr[i] ( sj - si ); dfs(cnt-1); // 4. a * b a[i] mul(ti, tj); expr[i] ( si * sj ); dfs(cnt-1); // 5. a / b if (tj.num ! 0) { a[i] divv(ti, tj); expr[i] ( si / sj ); dfs(cnt-1); } // 6. b / a if (ti.num ! 0) { a[i] divv(tj, ti); expr[i] ( sj / si ); dfs(cnt-1); } // 恢复现场 a[i] ti; expr[i] si; a[j] tj; expr[j] sj; used[j] false; } } } int main() { cout 请输入四个 1-30 之间的自然数; for (int i 0; i 4; i) { cin a[i].num; a[i].den 1; expr[i] to_string(a[i].num); } found false; memset(used, false, sizeof(used)); dfs(4); if (!found) cout 无法计算出 24。 endl; return 0; }
自创题目：24点游戏
题目这是源自生活中的一个经典小游戏。任意选出四张纸牌上面有四个数字J对应11 Q对应12 K对应13进行加减乘除运算最终得到24。要求每个纸牌上的数字必须且只能使用一次可以进行分数运算。不能进行平方、幂运算。#include bits/stdc.h using namespace std; // 分数结构体 struct Frac { int num, den; Frac(int n 0, int d 1) { if (d 0) { n -n; d -d; } int g __gcd(abs(n), d); num n / g; den d / g; } }; // 分数四则运算 Frac add(Frac a, Frac b) { return Frac(a.num*b.den b.num*a.den, a.den*b.den); } Frac sub(Frac a, Frac b) { return Frac(a.num*b.den - b.num*a.den, a.den*b.den); } Frac mul(Frac a, Frac b) { return Frac(a.num*b.num, a.den*b.den); } Frac divv(Frac a, Frac b) { if (b.num 0) return Frac(0,1); return Frac(a.num*b.den, a.den*b.num); } int n 4; Frac a[4]; string expr[4]; // 存储每个数字对应的表达式 bool used[4]; bool found false; void dfs(int cnt) { if (found) return; if (cnt 1) { for (int i 0; i 4; i) { if (!used[i]) { if (a[i].num 24 a[i].den 1) { found true; cout 可以计算出 24表达式为 endl; cout expr[i] 24 endl; } return; } } } for (int i 0; i 4; i) { if (used[i]) continue; for (int j i1; j 4; j) { if (used[j]) continue; Frac ti a[i], tj a[j]; string si expr[i], sj expr[j]; used[j] true; // 1. a b a[i] add(ti, tj); expr[i] ( si sj ); dfs(cnt-1); // 2. a - b a[i] sub(ti, tj); expr[i] ( si - sj ); dfs(cnt-1); // 3. b - a a[i] sub(tj, ti); expr[i] ( sj - si ); dfs(cnt-1); // 4. a * b a[i] mul(ti, tj); expr[i] ( si * sj ); dfs(cnt-1); // 5. a / b if (tj.num ! 0) { a[i] divv(ti, tj); expr[i] ( si / sj ); dfs(cnt-1); } // 6. b / a if (ti.num ! 0) { a[i] divv(tj, ti); expr[i] ( sj / si ); dfs(cnt-1); } // 恢复现场 a[i] ti; expr[i] si; a[j] tj; expr[j] sj; used[j] false; } } } int main() { cout 请输入四个 1-30 之间的自然数; for (int i 0; i 4; i) { cin a[i].num; a[i].den 1; expr[i] to_string(a[i].num); } found false; memset(used, false, sizeof(used)); dfs(4); if (!found) cout 无法计算出 24。 endl; return 0; }
