汉诺塔非递归算法c语言

时间: 2023-09-12 16:00:22 浏览: 42
汉诺塔是一个经典的递归问题,但也可以使用非递归算法来解决。下面是一个使用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语言代码: #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; }
汉诺塔问题是经典的递归问题,它的求解过程可以用递归算法来实现。以下是汉诺塔问题的C语言递归算法分析。 1. 问题描述 汉诺塔问题是指有三根柱子A、B、C,在A柱子上从下往上按照大小顺序放置n个盘子,要求把这n个盘子移动到C柱子上,移动过程中可以借助B柱子,但是要满足以下条件: 1. 每次只能移动一个盘子; 2. 盘子不能放在比它小的盘子上面。 2. 递归实现 汉诺塔问题可以通过递归实现,具体实现过程如下: 1. 将n-1个盘子从A柱子移动到B柱子上,借助C柱子; 2. 将A柱子上最大的盘子移动到C柱子上; 3. 将n-1个盘子从B柱子移动到C柱子上,借助A柱子。 递归终止条件是只有一个盘子时直接将其从A柱子移动到C柱子上。 3. 代码实现 下面是汉诺塔问题的C语言递归算法实现代码: c #include <stdio.h> void hanoi(int n, char from, char to, char via) { if (n == 1) { printf("Move disk %d from %c to %c\n", n, from, to); } else { hanoi(n-1, from, via, to); printf("Move disk %d from %c to %c\n", n, from, to); hanoi(n-1, via, to, from); } } int main() { int n = 3; // 三个盘子 hanoi(n, 'A', 'C', 'B'); return 0; } 代码中,hanoi函数用于求解汉诺塔问题,n表示盘子的个数,from表示起始柱子,to表示目标柱子,via表示中介柱子。在函数中,如果n等于1,则直接将盘子从起始柱子移动到目标柱子上;否则,递归地将n-1个盘子从起始柱子移动到中介柱子上,然后将最大的盘子从起始柱子移动到目标柱子上,最后递归地将n-1个盘子从中介柱子移动到目标柱子上。 在main函数中,首先定义了盘子的个数n,然后调用hanoi函数求解汉诺塔问题。 4. 总结 汉诺塔问题是经典的递归问题,通过递归算法可以简便地实现其求解过程。在实现时,需要注意递归的终止条件和递归调用的顺序。

最新推荐

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

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

企业人力资源管理系统的设计与实现-计算机毕业论文.doc

企业人力资源管理系统的设计与实现-计算机毕业论文.doc

"风险选择行为的信念对支付意愿的影响:个体异质性与管理"

数据科学与管理1(2021)1研究文章个体信念的异质性及其对支付意愿评估的影响Zheng Lia,*,David A.亨舍b,周波aa经济与金融学院,Xi交通大学,中国Xi,710049b悉尼大学新南威尔士州悉尼大学商学院运输与物流研究所,2006年,澳大利亚A R T I C L E I N F O保留字:风险选择行为信仰支付意愿等级相关效用理论A B S T R A C T本研究进行了实验分析的风险旅游选择行为,同时考虑属性之间的权衡,非线性效用specification和知觉条件。重点是实证测量个体之间的异质性信念,和一个关键的发现是,抽样决策者与不同程度的悲观主义。相对于直接使用结果概率并隐含假设信念中立的规范性预期效用理论模型,在风险决策建模中对个人信念的调节对解释选择数据有重要贡献在个人层面上说明了悲观的信念价值支付意愿的影响。1. 介绍选择的情况可能是确定性的或概率性�

动态规划与最大子数组和问题:如何高效解决序列中的最大子数组和

## 1. 引言 ### 1.1 背景介绍 动态规划是一种解决复杂问题的算法设计方法,它通过将问题分解成子问题,并解决每个子问题,从而逐步构建最优解。在计算机科学和算法领域,动态规划被广泛应用于优化问题的求解。 ### 1.2 动态规划在算法中的重要性 动态规划不仅仅是一种算法,更是一种解决问题的思维方式。它通过保存子问题的解,避免了重复计算,从而在时间和空间上实现了效率的提升。这种思想在很多经典算法问题中都发挥着关键作用,其中之一便是最大子数组和问题。 ### 1.3 最大子数组和问题的实际应用场景 最大子数组和问题是在一个数组中找到一个具有最大和的连续子数组的问题。这个问题在实际中有

devc++6.3大小写字母转换

根据提供的引用内容,无法直接回答关于 Dev-C++ 6.3 的大小写字母转换问题。Dev-C++ 是一个集成开发环境(IDE),用于编写和运行 C/C++ 程序。如果您想要实现大小写字母转换,可以使用 C++ 标准库中的 toupper() 和 tolower() 函数。这两个函数分别将字符转换为大写和小写形式。以下是一个简单的示例程序: ```c++ #include <iostream> #include <string> using namespace std; int main() { string str = "Hello, World!"; for (int

基于ADuC812单片机的温湿度检测仪-毕业设计.doc

基于ADuC812单片机的温湿度检测仪-毕业设计.doc

"Python编程新手嵌套循环练习研究"

埃及信息学杂志24(2023)191编程入门练习用嵌套循环综合练习Chinedu Wilfred Okonkwo,Abejide Ade-Ibijola南非约翰内斯堡大学约翰内斯堡商学院数据、人工智能和数字化转型创新研究小组阿提奇莱因福奥文章历史记录:2022年5月13日收到2023年2月27日修订2023年3月1日接受保留字:新手程序员嵌套循环练习练习问题入门编程上下文无关语法过程内容生成A B S T R A C T新手程序员很难理解特定的编程结构,如数组、递归和循环。解决这一挑战的一种方法是为学生提供这些主题中被认为难以理解的练习问题-例如嵌套循环。实践证明,实践有助于程序理解,因此,由于手动创建许多实践问题是耗时的;合成这些问题是一个值得研究的专家人工智能任务在本文中,我们提出了在Python中使用上下文无关语法进行嵌套循环练习的综合。我们定义了建模程序模板的语法规则基于上�

区间动态规划实践:如何在字符串和数组中处理复杂的区间问题

# 区间动态规划实践:如何在字符串和数组中处理复杂的区间问题? ## 1. 引言 ### 1.1 什么是区间动态规划? 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中常见的问题求解方法。而区间动态规划则是在这一思想基础上针对区间问题的一种具体实践。区间动态规划通常涉及字符串和数组等数据结构,在解决各种复杂问题时展现出强大的优势。 ### 1.2 区间动态规划在字符串和数组中的应用价值 区间动态规划的应用不仅仅局限于理论层面,它在实际问题中能够有效解决各种涉及区间操作的场景。通过深入理解区间动态规划的原理和实践经验,我们能够更好地处理字符串和数组中的复

4 1 C:\Users\魏榕本榕\Desktop\未命名2.c [Error] unknown type name 'LinkList'

根据提供的引用内容,我们无法确定您的问题的具体背景和上下文。但是,根据引用和引用的内容,我们可以推测您可能遇到了以下问题: 您的C语言程序中使用了未定义的类型名LinkList,导致编译错误。请检查您的程序中是否正确定义了LinkList类型,并且是否正确包含了相关头文件。 您的Java程序中使用了LinkedList类,但在迭代LinkedList时修改了它,导致了ConcurrentModificationException异常。请确保在迭代LinkedList时不要修改它,或者使用Iterator的remove()方法来删除元素。 您的Android NDK项目无法找到应用程序项目

基于java的网络聊天室服务器端.doc

基于java的网络聊天室服务器端.doc