漢諾塔問題（C語言遞歸實現）

一、問題分析

1.要用遞歸實現漢諾塔問題得先瞭解遞歸的兩個必要條件

（1）存在限制條件，當滿足這個條件的時候，遞歸將不再繼續

（2）每次調用遞歸之後會越來越接近這個限制條件

2.漢諾塔問題用遞歸解決的思路

（1）假設有n個大小不一樣的盤子且大盤子下麵不能有小盤子，三根柱子A,B,C

（2）找到限制條件：當只需要移動的盤子只有一個時直接移動該盤子

有n個盤子在A柱，將n-1個盤子移動到B柱，將A柱上剩餘的1個盤子移動到C柱

有n-1個盤子在B柱，將n-2個盤子移動到A柱，將B柱上剩餘的1個盤子移動到C柱

有n-2個盤子在A柱，將n-3個盤子移動到B柱，將A柱上剩餘的1個盤子移動到C柱

......

有2個盤子在A或B柱上，將1個盤子移動到B或A柱上，將A或B柱上剩餘的1個盤子移動到C柱

將A或B柱上的1個盤子移動到C柱上，完成了移動

二、具體代碼

#include <stdio.h>
void move(char ch1, char ch2)
{
    //把一根柱子的最上面的一個盤子移到另外一根柱子的最上面
    printf("%c->%c\n", ch1, ch2);
}
void Hanoi(char a, char b, char c, int n)
{
    if (n == 1)
    {
        //當移動的盤子數量只有一個的時候直接使用move函數
        move(a, c);
    }
    else
    {
        Hanoi(a, c, b, n - 1);//A柱藉助C柱將n-1個盤子移動到B柱       
        move(a, c);//將A柱剩餘的一個盤子移動到C柱                    
        Hanoi(b, a, c, n - 1);//將B柱的n-1個盤子藉助A柱移動到C柱     
    }
}
int main()
{
    int n;//要移動的盤子的總數
    scanf("%d", &n);
    Hanoi('A', 'B', 'C', n);//A柱藉助B柱將n個盤子移到C柱上
    return 0;
}

三、運行結果

四、總結

一開始打算用數組內移動元素的方式來寫，但覺得編譯後的結果很難看到具體的移動過程，於是借鑒了CSDN上一位老鐵的列印移動柱子的方法，並配上了漢諾塔遞歸最底層的邏輯思維寫出來的，並且補全了具體的遞歸步驟