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

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