用C语言写一个程序:分别用递归和迭代来解决河内塔问题
时间: 2024-05-12 16:16:38 浏览: 17
以下是用C语言解决河内塔问题的代码,分别使用递归和迭代。
递归实现:
```
#include<stdio.h>
void hanoi(int n, char a, char b, char c) {
if (n == 1) {
printf("%c->%c\n", a, c);
} else {
hanoi(n-1, a, c, b);
printf("%c->%c\n", a, c);
hanoi(n-1, b, a, c);
}
}
int main() {
int n;
printf("请输入盘子数量:");
scanf("%d", &n);
printf("移动路径:\n");
hanoi(n, 'A', 'B', 'C');
return 0;
}
```
迭代实现:
```
#include<stdio.h>
int main() {
int n, i = 0, cnt = 0;
char a = 'A', b = 'B', c = 'C';
int stack[100], top = -1; //栈
printf("请输入盘子数量:");
scanf("%d", &n);
printf("移动路径:\n");
while (1) {
while (n > 1) {
top++; //进栈
stack[top] = n;
top++;
stack[top] = a-'A'+1;
top++;
stack[top] = b-'A'+1;
top++;
stack[top] = c-'A'+1;
n--;
char tmp = b;
b = c;
c = tmp;
}
printf("%c->%c\n", a, c);
cnt++;
if (top == -1) {
break; //栈空,结束
}
c = stack[top--] + 'A' - 1;
b = stack[top--] + 'A' - 1;
a = stack[top--] + 'A' - 1;
n = stack[top--]; //出栈
char tmp = a;
a = b;
b = tmp;
}
printf("移动次数:%d\n", cnt);
return 0;
}
```
以上代码可以在Dev-C++中运行。递归实现简单易懂,时间复杂度为O(2^n-1);迭代实现利用栈将递归变成迭代,时间复杂度同样为O(2^n-1)。