c語(yǔ)言循環(huán)加數(shù)組實(shí)現(xiàn)漢諾塔問題

更新時(shí)間：2022年01月28日 10:29:52 作者：用戶882121311605lv-1

本文主要介紹了c語(yǔ)言循環(huán)加數(shù)組實(shí)現(xiàn)漢諾塔問題，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

簡(jiǎn)介

漢諾塔問題是學(xué)數(shù)據(jù)結(jié)構(gòu)與算法的時(shí)候會(huì)遇到的問題，相信來(lái)看本文的讀者應(yīng)該都對(duì)漢諾塔問題有基本的了解，理論上所有的遞歸都可以改成循環(huán)，常規(guī)的做法是借助堆棧，但是我一想好像用循環(huán)加數(shù)組也可以實(shí)現(xiàn)，于是就有了本文，實(shí)現(xiàn)聲明，本文最后出來(lái)的算法效率不高的，比直接用遞歸實(shí)現(xiàn)還要差很多，追求算法效率的同學(xué)就不用看這個(gè)了。
題目：假設(shè)有3個(gè)柱子，分別為A、B、C，A柱子上有數(shù)量為n個(gè)的空心圓盤，從上到下序號(hào)分別為1...n，要求把A柱子中的n個(gè)圓盤移動(dòng)到C柱中，且序號(hào)大的盤子必須在在需要小的圓盤下方。
思路：如果只有1個(gè)圓盤需要移動(dòng)，則直接從A柱移動(dòng)到C柱，如果有n個(gè)圓盤（n>1）需要移動(dòng)，則需要先把n-1個(gè)圓盤從A柱移動(dòng)到B柱，再把第n個(gè)圓盤從A柱移動(dòng)到C柱，最后把原來(lái)的n-1個(gè)圓盤從B柱移動(dòng)到C柱。

例如：

將1個(gè)圓盤從A柱移動(dòng)到C柱只需要1個(gè)步驟：

1. 把圓盤1從A移動(dòng)到C

將2個(gè)圓盤從A柱移動(dòng)到C柱需要3個(gè)步驟：

1. 把圓盤1從A移動(dòng)到B
2. 把圓盤2從A移動(dòng)到C
3. 把圓盤1從B移動(dòng)到C

將3個(gè)圓盤從A柱移動(dòng)到C柱需要7個(gè)步驟：

1. 把圓盤1從A移動(dòng)到C
2. 把圓盤2從A移動(dòng)到B
3. 把圓盤1從C移動(dòng)到B
4. 把圓盤3從A移動(dòng)到C
5. 把圓盤1從B移動(dòng)到A
6. 把圓盤2從B移動(dòng)到C
7. 把圓盤1從A移動(dòng)到C

遞歸的漢諾塔解法（c語(yǔ)言）

可以看出下面的遞歸算法的時(shí)間復(fù)雜度為O(2^n)，因?yàn)榇嬖谟姓{(diào)用2^n-2次遞歸調(diào)用和1次原生printf；而空間復(fù)雜度為O(n)，因?yàn)檫\(yùn)行時(shí)棧中最多會(huì)同時(shí)保存n個(gè)函數(shù)的調(diào)用信息。

#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);
}

解釋一下代碼中參數(shù)的含義，void towers(int n, char from, char to, char aux)的意思是把n個(gè)圓盤從from柱子移動(dòng)到to柱子，中間可以借用aux柱子。

分析一下上面的遞歸執(zhí)行過程：

我們已經(jīng)知道把1個(gè)圓盤從from移動(dòng)到to的步驟是showMove(1, from, to);

而把2個(gè)圓盤從from移動(dòng)到to的步驟是，先照著移動(dòng)1個(gè)圓盤的操作，把前面1個(gè)圓盤從from移動(dòng)到aux，再把第2個(gè)圓盤從from移動(dòng)到to，最后按照移動(dòng)1個(gè)圓盤的操作，把剛才的1個(gè)圓盤從aux移動(dòng)到to。

同理，把3個(gè)圓盤從from移動(dòng)到to的步驟是，先照著移動(dòng)2個(gè)圓盤的操作，把前面2個(gè)圓盤從from移動(dòng)到aux，再把第3個(gè)圓盤從from移動(dòng)到to，最后按照移動(dòng)2個(gè)圓盤的操作，把剛才的2個(gè)圓盤從aux移動(dòng)到to。

所以，把n個(gè)圓盤的操作從from移動(dòng)到to的步驟是，先照著移動(dòng)n-1個(gè)圓盤的操作，把前面n-1個(gè)圓盤從from移動(dòng)到aux，再把第n個(gè)圓盤從from移動(dòng)到to，最后按照移動(dòng)n-1個(gè)圓盤的操作，把剛才的n-1個(gè)圓盤從aux移動(dòng)到to。

因此，我們可以記錄移動(dòng)1個(gè)圓盤的步驟，來(lái)得到移動(dòng)2個(gè)圓盤的步驟，通過移動(dòng)2個(gè)圓盤的步驟來(lái)得到移動(dòng)3個(gè)圓盤的步驟,...最后得到移動(dòng)n個(gè)圓盤的步驟。經(jīng)過分析可以知道移動(dòng)n個(gè)圓盤一共會(huì)有2^n-1個(gè)步驟

循環(huán)實(shí)現(xiàn)漢諾塔問題（c語(yǔ)言）

為了代碼更加易懂，這里寫了注釋，修改了部分變量命名，統(tǒng)一用數(shù)組保存步驟集合，最后才輸出。
可以看出這個(gè)算法的時(shí)間復(fù)雜度還是O(2^n)，一共會(huì)執(zhí)行2^(n+1)-1次setMoveAction語(yǔ)句和2^n-1次，printf語(yǔ)句，比起直接用遞歸還要復(fù)雜一些，而空間復(fù)雜度也是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++)
?? ?{
?? ??? ?//本次循環(huán)會(huì)將把i個(gè)盤子從from移動(dòng)到to的步驟記錄到actions數(shù)組中
?? ??? ?// 設(shè)size是把i-1個(gè)盤子從from移動(dòng)到to的步驟數(shù)，
?? ??? ?// 則本次循環(huán)中集合{actions[x] | 0 <= x <= size -1 }就是size是把i-1個(gè)盤子從from移動(dòng)到aux的步驟集合，
?? ??? ?//而action[size]是把第i個(gè)盤子從from移到to，
?? ??? ?//而集合{actions[x] | size + 1 <= x <= 2*size }就應(yīng)該是把i-1個(gè)盤存從aux移動(dòng)到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);
?? ?}
}

到此這篇關(guān)于c語(yǔ)言循環(huán)加數(shù)組實(shí)現(xiàn)漢諾塔問題的文章就介紹到這了,更多相關(guān)c語(yǔ)言漢諾塔內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: