工学1号馆

home

Hanoi 塔问题

Wu Yudong    December 20, 2016     Algorithm   754

1、常规Hanoi 塔问题

#include <stdio.h>
void hanoi(int n, char A, char B, char C)
{
if (n == 1) {
printf("Move sheet %d from %c to %c\n", n, A, C);
} else {
hanoi(n - 1, A, C, B);
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n - 1, B, A, C);
}
}
int main()
{
int n;
printf("请输入盘数：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}

2、双色Hanoi 塔问题

#include <stdio.h>
void hanoi(int disks, char source, char temp, char target)
{
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks - 1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks - 1, temp, source, target);
}
}

void hanoi2colors(int disks)
{
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
for (i = disks / 2; i > 1; i--) {
hanoi(i - 1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
hanoi(i - 1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
}
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
}

int main()
{
int n;
printf("请输入盘数：");
scanf("%d", &n);
hanoi2colors(n);
return 0;
}

3、三色Hanoi 塔问题

#include <stdio.h>
void hanoi(int disks, char source, char temp, char target)
{
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks - 1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks - 1, temp, source, target);
}
}

void hanoi3colors(int disks)
{
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
if (disks == 3) {
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, source);
printf("move disk from %c to %c\n", target, temp);;
} else {
hanoi(disks / 3 - 1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);

hanoi(disks / 3 - 1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);

hanoi(disks / 3 - 1, source, target, temp);
printf("move disk from %c to %c\n", target, source);
printf("move disk from %c to %c\n", target, source);

hanoi(disks / 3 - 1, temp, source, target);
printf("move disk from %c to %c\n", source, temp);

for (i = disks / 3 - 1; i > 0; i--) {
if (i > 1) {
hanoi(i - 1, target, source, temp);
}
printf("move disk from %c to %c\n", target, source);
printf("move disk from %c to %c\n", target, source);
if (i > 1) {
hanoi(i - 1, temp, source, target);
}
printf("move disk from %c to %c\n", source, temp);
}
}
}

int main()
{
int n;
printf("请输入盘数：");
scanf("%d", &n);

hanoi3colors(n);
return 0;
}