c語言怎么循環加數組實現漢諾塔

今天小編給大家分享一下c語言怎么循環加數組實現漢諾塔的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

簡介

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

例如：

將1個圓盤從A柱移動到C柱只需要1個步驟：

1. 把圓盤1從A移動到C

將2個圓盤從A柱移動到C柱需要3個步驟：

1. 把圓盤1從A移動到B
2. 把圓盤2從A移動到C
3. 把圓盤1從B移動到C

將3個圓盤從A柱移動到C柱需要7個步驟：

1. 把圓盤1從A移動到C
2. 把圓盤2從A移動到B
3. 把圓盤1從C移動到B
4. 把圓盤3從A移動到C
5. 把圓盤1從B移動到A
6. 把圓盤2從B移動到C
7. 把圓盤1從A移動到C

遞歸的漢諾塔解法（c語言）

可以看出下面的遞歸算法的時間復雜度為O(2^n)，因為存在有調用2^n-2次遞歸調用和1次原生printf；而空間復雜度為O(n)，因為運行時棧中最多會同時保存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);
}

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

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

分析一下上面的遞歸執行過程：

我們已經知道把1個圓盤從from移動到to的步驟是showMove(1, from, to);

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

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

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

因此，我們可以記錄移動1個圓盤的步驟，來得到移動2個圓盤的步驟，通過移動2個圓盤的步驟來得到移動3個圓盤的步驟,...最后得到移動n個圓盤的步驟。經過分析可以知道移動n個圓盤一共會有2^n-1個步驟

循環實現漢諾塔問題（c語言）

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

以上就是“c語言怎么循環加數組實現漢諾塔”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。