今天小编给大家分享一下c语言怎么循环加数组实现汉诺塔的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。
简介
汉诺塔问题是学数据结构与算法的时候会遇到的问题，相信来看本文的读者应该都对汉诺塔问题有基本的了解，理论上所有的递归都可以改成循环，常规的做法是借助堆栈，但是我一想好像用循环加数组也可以实现，于是就有了本文，实现声明，本文最后出来的算法效率不高的，比直接用递归实现还要差很多，追求算法效率的同学就不用看这个了。
题目：假设有3个柱子，分别为A、B、C，A柱子上有数量为n个的空心圆盘，从上到下序号分别为1...n，要求把A柱子中的n个圆盘移动到C柱中，且序号大的盘子必须在在需要小的圆盘下方。
思路：如果只有1个圆盘需要移动，则直接从A柱移动到C柱，如果有n个圆盘（n>1）需要移动，则需要先把n-1个圆盘从A柱移动到B柱，再把第n个圆盘从A柱移动到C柱，最后把原来的n-1个圆盘从B柱移动到C柱。
例如：
将1个圆盘从A柱移动到C柱只需要1个步骤：
把圆盘1从A移动到C
将2个圆盘从A柱移动到C柱需要3个步骤：
把圆盘1从A移动到B
2. 把圆盘2从A移动到C
3. 把圆盘1从B移动到C
将3个圆盘从A柱移动到C柱需要7个步骤：
把圆盘1从A移动到C
2. 把圆盘2从A移动到B
3. 把圆盘1从C移动到B
4. 把圆盘3从A移动到C
5. 把圆盘1从B移动到A
6. 把圆盘2从B移动到C
7. 把圆盘1从A移动到C
递归的汉诺塔解法（c语言）
可以看出下面的递归算法的时间复杂度为O(2^n)，因为存在有调用2^n-2次递归调用和1次原生printf；而空间复杂度为O(n)，因为运行时栈中最多会同时保存n个函数的调用信息。
#include <stdio.h>#include <stdlib.h>#include <math.h>void towers(int n, char from, char to, char aux);int main() { towers(3, 'A', 'C', 'B'); return 0;}void showMove (int order, char from, char to) { printf("move disk %d from %c to %c\n", order, from, to);}void towers(int n, char from, char to, char aux) { if (n==1) { showMove(n, from, to); return; } towers(n-1, from, aux, to); showMove(n, from, to); towers(n-1, aux, to, from);}解释一下代码中参数的含义，void towers(int n, char from, char to, char aux)的意思是把n个圆盘从from柱子移动到to柱子，中间可以借用aux柱子。
分析一下上面的递归执行过程：
我们已经知道把1个圆盘从from移动到to的步骤是showMove(1, from, to);
而把2个圆盘从from移动到to的步骤是，先照着移动1个圆盘的操作，把前面1个圆盘从from移动到aux，再把第2个圆盘从from移动到to，最后按照移动1个圆盘的操作，把刚才的1个圆盘从aux移动到to。
同理，把3个圆盘从from移动到to的步骤是，先照着移动2个圆盘的操作，把前面2个圆盘从from移动到aux，再把第3个圆盘从from移动到to，最后按照移动2个圆盘的操作，把刚才的2个圆盘从aux移动到to。
所以，把n个圆盘的操作从from移动到to的步骤是，先照着移动n-1个圆盘的操作，把前面n-1个圆盘从from移动到aux，再把第n个圆盘从from移动到to，最后按照移动n-1个圆盘的操作，把刚才的n-1个圆盘从aux移动到to。
因此，我们可以记录移动1个圆盘的步骤，来得到移动2个圆盘的步骤，通过移动2个圆盘的步骤来得到移动3个圆盘的步骤,...最后得到移动n个圆盘的步骤。经过分析可以知道移动n个圆盘一共会有2^n-1个步骤
循环实现汉诺塔问题（c语言）
为了代码更加易懂，这里写了注释，修改了部分变量命名，统一用数组保存步骤集合，最后才输出。
可以看出这个算法的时间复杂度还是O(2^n)，一共会执行2^(n+1)-1次setMoveAction语句和2^n-1次，printf语句，比起直接用递归还要复杂一些，而空间复杂度也是O(2^n)，属于没什么用的算法，就是随便写写。
#include <stdio.h>#include <stdlib.h>#include <math.h>void towers(int n, char from, char to, char aux);int main(){ towers(3, 'A', 'C', 'B'); return 0;}void showMove(int order, char from, char to){ printf("move disk %d from %c to %c\n", order, from, to);}typedef struct{ int order; char from; char to;} MoveAction;void setMoveAction(MoveAction *p, int order, char from, char to){ p->order = order; p->from = from; p->to = to;}char compare_map(char c, char left, char right) { if (c == left) { return right; } else if (c == right) { return left; } return c;}void towers(int n, char from, char to, char aux){ MoveAction *actions, action; int i, k, size; char f, t; actions = (MoveAction *)calloc(pow(2, n - 1) - 1, sizeof(MoveAction)); setMoveAction(&actions[0], 1, from, to); size = 1; for (i = 2; i <= n; i++) { //本次循环会将把i个盘子从from移动到to的步骤记录到actions数组中 // 设size是把i-1个盘子从from移动到to的步骤数， // 则本次循环中集合{actions[x] | 0 <= x <= size -1 }就是size是把i-1个盘子从from移动到aux的步骤集合， //而action[size]是把第i个盘子从from移到to， //而集合{actions[x] | size + 1 <= x <= 2*size }就应该是把i-1个盘存从aux移动到to的步骤集合 // 倒序，先求解集合{actions[x] | size + 1 <= x <= 2*size } for (k = 0; k < size; k++) { action = actions[k]; f = compare_map(action.from, from, aux); t = compare_map(action.to, from, aux); setMoveAction(&actions[k + size + 1], action.order, f, t); } // 求解action[size] setMoveAction(&actions[size], i, from, to); // 求解集合{actions[x] | 0 <= x <= size -1 } for (k = 0; k < size; k++) { action = actions[k]; f = compare_map(action.from, to, aux); t = compare_map(action.to, to, aux); setMoveAction(&actions[k], action.order, f, t); } size = size * 2 + 1; } for (i = 0; i < size; i++) { showMove(actions[i].order, actions[i].from, actions[i].to); }}以上就是“c语言怎么循环加数组实现汉诺塔”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注编程网行业资讯频道。
