1. 项目概述:从“算24点”到C++实战编程
最近在整理旧项目时,翻出了一个大学时期用Visual Studio和C++写的“二十四点游戏”。这可不是一个简单的控制台小程序,它完整地实现了从随机发牌、表达式计算、到求解与验证的全流程。对于很多C++初学者,或者想找一个既有算法深度又有界面交互的练手项目来说,“二十四点”是个绝佳的选择。它麻雀虽小,五脏俱全:涉及随机数生成、数据结构(栈的应用)、算法(深度优先搜索)、字符串处理,以及最基础的命令行交互逻辑。如果你正在学习C++,厌倦了书本上的例题,想找一个能串联起多个知识点的综合实践,或者你是一位开发者,需要参考一个结构清晰、可扩展的游戏逻辑实现,那么这份源代码和背后的实现思路,或许能给你带来不少启发。接下来,我将带你深入这个项目的每一个核心模块,分享我当时的设计考量、踩过的坑以及优化思路。
2. 项目整体设计与核心思路拆解
2.1 游戏规则与核心挑战解析
“二十四点”的规则大家都不陌生:随机抽取4张扑克牌(通常用1-13代表A-K,其中1代表Ace,11、12、13代表J、Q、K),玩家需要使用加(+)、减(-)、乘(*)、除(/)四种运算符和括号,将这4个数字组合成一个表达式,使得表达式的计算结果等于24。每个数字必须且只能使用一次。
这个看似简单的游戏,对程序来说有几个核心挑战:
- 数字组合的全排列:4个数字,不同的排列顺序会影响运算结果,因此需要遍历所有可能的排列(4! = 24种)。
- 运算符的穷举:在数字之间插入运算符,每个位置有4种选择(+、-、*、/)。对于3个运算符位置,理论上有4³=64种组合,但结合括号后,实际有效的运算符插入模式(即运算优先级结构)是有限的。
- 运算结构的枚举:括号决定了运算的优先级。对于4个数,本质上是二叉树的所有可能形态。常见的结构有:
((a b) (c d))、(a (b (c d)))、(((a b) c) d)等。我们需要枚举所有可能的二叉树结构。 - 浮点数精度处理:由于涉及除法,结果可能是浮点数。判断结果是否等于24时,不能直接用
==,而需要判断其与24的差的绝对值是否小于一个极小的误差(如1e-6)。 - 表达式生成与去重:找到解法后,需要生成可读的表达式字符串。同时,不同的数字排列和运算符组合可能产生本质上相同的表达式(如加法、乘法的交换律),需要进行适当的去重或规范化,以提供更友好的答案。
2.2 技术栈选型与开发环境搭建
为什么选择Visual Studio和原生C++?这是基于教学、性能和可控性的综合考量。
开发环境:Visual Studio 2022
- 理由:VS提供了业界最强大的C++开发体验,特别是其调试器,对于理解递归、栈变化等复杂程序流至关重要。社区版完全免费,对学习者极其友好。其集成的项目管理系统(
.sln,.vcxproj)也让代码组织变得简单。 - 项目创建:创建一个新的“控制台应用”项目即可。确保使用C++17或更新的标准,以利用
std::optional、结构化绑定等现代特性简化代码。
核心C++标准库组件:
<vector>,<array>:用于存储数字集合、表达式元素和中间结果。<algorithm>:特别是next_permutation函数,用于优雅地生成数字的全排列,避免了手动编写递归排列算法的麻烦。<stack>:用于实现表达式求值,这是本项目算法部分的核心数据结构。<cmath>:使用fabs函数进行浮点数精度比较。<random>(C++11):取代传统的rand()和srand(),提供更可靠、分布更均匀的随机数生成,用于发牌。<string>,<sstream>:用于构建和输出表达式字符串。
注意:许多教学代码仍在使用
rand() % 13 + 1来生成1-13的随机数。这不仅是过时的,而且存在分布不均匀、周期性等问题。在现代C++中,务必使用<random>库。
2.3 系统架构设计
整个程序可以划分为几个相对独立的模块,遵循高内聚、低耦合的原则:
- 游戏控制模块 (GameController):负责游戏流程控制,包括欢迎界面、发牌、接受用户输入、判断对错、显示答案、开始新游戏等。
- 计算核心模块 (Solver):这是项目的“大脑”。接收4个数字,穷举所有可能的表达式,寻找结果为24的解,并返回所有找到的表达式字符串。
- 表达式求值模块 (Evaluator):被Solver调用。给定一个中缀表达式字符串(如
"(1+2)*(3+4)"),计算其浮点数结果。这里需要处理运算符优先级和括号,通常使用“双栈法”(操作数栈和运算符栈)将中缀表达式转为后缀表达式(逆波兰式)再求值,或者直接递归求值。 - 工具模块 (Utils):包含随机数生成器、精度比较函数、表达式规范化辅助函数等。
这种架构的好处是,Solver和Evaluator模块可以独立测试和复用。例如,你可以轻易地将命令行界面替换为图形界面(如Qt),而核心算法无需改动。
3. 核心算法实现细节与难点剖析
3.1 穷举算法的实现:排列、组合与结构
这是本项目最核心的部分。一种直观且易于实现的算法思路是:枚举数字的所有排列 -> 枚举所有可能的运算符组合 -> 枚举所有可能的括号结构(运算顺序)。
步骤一:数字全排列使用std::array<double, 4>存储4个数字。利用std::next_permutation函数,可以轻松遍历所有24种排列。记得在循环前先用std::sort对数组排序,因为next_permutation要求输入序列是升序的。
std::array<double, 4> nums = {a, b, c, d}; std::sort(nums.begin(), nums.end()); do { // 对当前排列nums进行后续操作 } while (std::next_permutation(nums.begin(), nums.end()));步骤二:运算符穷举运算符有4种,填充在3个位置。我们可以用一个三层循环来生成所有64种组合。
const std::array<char, 4> ops = {'+', '-', '*', '/'}; for (char op1 : ops) { for (char op2 : ops) { for (char op3 : ops) { // 当前运算符组合为 op1, op2, op3 } } }步骤三:括号结构枚举这是难点。对于4个数字,其运算本质是一棵有4个叶子节点(数字)的二叉树。我们可以递归地枚举所有可能的二叉树。一种实用的方法是“递归分割法”:对于数字序列nums[0..3],我们尝试在所有可能的位置i进行分割,将序列分成左子序列nums[0..i]和右子序列nums[i+1..3],然后分别递归计算左右子序列所有可能的结果集合,最后将左右集合的结果用当前运算符组合起来。
// 伪代码:递归函数,返回给定数字序列所有可能的运算结果及对应表达式 vector<pair<double, string>> getAllResults(vector<double> nums) { vector<pair<double, string>> res; if (nums.size() == 1) { // 基线条件:只有一个数字,直接返回该数字和它的字符串形式 res.emplace_back(nums[0], to_string(nums[0])); return res; } // 遍历所有分割点 for (int i = 0; i < nums.size() - 1; ++i) { auto leftResults = getAllResults(截取nums[0..i]); auto rightResults = getAllResults(截取nums[i+1..end]); // 遍历左右所有结果,用四种运算符组合 for (auto& [lVal, lExp] : leftResults) { for (auto& [rVal, rExp] : rightResults) { // 加法、乘法(满足交换律,可考虑去重) res.emplace_back(lVal + rVal, "(" + lExp + "+" + rExp + ")"); res.emplace_back(lVal * rVal, "(" + lExp + "*" + rExp + ")"); // 减法、除法(注意顺序,且除数不能为0) res.emplace_back(lVal - rVal, "(" + lExp + "-" + rExp + ")"); if (fabs(rVal) > 1e-6) { // 避免除零 res.emplace_back(lVal / rVal, "(" + lExp + "/" + rExp + ")"); } // 也可以考虑右减左、右除左,以覆盖更多情况 } } } return res; }调用getAllResults得到4个数字的所有可能结果和表达式后,遍历结果集,找出值接近24的项即可。
实操心得:这种递归分割法比显式地枚举括号位置更通用和清晰,并且很容易扩展到更多数字(虽然复杂度会爆炸式增长)。它直接对应了表达式树的构建过程。
3.2 表达式求值器的两种实现
Solver需要频繁计算表达式的值。我们可以选择在生成表达式字符串后求值,也可以在递归组合结果时直接计算数值。这里介绍两种求值器。
方法一:双栈法中缀转后缀求值这是数据结构课程的经典例题。算法步骤如下:
- 初始化一个操作数栈
numStack和一个运算符栈opStack。 - 遍历表达式字符串。
- 遇到数字,压入
numStack。 - 遇到运算符
op:- 如果
opStack为空或栈顶是(,直接压入。 - 否则,比较
op与栈顶运算符的优先级。如果op优先级不高于栈顶,则循环弹出栈顶运算符和两个操作数进行计算,结果压回numStack,直到条件不满足,再将op压栈。
- 如果
- 遇到
(,直接压入opStack。 - 遇到
),循环弹出opStack中的运算符并计算,直到遇到(,弹出(。 - 遍历结束后,将
opStack中剩余运算符依次弹出计算。 - 最后
numStack栈顶即为结果。
方法二:递归求值如果表达式是以二叉树或类似(leftExp op rightExp)的字符串形式生成的,可以直接递归求值,逻辑更直观,且天然处理了优先级。
double evaluate(const string& exp) { // 假设exp是“(A op B)”的形式,或者是一个纯数字 // 需要先解析出最外层的操作符和左右子表达式,这是一个简化的示意 // 实际实现需要处理字符串解析的细节 }在“递归分割法”中,我们实际上采用了类似方法二的思路,在组合表达式时直接计算了数值,避免了字符串的反复解析,效率更高。
3.3 精度处理与表达式规范化
浮点数精度:这是必须小心处理的坑。因为除法可能产生无限循环小数,用double存储会有精度损失。判断两个浮点数a和b是否“相等”,应使用:
bool isEqual(double a, double b) { return std::fabs(a - b) < 1e-6; // 1e-6是一个常用的误差阈值 }在判断结果是否为24时,就使用isEqual(value, 24.0)。
表达式规范化与去重:由于数字排列和运算符组合的穷举,会产生大量重复或本质相同的解。例如,(1+2)+3+4和1+(2+3)+4计算结果相同,但字符串不同。更复杂的,加法和乘法满足交换律,a+b和b+a是等价的。实现完全的去重比较复杂,一个实用的简化策略是:
- 在递归分割时,对于加法和乘法,强制规定左子表达式的“某种值”(如字符串哈希或排序后的数字序列)不大于右子表达式,否则不生成该分支。这需要定义一种表达式的规范形式。
- 或者,在收集所有解后,对表达式字符串进行简单的标准化(如去除不必要的括号),然后使用
std::unordered_set<string>进行去重。 - 对于教学项目,也可以选择不去重,或者只去除完全字符串相同的解,这已经能大大改善输出。
4. 完整实现流程与关键代码解读
4.1 项目文件结构
一个清晰的项目结构有助于管理代码。建议如下:
24PointGame/ ├── 24PointGame.sln # Visual Studio解决方案文件 ├── 24PointGame/ │ ├── 24PointGame.vcxproj # 项目文件 │ ├── Source Files/ │ │ ├── main.cpp # 程序入口,游戏主循环 │ │ ├── GameController.cpp/.h # 游戏流程控制 │ │ ├── Solver.cpp/.h # 24点求解器核心 │ │ ├── ExpressionEvaluator.cpp/.h # 表达式求值器(如果单独实现) │ │ └── Utils.cpp/.h # 工具函数 │ └── Resource Files/ # 如有图标等资源4.2 核心类与函数设计
Solver类:
// Solver.h #pragma once #include <vector> #include <string> #include <array> class Solver { public: // 主求解函数,输入4个数字,返回所有找到的解法表达式 static std::vector<std::string> solve(const std::array<double, 4>& numbers); private: // 递归分割法的核心实现 static std::vector<std::pair<double, std::string>> dfs(const std::vector<double>& nums); // 辅助函数:判断是否为24 static bool is24(double value); // 辅助函数:生成规范化表达式(可选) static std::string normalizeExp(const std::string& exp); };GameController类:
// GameController.h #pragma once #include <array> class GameController { public: void run(); // 启动游戏 private: void showWelcome(); std::array<double, 4> drawCards(); // 随机发牌 void showCards(const std::array<double, 4>& cards); bool getPlayerInput(std::string& expression); // 获取玩家输入的表达式 bool validateExpression(const std::string& exp, const std::array<double, 4>& cards); // 验证表达式合法性 double calculateExpression(const std::string& exp); // 计算表达式值 void showSolutions(const std::array<double, 4>& cards); // 显示所有解 };4.3 主程序流程 (main.cpp)
#include "GameController.h" int main() { // 设置随机数种子 std::random_device rd; std::mt19937 gen(rd()); GameController game; game.run(); return 0; }4.4 关键代码片段:Solver::solve 的实现
这里展示递归分割法求解的核心逻辑。注意,为了清晰,省略了详细的表达式字符串拼接和部分错误处理。
std::vector<std::string> Solver::solve(const std::array<double, 4>& numbers) { std::vector<std::string> solutions; std::vector<double> numList(numbers.begin(), numbers.end()); // 首先对数字排序,用于生成排列 std::sort(numList.begin(), numList.end()); // 关键:使用递归函数获取所有可能的结果 auto allResults = dfs(numList); // dfs返回 vector<pair<值, 表达式>> for (const auto& [value, expression] : allResults) { if (is24(value)) { // 可能需要对expression进行后处理,比如去除最外层多余括号 std::string finalExp = expression; // 简单去重:检查solutions中是否已存在相同字符串的表达式 if (std::find(solutions.begin(), solutions.end(), finalExp) == solutions.end()) { solutions.push_back(finalExp); } } } return solutions; } // 递归分割函数 std::vector<std::pair<double, std::string>> Solver::dfs(const std::vector<double>& nums) { std::vector<std::pair<double, std::string>> res; if (nums.size() == 1) { // 基线条件:单个数字,直接返回其值和字符串形式 // 注意:整数直接转,浮点数可能需处理.0的情况 std::string exp = std::to_string((int)nums[0]); // 简单处理,假设都是整数牌 res.emplace_back(nums[0], exp); return res; } // 遍历所有可能的分割点 for (size_t i = 0; i < nums.size() - 1; ++i) { // 分割左半部分 nums[0..i] std::vector<double> left(nums.begin(), nums.begin() + i + 1); // 分割右半部分 nums[i+1..end] std::vector<double> right(nums.begin() + i + 1, nums.end()); auto leftRes = dfs(left); auto rightRes = dfs(right); // 组合左右两部分的所有结果 for (const auto& [lVal, lExp] : leftRes) { for (const auto& [rVal, rExp] : rightRes) { // 加法 res.emplace_back(lVal + rVal, "(" + lExp + "+" + rExp + ")"); // 乘法 res.emplace_back(lVal * rVal, "(" + lExp + "*" + rExp + ")"); // 减法 (左减右) res.emplace_back(lVal - rVal, "(" + lExp + "-" + rExp + ")"); // 减法 (右减左) - 覆盖更多情况 res.emplace_back(rVal - lVal, "(" + rExp + "-" + lExp + ")"); // 除法 (左除以右),确保除数不为零 if (std::fabs(rVal) > 1e-6) { res.emplace_back(lVal / rVal, "(" + lExp + "/" + rExp + ")"); } // 除法 (右除以左) if (std::fabs(lVal) > 1e-6) { res.emplace_back(rVal / lVal, "(" + rExp + "/" + lExp + ")"); } } } } return res; }5. 常见问题、调试技巧与优化方向
5.1 编译与运行常见问题
“无法打开源文件...”或“未定义的标识符”:
- 检查:确保所有
.cpp文件都已添加到项目的“源文件”筛选器中,所有.h文件都在“头文件”筛选器下,或在#include时使用了正确的相对或绝对路径。 - 检查:在Visual Studio中,右键点击项目 -> “属性” -> “C/C++” -> “常规” -> “附加包含目录”,确保包含了自定义头文件所在的目录。
- 检查:确保所有
程序运行后立即退出:
- 在
main函数末尾(return 0;之前)添加system("pause");或std::cin.get();,以便在控制台窗口停留查看输出。更推荐的做法是在VS中按Ctrl+F5(开始执行不调试)运行,程序结束后会提示“按任意键继续”。
- 在
随机数每次运行都一样:
- 你很可能错误地使用了
std::mt19937 gen(123);(固定种子)。确保使用std::random_device来获取真随机种子:std::mt19937 gen(std::random_device{}());。
- 你很可能错误地使用了
5.2 算法逻辑调试技巧
- 输出中间结果:在递归函数
dfs的关键位置(如进入函数、组合结果时)打印当前的数字集合、左右部分的值和表达式,可以帮助你理解程序的枚举过程,并发现逻辑错误。 - 使用小型测试用例:不要一开始就用4个随机数测试。使用
{1, 2, 3, 4}这样有明确解的例子,手动推导几个解,然后对比程序输出。 - 利用Visual Studio调试器:
- 设置断点:在
Solver::solve和dfs函数开始处设置断点。 - 监视窗口:添加监视
nums(当前数字向量)、left、right、res等变量。 - 调用堆栈:当程序停在递归深处时,查看“调用堆栈”窗口,可以清晰地看到递归的层级和每一步的参数,对于理解递归流程至关重要。
- 逐语句(F11)与逐过程(F10):灵活使用,深入函数内部或跳过函数调用。
- 设置断点:在
5.3 性能优化与扩展思路
- 剪枝优化:在递归组合时,如果中间结果已经出现非有限值(如无穷大
INF、NaN),或者已经远远超过24(例如在纯乘法中,数字都大于1,结果很快会远大于24),可以提前终止该分支的进一步计算,节省大量时间。 - 记忆化搜索:对于相同的数字集合(不考虑顺序),其所有可能的运算结果集合是相同的。可以使用一个哈希表(
map<vector<double>, vector<pair<double, string>>>)来存储已经计算过的数字集合的结果,避免重复计算。这对于多次求解或数字更多时效果显著。 - 并行计算:数字的全排列是相互独立的。可以使用C++11的
<thread>或<future>库,将不同的排列分配给多个线程同时求解,充分利用多核CPU。注意线程间共享数据(如结果容器)需要加锁或使用线程安全容器。 - 支持更多运算符:可以很容易地扩展支持乘方(
^)、阶乘(!)等运算符,只需在递归组合部分增加相应的运算分支,并注意新运算符的优先级和定义域(如阶乘要求整数且不能太大)。 - 图形化界面:使用Qt、wxWidgets或简单的Windows API为游戏添加图形界面。将发牌显示为扑克牌图片,提供数字和运算符按钮让用户点击组合,并实时验证表达式,体验会好很多。
5.4 表达式验证的陷阱
在GameController::validateExpression中,验证玩家输入的表达式是否合法是一个挑战。你需要检查:
- 是否只使用了给定的4个数字,且每个数字只用了一次。
- 是否只使用了允许的运算符。
- 括号是否匹配。
- 除数是否为零(在求值前做语法检查时可能难以判断,可以在求值过程中捕获异常或检查结果是否为
INF/NaN)。
一个相对稳健的做法是:将玩家输入的表达式字符串,用你自己的表达式求值器(或一个简化版的解析器)解析成一棵语法树或一个RPN序列,在这个过程中同时检查语法和数字使用情况。如果解析成功且使用了正确的数字,再计算其值并与24比较。
这个用Visual Studio和C++实现二十四点游戏的项目,虽然代码量不大,但几乎触及了初级到中级C++编程的多个关键知识点:从基本的控制流、函数、类,到STL容器的使用、算法库的调用,再到递归、回溯、栈应用等核心算法思想,最后还涉及浮点数精度、字符串处理等实用技巧。它完美地诠释了“小游戏,大道理”。在实现过程中,最深的体会是设计清晰的程序结构比一开始就追求完美的算法更重要。先让程序能正确跑起来,得到结果,然后再考虑优化(如剪枝、去重)和扩展(如GUI)。调试递归函数时,耐心和调试器的熟练使用是成功的关键。最后,将这个项目作为你C++学习路上的一个里程碑,它的完整实现会给你带来巨大的成就感,并为你理解更复杂的软件系统打下坚实的基础。