C语言汉诺塔代码非递归

时间: 2023-11-12 16:04:01 浏览: 37
好的,以下是C语言汉诺塔问题的非递归代码: ```c #include <stdio.h> int main() { int n, i, x, y, z, count = 0; int stack[100], top = -1; printf("请输入盘数:"); scanf("%d", &n); // 把第一次需要移动的数据压入栈中 stack[++top] = n; stack[++top] = 1; stack[++top] = 3; while (top > -1) { z = stack[top--]; x = stack[top--]; y = stack[top--]; if (x == y) { printf("第 %d 步: 把盘子 %d 从 %d 号柱移动到 %d 号柱\n", ++count, z, x, y); } else { // 把盘子压入栈中 stack[++top] = z; stack[++top] = x; stack[++top] = y; // 计算出第三个柱子的编号 int temp = 6 - x - y; // 把需要移动的数据压入栈中 stack[++top] = z - 1; stack[++top] = temp; stack[++top] = y; // 把需要移动的数据压入栈中 stack[++top] = 1; stack[++top] = x; stack[++top] = y; // 把需要移动的数据压入栈中 stack[++top] = z - 1; stack[++top] = x; stack[++top] = temp; } } return 0; } ``` 希望能够帮到您!

相关推荐

以下是汉诺塔的非递归C语言代码: #include <stdio.h> #include <stdlib.h> // 定义堆栈结构 struct Stack { int capacity; int top; int *array; }; // 创建堆栈 struct Stack *createStack(int capacity) { struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack)); stack->capacity = capacity; stack->top = -1; stack->array = (int *)malloc(stack->capacity * sizeof(int)); return stack; } // 判断堆栈是否为空 int isEmpty(struct Stack *stack) { return stack->top == -1; } // 判断堆栈是否已满 int isFull(struct Stack *stack) { return stack->top == stack->capacity - 1; } // 入栈 void push(struct Stack *stack, int item) { if (isFull(stack)) { return; } stack->array[++stack->top] = item; } // 出栈 int pop(struct Stack *stack) { if (isEmpty(stack)) { return -1; } return stack->array[stack->top--]; } // 非递归汉诺塔函数 void hanoi(int n) { struct Stack *source = createStack(n); struct Stack *auxiliary = createStack(n); struct Stack *destination = createStack(n); int i; for (i = n; i > 0; i--) { push(source, i); } int totalMoves = (1 << n) - 1; int from, to; if (n % 2 == 0) { from = 2; to = 3; } else { from = 1; to = 2; } for (i = 1; i <= totalMoves; i++) { if (i % 3 == 1) { if (isEmpty(destination)) { push(destination, pop(source)); } else if (isEmpty(source)) { push(source, pop(destination)); } else if (source->array[source->top] > destination->array[destination->top]) { push(destination, pop(source)); } else { push(source, pop(destination)); } } else if (i % 3 == 2) { if (isEmpty(auxiliary)) { push(auxiliary, pop(source)); } else if (isEmpty(source)) { push(source, pop(auxiliary)); } else if (source->array[source->top] > auxiliary->array[auxiliary->top]) { push(auxiliary, pop(source)); } else { push(source, pop(auxiliary)); } } else if (i % 3 == 0) { if (isEmpty(destination)) { push(destination, pop(auxiliary)); } else if (isEmpty(auxiliary)) { push(auxiliary, pop(destination)); } else if (auxiliary->array[auxiliary->top] > destination->array[destination->top]) { push(destination, pop(auxiliary)); } else { push(auxiliary, pop(destination)); } } printf("Move disk %d from rod %d to rod %d\n", i, from, to); if (from == 1 && to == 2) { from = 1; to = 3; } else if (from == 1 && to == 3) { from = 2; to = 3; } else { from = 1; to = 2; } } } // 主函数 int main() { int n = 3; hanoi(n); return 0; }
汉诺塔问题的非递归实现可以利用栈来实现。具体步骤如下: 1. 将初始状态下的所有盘子按从大到小的顺序压入起始栈。 2. 根据汉诺塔的规则,将起始栈中的最上面的盘子移动到目标栈中。如果某一时刻起始栈为空,则说明所有盘子都已经被移动到目标栈中,此时程序结束。 3. 将目标栈中的最上面的盘子移动到辅助栈中。 4. 重复步骤2和3,直到所有盘子都被移动到目标栈中为止。 下面是一个使用C++实现的汉诺塔非递归代码示例: c++ #include <iostream> #include <stack> using namespace std; void hanoi(int n, stack<int>& from, stack<int>& to, stack<int>& aux) { int moves = pow(2, n) - 1; //总共需要移动的次数 for (int i = n; i >= 1; i--) { from.push(i); //初始状态下所有盘子都在起始栈中 } for (int i = 1; i <= moves; i++) { if (i % 3 == 1) { if (!aux.empty() && (from.empty() || aux.top() < from.top())) { //将辅助栈中的盘子移动到起始栈中 from.push(aux.top()); aux.pop(); cout << "Move disk " << from.top() << " from Aux to From" << endl; } else { //将起始栈中的盘子移动到目标栈中 to.push(from.top()); from.pop(); cout << "Move disk " << to.top() << " from From to To" << endl; } } else if (i % 3 == 2) { if (!to.empty() && (from.empty() || to.top() < from.top())) { //将目标栈中的盘子移动到起始栈中 from.push(to.top()); to.pop(); cout << "Move disk " << from.top() << " from To to From" << endl; } else { //将起始栈中的盘子移动到辅助栈中 aux.push(from.top()); from.pop(); cout << "Move disk " << aux.top() << " from From to Aux" << endl; } } else { if (!to.empty() && (aux.empty() || to.top() < aux.top())) { //将目标栈中的盘子移动到辅助栈中 aux.push(to.top()); to.pop(); cout << "Move disk " << aux.top() << " from To to Aux" << endl; } else { //将辅助栈中的盘子移动到目标栈中 to.push(aux.top()); aux.pop(); cout << "Move disk " << to.top() << " from Aux to To" << endl; } } } } int main() { stack<int> from, to, aux; int n = 3; //汉诺塔的层数 hanoi(n, from, to, aux); return 0; }
### 回答1: 好的,我会用中文来解释如何用递归来写汉诺塔的程序。 首先,如果只有一个盘子,我们可以直接将它从一根柱子移动到另一根柱子。如果有多个盘子,我们可以用递归的方法来解决。我们先将上面的所有盘子(除了最大的盘子)从源柱子移动到辅助柱子,然后将最大的盘子移动到目标柱子,最后将所有盘子从辅助柱子移动到目标柱子。 下面是一个简单的递归函数,它可以帮助你理解这个过程: void hanoi(int n, char src, char aux, char dest) { if (n == 1) { // 如果只有一个盘子,直接移动 printf("Move disk 1 from %c to %c\n", src, dest); return; } // 将上面的所有盘子(除了最大的盘子)从源柱子移动到辅助柱子 hanoi(n - 1, src, dest, aux); // 将最大的盘子从源柱子移动到目标柱子 printf("Move disk %d from %c to %c\n", n, src, dest); // 将所有盘子从辅助柱子移动到目标柱子 hanoi(n - 1, aux, src, dest); } 希望这对你有帮助。 ### 回答2: 汉诺塔问题是经典的递归问题,递归函数用于解决问题时,首先要找到递归的出口条件,然后再考虑递归的过程。 在汉诺塔问题中,我们需要将盘子从一个柱子移动到另一个柱子上,且每次只能移动一个盘子,且不能将较大的盘子放在较小的盘子上面。 下面是用C语言编写汉诺塔的递归函数的示例: #include <stdio.h> void hanoi(int n, char A, char B, char C) { // 递归出口条件 if (n == 1) { printf("将盘子1从%c移动到%c\n", A, C); return; } // 将n-1个盘子从A柱移动到B柱 hanoi(n - 1, A, C, B); // 将最大的盘子从A柱移动到C柱 printf("将盘子%d从%c移动到%c\n", n, A, C); // 将n-1个盘子从B柱移动到C柱 hanoi(n - 1, B, A, C); } int main() { int n; // 盘子的数量 printf("请输入盘子的数量:"); scanf("%d", &n); printf("移动的步骤如下:\n"); hanoi(n, 'A', 'B', 'C'); return 0; } 以上使用了一个hanoi函数来实现递归操作,其中n表示盘子的数量,A、B、C表示三个柱子。 在hanoi函数中,首先判断递归的出口条件,当只有一个盘子时,直接将该盘子从A柱移动到C柱; 然后递归调用hanoi函数,将n-1个盘子从A柱通过C柱移动到B柱; 最后将最大的盘子从A柱直接移动到C柱; 再次递归调用hanoi函数,将n-1个盘子从B柱通过A柱移动到C柱。 通过这样不断递归调用hanoi函数,直到盘子全部移动完成。 ### 回答3: C语言中的汉诺塔问题是一个典型的递归问题。汉诺塔问题的目标是将一堆盘子从起始柱子移动到目标柱子,其中有三根柱子可供使用。规则是一次只能移动一个盘子,并且较大的盘子不能放在较小的盘子之上。 下面是一个使用C语言编写的汉诺塔递归解决方案: c #include <stdio.h> void hanoi(int n, char start, char middle, char end) { // 递归的出口,当只有一个盘子时直接移动即可 if (n == 1) { printf("Move disk 1 from %c to %c\n", start, end); return; } // 将 n-1 个盘子从起始柱子移动到中间柱子 hanoi(n - 1, start, end, middle); // 将最底下的一个盘子从起始柱子移动到目标柱子 printf("Move disk %d from %c to %c\n", n, start, end); // 将 n-1 个盘子从中间柱子移动到目标柱子 hanoi(n - 1, middle, start, end); } int main() { int numDisks = 3; // 盘子的数量 char start = 'A'; // 起始柱子 char middle = 'B'; // 中间柱子 char end = 'C'; // 目标柱子 hanoi(numDisks, start, middle, end); return 0; } 这个程序首先定义了一个函数hanoi用于解决汉诺塔问题。函数的参数包括:盘子的数量n,起始柱子start,中间柱子middle,目标柱子end。在日志输出中,打印出每次移动的盘子编号和起始柱子到目标柱子的移动。 然后在main函数中,定义了盘子的数量numDisks以及起始、中间和目标柱子的名称。通过调用hanoi函数来解决汉诺塔问题。 运行该程序,它将会按照递归规则打印出相应的移动步骤,最终完成汉诺塔问题的求解。
汉诺塔是一个经典的递归问题,但也可以使用非递归算法来解决。下面是一个使用C语言实现的非递归算法: c #include <stdio.h> #include <stdlib.h> typedef struct { int n; char source, temp, dest; } State; typedef struct { State *array; int size; int top; } Stack; Stack *createStack(int size) { Stack *stack = (Stack *) malloc(sizeof(Stack)); stack->array = (State *) malloc(sizeof(State) * size); stack->size = size; stack->top = -1; return stack; } void push(Stack *stack, State state) { stack->array[++stack->top] = state; } State pop(Stack *stack) { return stack->array[stack->top--]; } void hanoi(int n, char source, char temp, char dest) { Stack *stack = createStack(n); push(stack, (State) {n, source, temp, dest}); while (stack->top >= 0) { State currentState = pop(stack); if (currentState.n == 1) { printf("Move disk from %c to %c\n", currentState.source, currentState.dest); } else { push(stack, (State) {currentState.n - 1, currentState.temp, currentState.source, currentState.dest}); push(stack, (State) {1, currentState.source, currentState.temp, currentState.dest}); push(stack, (State) {currentState.n - 1, currentState.source, currentState.dest, currentState.temp}); } } free(stack->array); free(stack); } int main() { int n; printf("Enter the number of disks: "); scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); return 0; } 这个算法使用了一个栈来模拟递归的过程。首先将初始状态压入栈中,然后在每一次循环中取出栈顶状态进行处理。当只有一个盘子时,直接移动即可,否则将分解成三个子问题,分别将n-1个盘子从源柱移动到辅助柱,将最后一个盘子从源柱移动到目标柱,最后将n-1个盘子从辅助柱移动到目标柱。循环直到栈为空,即所有盘子都移动到了目标柱。 示例代码中的hanoi函数接受三个参数:n表示盘子的个数,source表示源柱,temp表示辅助柱,dest表示目标柱。在每一次移动盘子时,会打印出移动的步骤。 你可以在程序中输入想要的盘子数量,然后运行该程序来查看非递归算法的结果。

最新推荐

汉诺塔递归算法--C语言

汉诺塔递归算法: 问题抽象  3个塔,n个碟子  初始:所有碟子放在1号塔,大的在底下,小的在上面  任务:把碟子移动到2号塔,顺序不变, 可用3号塔辅助  限制  每次只能移动一个碟子  总是大碟子...

火焰处理输送线sw18_零件图_机械工程图_机械三维3D设计图打包下载.zip

火焰处理输送线sw18_零件图_机械工程图_机械三维3D设计图打包下载.zip

面向6G的编码调制和波形技术.docx

面向6G的编码调制和波形技术.docx

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

Power BI中的数据导入技巧

# 1. Power BI简介 ## 1.1 Power BI概述 Power BI是由微软公司推出的一款业界领先的商业智能工具,通过强大的数据分析和可视化功能,帮助用户快速理解数据,并从中获取商业见解。它包括 Power BI Desktop、Power BI Service 以及 Power BI Mobile 等应用程序。 ## 1.2 Power BI的优势 - 基于云端的数据存储和分享 - 丰富的数据连接选项和转换功能 - 强大的数据可视化能力 - 内置的人工智能分析功能 - 完善的安全性和合规性 ## 1.3 Power BI在数据处理中的应用 Power BI在数据处

建立关于x1,x2 和x1x2 的 Logistic 回归方程.

假设我们有一个包含两个特征(x1和x2)和一个二元目标变量(y)的数据集。我们可以使用逻辑回归模型来建立x1、x2和x1x2对y的影响关系。 逻辑回归模型的一般形式是: p(y=1|x1,x2) = σ(β0 + β1x1 + β2x2 + β3x1x2) 其中,σ是sigmoid函数,β0、β1、β2和β3是需要估计的系数。 这个方程表达的是当x1、x2和x1x2的值给定时,y等于1的概率。我们可以通过最大化似然函数来估计模型参数,或者使用梯度下降等优化算法来最小化成本函数来实现此目的。

智能网联汽车技术期末考试卷B.docx

。。。

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依

数据可视化:Pandas与Matplotlib的结合应用

# 1. 数据可视化的重要性 1.1 数据可视化在数据分析中的作用 1.2 Pandas与Matplotlib的概述 **1.1 数据可视化在数据分析中的作用** 数据可视化在数据分析中扮演着至关重要的角色,通过图表、图形和地图等形式,将抽象的数据转化为直观、易于理解的可视化图像,有助于人们更直观地认识数据,发现数据之间的关联和规律。在数据分析过程中,数据可视化不仅可以帮助我们发现问题和趋势,更重要的是能够向他人有效传达数据分析的结果,帮助决策者做出更明智的决策。 **1.2 Pandas与Matplotlib的概述** Pandas是Python中一个提供数据

1. IP数据分组的片偏移计算,MF标识符怎么设置。

IP数据分组是将较长的IP数据报拆分成多个较小的IP数据报进行传输的过程。在拆分的过程中,每个数据分组都会设置片偏移和MF标识符来指示该分组在原始报文中的位置和是否为最后一个分组。 片偏移的计算方式为:将IP数据报的总长度除以8,再乘以当前分组的编号,即可得到该分组在原始报文中的字节偏移量。例如,若原始报文总长度为1200字节,每个数据分组的最大长度为500字节,那么第一个分组的片偏移为0,第二个分组的片偏移为500/8=62.5,向下取整为62,即第二个分组的片偏移为62*8=496字节。 MF标识符是指“更多的分组”标识符,用于标识是否还有后续分组。若该标识位为1,则表示还有后续分组;