简介汉诺塔是经典的递归算法实例要求将多个盘子从起始柱借助辅助柱移至目标柱并保证大盘始终在小盘之下。这份C课程设计资源围绕该问题提供可直接运行的Visual Studio工程与源码适合正在学习递归算法与数据结构的在校学生也可供准备课程设计者参考。包内共五个文件cpp源代码实现核心移动逻辑dsp与dsw维护工程配置和项目结构ncb和opt保存编译辅助信息压缩包仅7KB轻量便携目前已有207人学习下载。源码利用moveDisk函数递归调用先移动上方n-1个盘子再移动最下层大盘最后将辅助柱上的盘子回移并逐步打印每一步移动方向。读者可直接编译运行观察不同盘子数量下的移动序列深入体会递归终止条件与分治思想同时也能巩固C函数定义、参数传递和标准输入输出等基础知识为后续更复杂的算法设计打下扎实基础。1. 别再交三行递归C课程设计汉诺塔需要完整工程提到C课程设计之汉诺塔源代码很多同学的第一反应是太简单递归三行就能搬完网上随手一搜一大堆。但真正到了验收就会明白这题的反直觉之处——代码越短越难做成课程设计因为老师要看的不是那三行移动逻辑而是一个完整程序该有的东西菜单和输入校验、移动过程可见、步数与复杂度有量化说明甚至要能回答“递归为什么不会无限递归”。按一条能交、能答、能演示的路线展开先把递归原理立住再给一套可编译的工程写法最后把常见翻车点逐个说透。这条路适合第一次做C课程设计的人也适合想靠这个题拿加分演示的人。2. 递归拆分与调用栈为什么汉诺塔天生适合分治2.1 先做纸上推演四句话把n层问题拆成三步汉诺塔的规则只有两条一次只能搬一个盘大盘永远不能压在小盘上。课程设计偏爱汉诺塔的原因是它的解法结构本身就是标准递归式分解问题规模从n降到n-1但处理方式不变天然能讲清楚“分治”这个抽象概念。做程序之前先在纸上把搬运方案写出来。假设三个柱子分别叫A起始柱、B辅助柱、C目标柱要把n个盘从A整体搬到C只需要完成三件事第一把A顶上的n-1个盘搬到B这一步完全借用C作为辅助柱第二把A底部第n个盘直接搬到C这是一次真正的单盘移动第三把B上的n-1个盘搬到C这一次轮到A做辅助柱。关键点在于第一步和第三步里“整体搬n-1个盘”这件事本身就是原问题的缩小版所以可以继续拆成三步直到n变成1。写成C代码时不需要手工计算每一步的顺序只需要把柱子身份正确传递下去移动顺序由递归自动展开。void hanoi(int n, char from, char aux, char to) { if (n 1) { cout from - to endl; // 递归出口单盘直接移动 return; } hanoi(n - 1, from, to, aux); // 第一步n-1个盘 from - aux cout from - to endl; // 第二步底盘 from - to hanoi(n - 1, aux, from, to); // 第三步n-1个盘 aux - to }参数说明n是当前要搬的盘数from是这一层递归里的出发柱aux是辅助柱to是目的柱。每一次递归调用都在重新命名三个柱子的身份盘子的编号并不需要显式传入底层大盘的顺序靠递归深度天然保证。初学者最容易看晕的地方就在这里aux和to在两次递归里的角色是互换的人脑去模拟递归很容易乱编译器却只认参数顺序。2.2 递归出口、栈帧与停止性为什么这个函数不会无限调用递归最怕的是“看似调用了自己实际上没有逼近出口”。上面代码里出口写的是n 1时直接return而每次递归传入的参数都是n-1所以当n从5一路减到1递归总会停下来这个性质叫“递归的停止性”。如果去掉这个出口函数会一直调自己直到栈空间耗尽程序崩溃。这里有一个常见的边界设计争论出口能不能写成n 0我一般不建议初级课程设计这么写。用n 0作为出口意味着要允许“搬0个盘”的调用存在代码表面少了一次判断但会多一次无效返回更麻烦的是一旦写成if (n 0) returnn小于0的非法输入也会被直接吞掉程序根本不知道输入错了。从工程角度讲出口设在n 1配合调用前检查n 1语义最清楚答辩被问边界条件时也最好讲。调用栈是理解这个程序的第二个重点。每调用一次hanoiC就在栈上分配一块栈帧保存当前n、三个柱子参数和返回地址递归到最深层时栈里同时存在的帧数正好等于n。默认栈空间一般在8MB左右每一个栈帧虽然很小但n达到几万层时仍可能溢出。汉诺塔课程设计通常只处理个位数到二三十层的盘子不会真有栈溢出问题但这个概念答辩时经常被问到。先记住“最大栈深度等于递归层数等于盘子数”就能解释大多数运行异常。有不少同学会问既然递归可以写成循环为什么不把汉诺塔直接用循环这里有个编译原理层面的原因汉诺塔的递归有两个自身调用而且第二次调用需要等第一次返回后再执行这个“等待”状态必须存在栈上所以编译器无法用尾递归优化把它改写成普通循环。也就是说只要还用这种自然的递归写法调用栈就是必然存在的不是额外开销。2.3 最少步数是定值2^n - 1 与复杂度量化汉诺塔的移动次数是可以精确计算的这给课程设计提供了一个天然的正确性标尺。用T(n)表示把n个盘从一根柱子搬到另一根需要的步数按前面三步拆分可以得到递推式T(1) 1T(n) 2 * T(n-1) 1。把这个递推式展开结果就是T(n) 2^n - 1。这组数字非常直观5个盘是31步10个盘是1023步20个盘约105万步64个盘约1.8乘以10的19次方步。程序跑出来的步数与2^n-1对不上说明递归分解写错了如果对得上至少说明移动次数层面的逻辑成立。这个指数增长还有两个课程设计里必须处理的后果第一步数增长很快程序不能只靠疯狂打印来展示要提供延迟、暂停和步进第二步数有可能超出int和long的表示范围需要在计数器上做类型选择。这两点分别对应后面的实现章节和避坑章节现在先记住汉诺塔的正确性不是靠肉眼盯着屏幕看完的而是靠步数校验、状态校验和复杂度说明来证明的。3. 三文件工程与核心move函数从空项目到可编译的汉诺塔程序3.1 文件组织与程序骨架不要把所有代码塞进一个main.cpp课程设计提交时老师通常要的是一个工程而不是一段代码。如果把全部代码塞进单个main.cpp编译虽然简单但代码可读性差头文件、实现、测试三者混杂答辩时也不好讲。常见做法是拆成三个文件main.cpp放菜单和输入处理hanoi.h放类或函数声明hanoi.cpp放递归实现和演示控制。这种拆分的好处是接口和实现分离。hanoi.h里的声明就是一份说明书别人只看头文件就知道这个程序能做什么hanoi.cpp里的实现可以单独修改不影响调用方。下面给一个最小但完整的头文件示例// hanoi.h #ifndef HANOI_H #define HANOI_H class Hanoi { public: Hanoi(); // 构造初始化计数器和延迟参数 void run(); // 程序入口菜单 输入 递归演示 private: void move(int n, char from, char aux, char to); // 递归核心 int diskCount; // 用户输入的盘数 unsigned long long stepCount; // 移动步数计数器 unsigned delayMs; // 每步之间的演示延迟 }; #endif参数说明diskCount保存用户输入的层数stepCount用来统计已经执行的移动次数delayMs控制演示速度。用类而不是全局函数组织代码是因为计数器、延迟、盘子数都作为成员变量存在不需要靠全局变量传递全局变量在递归演示里很容易被误改后面避坑章节会专门提到。3.2 核心move函数的参数语义from/aux/to为什么是“参数”而不是“状态”递归版汉诺塔最容易写错的地方不是递归本身而是移动函数里三个柱子的传递顺序。很多同学的思路是“程序里应该维护三个数组代表柱子”移动时不断修改数组其实这样做也能做出来但代码量和出错率都会上升。递归写法的思路相反当前三个柱子分别放了多少盘并不重要重要的是在这一步里哪个是出发柱、哪个是辅助柱、哪个是目标柱。核心函数的参数顺序建议固定为move(n, from, aux, to)。在这个约定里每次递归调用遵循两条规则第一步把上面的n-1个盘从from搬到aux此时to是辅助第二步把from底部的盘直接搬到to第三步把aux上的n-1个盘搬到to此时from变成辅助。只要参数名按“from-aux-to”这个顺序写两处递归调用的实参就分别是(from, to, aux)和(aux, from, to)。// hanoi.cpp 核心实现 #include hanoi.h #include iostream #include thread #include chrono using namespace std; void Hanoi::move(int n, char from, char aux, char to) { if (n 1) { cout from - to endl; // 最小问题一个盘直接到位 stepCount; // 每移动一次计数器加一 if (delayMs 0) this_thread::sleep_for(chrono::milliseconds(delayMs)); return; } move(n - 1, from, to, aux); // 上半部分先让路 // 底部最大的盘从 from 直接去 to没有比它更大的盘不需要辅助柱 cout from - to endl; stepCount; if (delayMs 0) this_thread::sleep_for(chrono::milliseconds(delayMs)); move(n - 1, aux, from, to); // 下半部分跟上来 }逻辑说明每一次递归调用对应一次真实的单盘移动所以stepCount在打印移动行之后自增而不是在函数开头自增否则一个非底层的递归调用也会被错误计数。delayMs是演示速度参数设为0时程序以最快速度跑完设为200时每秒约移动5步适合在答辩现场演示。参数说明move(n-1, from, to, aux)这一行里原本的to变成了aux。写的时候可以默念一句口诀第一段递归里“目标柱”让位给辅助柱第三段递归里“出发柱”变成辅助柱。盘数n在每次递归里减1永远不会原地踏步所以递归深度有上界。3.3 完整可编译工程main入口、输入校验与运行示例核心递归只占函数的一小部分课程设计的大量工作在main入口。main要做的事情至少有四件显示菜单、读取盘数、校验非法输入、调用run()执行演示。下面给出main.cpp的完整实现把上一节的核心move与这一节的run()合并在同一个hanoi.cpp里就能直接编译。// main.cpp #include hanoi.h #include iostream using namespace std; int main() { Hanoi solver; solver.run(); return 0; }// hanoi.cpp 运行入口部分 #include hanoi.h #include iostream #include limits using namespace std; Hanoi::Hanoi() : diskCount(0), stepCount(0), delayMs(150) {} void Hanoi::run() { cout 汉诺塔演示程序 endl; cout 请输入盘子数量(1-15): ; cin diskCount; // 输入失败或越界时重新读取这是课程设计常被问到的一个细节 if (cin.fail() || diskCount 1 || diskCount 15) { cin.clear(); cin.ignore(numeric_limitsstreamsize::max(), \n); cout 输入无效使用默认盘数 3 endl; diskCount 3; } stepCount 0; cout 移动序列如下 endl; move(diskCount, A, B, C); // 按顺序传参不省略任何一项 cout 总步数: stepCount endl; cout 理论最少步数: ((1ULL diskCount) - 1) endl; }参数说明构造函数把delayMs初始化为150ms每移动一步停顿150毫秒窗口里能看到动态过程。输入范围定为1到15是因为15层理论步数是32767控制台滚动可以接受如果再大建议改成只显示统计信息不打印每一步。cin.fail()处理输入字母、负数和小数的情况cin.clear()和cin.ignore()用来清空错误状态和残留缓冲区避免下一次读入直接失败。编译与运行使用下面的命令推荐把编译告警打开g -stdc17 -Wall -Wextra main.cpp hanoi.cpp -o hanoi -pthread ./hanoi逻辑说明-Wall和-Wextra会提示未使用变量、符号比较等问题对查递归参数写反这种“编译器不报错但结果不对”的情况很有用。这里额外加了-pthread因为std::this_thread::sleep_for在Linux下要用线程库不加可能报链接错误。运行效果可以这样对照手动给两个盘做一次正确顺序是A-B、A-C、B-C程序输出也应该是同样的三行。如果你看到的顺序是A-C、A-B、C-B说明参数传递顺序写反了这就是后面要讲的验证方法的价值所在。提示如果在Windows的Visual Studio环境里编译不必加-pthread但如果交到Linux服务器上用g编译一定要保留这个选项否则会出现“undefined reference to pthread_create”之类的链接错误。4. 迭代模拟与64层极限类型、溢出和序列自检4.1 非递归实现为什么能用栈模拟却很少有人手写课程设计的加分方向常有一个选项不用递归用栈模拟实现汉诺塔。汉诺塔的递归本质就是不断往调用栈里压入子任务如果不想依赖系统调用栈可以自己维护一个显式栈把“待执行的移动任务”压进去。#include stack void hanoiIterative(int n, char from, char aux, char to) { struct Task { int n; char from, aux, to; bool expand; // true 表示还需要拆解false 表示直接执行 }; stackTask st; st.push({n, from, aux, to, true}); while (!st.empty()) { Task t st.top(); st.pop(); if (t.n 1) { cout t.from - t.to endl; continue; } if (t.expand) { // 逆序压栈先执行的任务后压入栈顶先被处理 st.push({t.n - 1, t.aux, t.from, t.to, true}); // 第三段任务 st.push({1, t.from, t.aux, t.to, false}); // 第二段任务 st.push({t.n - 1, t.from, t.to, t.aux, true}); // 第一段任务 } else { cout t.from - t.to endl; } } }逻辑说明结构体Task保存一个子任务expand字段区分是否还要继续分解。由于栈是后进先出三段压栈顺序必须和递归执行顺序相反递归先做第一段再做第二段最后做第三段所以压栈时先压第三段再压第二段最后压第一段这样栈顶最先取出的就是第一段。参数说明t.n 1时直接输出不再拆解t.n 1且有expand标志时把任务拆成三个更小的子任务其中第二段已经是一个单盘移动所以expand为false。这段代码的运行结果与递归版完全一样但它能让你在答辩时展开“递归为什么能改成循环”的讨论。一个常见误区是以为循环版一定更快。实际上汉诺塔的步数本身是2^n-1任何实现都躲不开这个指数下限区别只在于显式栈会不会因为内存分配而更慢。如果课程设计只要求功能不必追求非递归但能把这段讲清楚加分效果很明显。4.2 移动次数与大数溢出unsigned long long的极限在哪计数器类型是很多作业里被忽略的点。int在31层时就会溢出因为2^31-1已经超过int最大值unsigned long long也不能无限计数它的上限是2^64-1所以63层以内用unsigned long long安全64层理论步数恰好等于2^64-1刚好到上限再加一层就溢出。课程设计通常不会真去跑64层但答辩可能问你“程序能不能支持更大的n”。我一般会在输入处做上限保护而不是放任溢出。下面这段代码放在输入校验之后把层数限制在能统计的范围内if (diskCount 63) { cout 层数达到 diskCount 总步数已超出 64 位整数范围无法统计 endl; return; }参数说明unsigned long long能安全表示2^64-1以内的整数因此63层可以完整统计64层理论步数恰好是2^64-1虽没有超出但移位写法(1ULL 64)已经溢出属于语法层表现正常、数值层结果错误的坑。如果你的run()把输入上限放到20以上这段保护就很有必要如果维持第3章的1到15限制这段代码不会触发但作为边界说明出现在答辩材料里仍然有用。打印到控制台的IO开销常常被低估。n20时步数约为105万步cout输出一行至少耗时几十微秒加上sleep_for会把运行时间放大几十倍。所以演示场景建议小盘数用完整打印大盘数只输出统计信息或者把打印关了只保留总步数。这是课程设计里最基本的模式切换设计。4.3 验证输出序列正确性的自检小函数代码写得对不对不能光靠数步数还要验证每一步移动都不违规。可以在运行完递归后重建三根柱子的状态按输出顺序逐条执行移动检查“移动的盘子是否来自柱顶”以及“是否压到了更小的盘子”。#include vector #include string bool validateSequence(int n, const vectorstring moves) { vectorvectorint pegs(3); // 三根柱子盘子用编号表示编号越大越重 for (int i n; i 1; --i) pegs[0].push_back(i); // 初始所有盘子都在A柱顶部是编号最小 for (const string mv : moves) { char s mv[0], t mv[3]; // 解析 A - C 这类格式 int si s - A, ti t - A; if (pegs[si].empty()) return false; // 出发点没有盘子 int disk pegs[si].back(); pegs[si].pop_back(); if (!pegs[ti].empty() pegs[ti].back() disk) return false; // 大盘压小盘非法 pegs[ti].push_back(disk); } return pegs[0].empty() pegs[1].empty() pegs[2].size() (size_t)n; }逻辑说明验证函数接收n和移动序列模拟执行。它在递归输出之后运行如果返回false说明输出序列里存在非法移动比如从空柱子取盘或者大盘压小盘。参数说明pegs是vectorvector 编号越大的整数代表越重的盘初始把所有盘子按从大到小压进A柱back()代表柱顶因为vector末尾就是最近放进去的盘。这个函数复杂度是O(n * 2^n)只能用于小n自动测试不要对大n运行。有了步数校验和序列校验两层保障正确性论证就完整了步数对上证明没有漏步序列校验通过证明没有违规移动。这两个小工具在答辩时非常加分因为老师想看的不只是能跑而是知道自己为什么是对的。5. 汉诺塔程序避坑清单现象、原因与处理5.1 坑一移动结果方向反了总步数却依然正确现象程序输出总步数正确比如三盘7步但中间过程的柱子方向看着别扭。原因递归里两次调用的实参写错位置比如把第一步写成了move(n-1, aux, from, to)导致“从B搬到A”和“从A搬到B”互相颠倒而总步数不受影响所以只靠步数校验查不出来。解决在核心函数里固定“from-aux-to”的形参顺序测试盘数设为2此时正确序列只有3步能一眼看出方向再用上一节的validateSequence做校验会自动识别从空柱取盘等荒谬操作。5.2 坑二stepCount统计结果比理论步数多了一倍现象运行时屏幕刷了不少移动行最后总步数是理论值的两倍左右。原因常见写法是把stepCount放在了move函数的开头而不是实际移动盘的位置这样n1的每一层递归进入函数就算一次底层n1时又会算一次重复计数。解决将计数器自增只放在输出移动行之后与sleep_for放在一起保证“打印一行计数一次”。还有一个变体是误把同一行移动打印了两次比如在两次递归调用之间重复写cout这种要靠对比2盘3步的标准输出排查。5.3 坑三程序瞬间刷完几千行根本看不清过程现象输入15以后控制台像流水一样滚动移动键都来不及看甚至卡顿几秒钟。原因没有延时输出也没有分页暂停控制台光标滚动本身比cout输出慢得多IO成了瓶颈。解决在核心move中按delayMs做sleep更稳妥的做法是加入“按回车步进”模式用户输入一个回车执行一步。步进模式比定时sleep更适合答辩因为可以在关键步骤停下来讲。参数建议定时模式delayMs设为120到300毫秒步进模式则把sleep设为0。5.4 坑四Windows控制台中文乱码移动序列变成乱码现象代码里用了中文提示运行时出现乱码或者编译器直接报编码错误。原因Windows控制台默认代码页与源码文件编码不一致常见于UTF-8源码和GBK控制台混用。解决给main.cpp开头加一句system(chcp 65001 nul)能强制控制台切到UTF-8如果嫌这条命令在部分环境不生效更稳的做法是源码用GBK保存并去掉所有中文只保留ASCII输出。课程设计文档里的中文注释和运行窗口里的中文提示是两回事界面用英文也完全能说明问题不必为了中文界面引入编码麻烦。注意chcp命令改变的是当前终端会话的代码页不影响程序本身。如果你用VS直接跑IDE的终端可能已经处理好了编码用cmd窗口跑时这条命令才真正需要。5.5 坑五输入字母或超范围数后程序卡死或无限循环现象输入abc然后回车程序不再输出任何内容好像死机或者输入100后窗口疯狂滚动根本停不下来。原因cin读取失败后错误状态位未清除后续cin直接失败同时输入缓冲区里的换行和字母残留导致下一次读取又失败形成忙循环。解决在run()里用cin.clear()加cin.ignore()恢复流状态对于超范围输入直接设置默认值并提示用户而不是把非法值传进move函数。把输入范围上限设置为15或20从源头避免灾难性的2^64步输出。6. 图形化演示与答辩自检把运行结果变成分数6.1 控制台图形化用字符画画出三根柱子和盘子递归输出只是一行行文字答辩演示时不够直观。我一般会在课程设计里加一个drawStatus()函数每移动一步就重绘三根柱子的状态。绘制不必复杂用竖线表示柱子用数字表示盘子层数即可。void drawStatus(const vectorvectorint pegs) { for (int row 5; row 0; --row) { // 从顶部到底部逐行画 for (int col 0; col 3; col) { int disk (pegs[col].size() (size_t)row) ? pegs[col][row] : 0; if (disk 0) cout | ; else cout [ disk ]; } cout endl; } cout A B C endl; }逻辑说明pegs的index从0开始0是柱底画图时要从上往下把数组倒过来访问。每移动一步后调用这个函数屏幕上就能看到盘子从A柱依次挪到C柱。参数说明内层vector的索引就是柱上的层序row从5到0控制图的高度盘子超过6层时只画最上面的5层也够辨别。数字超过9时宽度会不对齐课程设计用单字符盘号或直接把盘号改成字母就能避开。这个函数配合延时输出就是最简单的动画。注意它要拿到三根柱子的当前状态所以建议把演示逻辑从“只打印移动”升级为“先更新柱子状态再打印状态”这样图形和文字可以同时保留。6.2 步进模式与文本日志让答辩有据可查只靠屏幕输出老师低头看了眼再抬头就可能错过关键步骤。建议再加一个日志模式把每一步移动写入hanoi_log.txt运行完后可以回去查。实现上只需要在Hanoi类里加一个ofstream成员在move里移动盘时同时写日志。// 在 Hanoi 类中增加成员ofstream logFile; logFile.open(hanoi_log.txt); // 核心move函数里移动盘时同时写日志 logFile from - to endl;文本日志的好处是被追问“第37步为什么是C-A”时可以直接翻日志而不是重跑一遍程序。日志文件里还可以顺手记录盘数、总耗时、总步数、系统环境作为实验报告附件。这个细节被很多作业忽略但很能让报告显得完整。6.3 答辩三连问被问倒前先想好怎么答程序写得不错、答辩却临时卡壳的例子我见过不少。汉诺塔的常见答辩问题基本就三个为什么递归不会无限递归改成循环应该怎么做层数很大时程序会怎样回答顺序一般这样准备递归不会无限因为每层调用传入的都是n-1当n减到1时直接返回不产生新调用所以递归深度有上界n循环版可以用显式栈模拟把任务结构体压栈压栈顺序与递归相反之前验证过输出一致层数很大时步数指数增长超过int范围所以要改用unsigned long long并限制打印只输出统计信息。把这三句话练熟比临时翻代码管用得多。我的习惯是答辩前把n设成4delayMs设成250完整演示一遍再关掉延时跑一轮确认总步数为15。这两个动作做完整个程序的功能和边界就都在脑子里了。汉诺塔这道题表面是考递归实际考的是工程意识和表达能力代码能跑只是起点能把每一步为什么这么写讲清楚才是拿高分的关键。希望这份笔记能帮到你。本文还有配套的精品资源点击获取
