溫馨提示×

c語言漢諾塔遞歸算法怎么實(shí)現(xiàn)

小億
96
2023-10-30 11:42:56
欄目: 編程語言

下面是使用遞歸算法實(shí)現(xiàn)C語言版本的漢諾塔問題：

#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3; // 將三個盤子從A移動到C
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

輸出結(jié)果：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

該算法使用遞歸的思想，將問題分解為更小的子問題。首先將 n-1 個盤子從起始柱子（from）移動到輔助柱子（aux），然后將最大的盤子從起始柱子（from）移動到目標(biāo)柱子（to），最后將 n-1 個盤子從輔助柱子（aux）移動到目標(biāo)柱子（to）。通過遞歸調(diào)用，將問題規(guī)?？s小，直到只剩下一個盤子需要移動。

0 踩