文章目錄

• • c語言簡化版
  • C語言強化版（能看到每一步每個塔的情況）（使用了順序棧庫）
  • • main.c
    • sequential_stack.cpp
    • sequential_stack.h
    • 運行結果

找了個漢諾塔游戲玩，一開始玩給我整懵逼了，后來玩著玩著才慢慢找到訣竅，但到了高階（> = 7）的時候，老是記不住步驟，果然普通人的腦袋對于遞歸這種層層遞進式線索較長的運算結構，還是不具備優勢啊！就好比由一個問題衍生出另一個問題，只有解決了后面的問題才能解決前面的問題，但當問題一個接著一個衍生到七八個問題的時候，最初的問題是啥都給忘得一干二凈了！

但是計算機不會，它會把一個一個問題存放在函數調用棧中，就算是后面衍生出幾百上千個問題，它也不可能忘記！

下面用我們用代碼來實現它，有python和c語言兩個版本：

c語言簡化版

輸入的是當前I塔的層數n，

#include <stdio.h>void hanoi(int n, char I, char J, char K) {//printf("n = %d\n", n);if (n == 1) {printf("%c -> %c\n", I, K);}else {hanoi(n-1, I, K, J);printf("%c -> %c\n", I, K);hanoi(n-1, J,I,K);} }int main() {hanoi(3, 'A', 'B', 'C');return 0; }

運行結果：

A -> C A -> B C -> B A -> C B -> A B -> C A -> C

C語言強化版（能看到每一步每個塔的情況）（使用了順序棧庫）

main.c

#include <stdio.h> #include "sequential_stack.h"struct SqStack A = { 'A' }; struct SqStack B = { 'B' }; struct SqStack C = { 'C' };void print_hanoi_tower() {StackTraverse_R(A);StackTraverse_R(B);StackTraverse_R(C);printf("\n"); }void hanoi(int n, struct SqStack* I , struct SqStack* J, struct SqStack* K) {if (n == 1) {printf("%c -> %c\n", I->name, K->name);int e;Pop(I, &e);Push(K, e);print_hanoi_tower();printf("\n");}else {hanoi(n-1, I, K, J);printf("%c -> %c\n", I->name, K->name);int e;Pop(I, &e);Push(K, e);print_hanoi_tower();printf("\n");hanoi(n-1, J, I, K);} }int main() {InitStack(&A);InitStack(&B);InitStack(&C);//漢諾塔階數int tower_floor = 4;for (int i = tower_floor; i > 0; i--)Push(&A, i);printf("%d階漢諾塔：\n", tower_floor);print_hanoi_tower();printf("\n");int len = StackLength(A);hanoi(len, &A, &B, &C);return 0; }

sequential_stack.cpp

//順序棧：泛型版，里面存指針 #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #include "sequential_stack.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲空間初始分配量 */int visit(int c) {printf("%d ", c);return OK; }/* 構造一個空棧S */ int InitStack(struct SqStack* S) {/* S.data=(int *)malloc(MAXSIZE*sizeof(int)); */S->top = -1;return OK; }/* 把S置為空棧 */ int ClearStack(struct SqStack* S) {S->top = -1;return OK; }/* 若棧S為空棧，則返回TRUE，否則返回FALSE */ int StackEmpty(struct SqStack S) {if (S.top == -1)return TRUE;elsereturn FALSE; }/* 返回S的元素個數，即棧的長度 */ int StackLength(struct SqStack S) {return S.top + 1; }/* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ int GetTop(struct SqStack S, int* e) {if (S.top == -1)return ERROR;else*e = S.data[S.top];return OK; }/* 插入元素e為新的棧頂元素 */ int Push(struct SqStack* S, int e) {if (S->top == MAXSIZE - 1) /* 棧滿 */{return ERROR;}S->top++; /* 棧頂指針增加一 */S->data[S->top] = e; /* 將新插入元素賦值給棧頂空間 */return OK; }/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ int Pop(struct SqStack* S, int* e) {if (S->top == -1)return ERROR;*e = S->data[S->top]; /* 將要刪除的棧頂元素賦值給e */S->top--; /* 棧頂指針減一 */return OK; }/* 從棧底到棧頂依次對棧中每個元素顯示 */ int StackTraverse(struct SqStack S) {int i;i = 0;while (i <= S.top){visit(S.data[i++]);}//printf("\n");return OK; }/* 從棧頂到棧底依次對棧中每個元素顯示 */ int StackTraverse_R(struct SqStack S) {printf("%c:", S.name);int i;i = S.top;while (i > -1){visit(S.data[i--]);}printf("\t");return OK; }

sequential_stack.h

#pragma once #define MAXSIZE 20/* 順序棧結構 */ struct SqStack {char name;int data[MAXSIZE];int top; /* 用于棧頂指針 */ };extern int visit(int c); extern int InitStack(struct SqStack* S); extern int ClearStack(struct SqStack* S); extern int StackEmpty(struct SqStack S); extern int StackLength(struct SqStack S); extern int GetTop(struct SqStack S, int* e); extern int Push(struct SqStack* S, int e); extern int Pop(struct SqStack* S, int* e); extern int StackTraverse_R(struct SqStack S);

運行結果

4階漢諾塔： A:1 2 3 4 B: C:A -> B A:2 3 4 B:1 C:A -> C A:3 4 B:1 C:2B -> C A:3 4 B: C:1 2A -> B A:4 B:3 C:1 2C -> A A:1 4 B:3 C:2C -> B A:1 4 B:2 3 C:A -> B A:4 B:1 2 3 C:A -> C A: B:1 2 3 C:4B -> C A: B:2 3 C:1 4B -> A A:2 B:3 C:1 4C -> A A:1 2 B:3 C:4B -> C A:1 2 B: C:3 4A -> B A:2 B:1 C:3 4A -> C A: B:1 C:2 3 4B -> C A: B: C:1 2 3 4

參考文章：「遞歸練習」漢諾塔

總結

以上是生活随笔為你收集整理的汉诺塔（Tower of Hanoi） 递归代码实现 c语言（顺序栈实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。