/* $Id: hanoi.html,v 1.1 2009/06/22 16:12:12 kishi Exp kishi $ */
/* Author : KISHI Yasuhiro */
/* Description: ハノイの塔のシミュレーション */
#include <stdio.h>
#define EMPTY -1
int N;
typedef struct
{
int *value;
int count;
} STACK;
STACK source;
STACK destination;
STACK temporary;
void
init (int n)
{
int i;
source.value = (int *) calloc (n, sizeof (int));
destination.value = (int *) calloc (n, sizeof (int));
temporary.value = (int *) calloc (n, sizeof (int));
source.count = n;
destination.count = 0;
temporary.count = 0;
for (i = 0; i < n; i++) {
destination.value[i] = EMPTY;
temporary.value[i] = EMPTY;
}
for (i = 0; i < n; i++) {
source.value[n - i - 1] = i;
}
}
void
show_image (int n)
{
int i;
printf ("%6s %6s %6s\n", "src", "dst", "tmp");
printf ("%6s %6s %6s\n", "------", "------", "------");
for (i = n - 1; i >= 0; i--) {
if (source.value[i] == -1) {
printf ("%6s", " ");
}
else {
printf ("%6d", source.value[i]);
}
printf (" ");
if (destination.value[i] == -1) {
printf ("%6s", " ");
}
else {
printf ("%6d", destination.value[i]);
}
printf (" ");
if (temporary.value[i] == -1) {
printf ("%6s", " ");
}
else {
printf ("%6d", temporary.value[i]);
}
printf ("\n");
}
printf ("\n");
}
void
action (int n, STACK * from, STACK * to)
{
to->value[to->count] = from->value[from->count - 1];
from->value[from->count - 1] = EMPTY;
from->count--;
to->count++;
/*
* printf("from_count=%d, to_count=%d\n",from->count,to->count);
*/
}
void
hanoi (int n, char a, char b, char c)
{
STACK *from, *to;
if (n > 0) {
hanoi (n - 1, a, c, b);
/*
* printf("#%d plate is moved ... %c -> %c\n", n, a, b);
*/
from = (a == 'a') ? &source : (a == 'b')
? &destination : (a == 'c') ? &temporary : NULL;
to = (b == 'a') ? &source : (b == 'b')
? &destination : (b == 'c') ? &temporary : NULL;
action (n, from, to);
show_image (N);
hanoi (n - 1, c, b, a);
}
}
int
main (int argc, char **argv)
{
if (argc != 2) {
fprintf (stderr, "Usage: %s number\n", argv[0]), exit (-1);
}
N = atoi (argv[1]);
init (N);
show_image (N);
hanoi (N, 'a', 'b', 'c');
return 0;
}
■実行結果
$ ./TowerOfHanoi 6
src dst tmp
------ ------ ------
0
1
2
3
4
5
src dst tmp
------ ------ ------
1
2
3
4
5 0
src dst tmp
------ ------ ------
2
3
4
5 1 0
src dst tmp
------ ------ ------
2
3
4 0
5 1
src dst tmp
------ ------ ------
3
4 0
5 1 2
src dst tmp
------ ------ ------
0
3
4
5 1 2
src dst tmp
------ ------ ------
0
3
4 1
5 2
src dst tmp
------ ------ ------
3 0
4 1
5 2
src dst tmp
------ ------ ------
0
4 1
5 3 2
src dst tmp
------ ------ ------
4 0 1
5 3 2
src dst tmp
------ ------ ------
1
4 0
5 3 2
src dst tmp
------ ------ ------
0
1
4
5 3 2
src dst tmp
------ ------ ------
0
1
4 2
5 3
src dst tmp
------ ------ ------
1
4 2
5 3 0
src dst tmp
------ ------ ------
1
4 2
5 3 0
src dst tmp
------ ------ ------
0
1
4 2
5 3
src dst tmp
------ ------ ------
0
1
2
5 3 4
src dst tmp
------ ------ ------
1
0 2
5 3 4
src dst tmp
------ ------ ------
0 2 1
5 3 4
src dst tmp
------ ------ ------
0
2 1
5 3 4
src dst tmp
------ ------ ------
0
2 1
5 3 4
src dst tmp
------ ------ ------
2 0 1
5 3 4
src dst tmp
------ ------ ------
1
2 0
5 3 4
src dst tmp
------ ------ ------
0
1
2
5 3 4
src dst tmp
------ ------ ------
0
1
2 3
5 4
src dst tmp
------ ------ ------
1 0
2 3
5 4
src dst tmp
------ ------ ------
0
2 3
5 1 4
src dst tmp
------ ------ ------
2 0 3
5 1 4
src dst tmp
------ ------ ------
2
0 3
5 1 4
src dst tmp
------ ------ ------
2
0 3
5 1 4
src dst tmp
------ ------ ------
1
2
0 3
5 4
src dst tmp
------ ------ ------
0
1
2
3
5 4
src dst tmp
------ ------ ------
0
1
2
3
5 4
src dst tmp
------ ------ ------
1
2
0 3
5 4
src dst tmp
------ ------ ------
2
0 3
1 5 4
src dst tmp
------ ------ ------
2
0 3
1 5 4
src dst tmp
------ ------ ------
0 2 3
1 5 4
src dst tmp
------ ------ ------
0
2 3
1 5 4
src dst tmp
------ ------ ------
1 0
2 3
5 4
src dst tmp
------ ------ ------
0
1
2 3
5 4
src dst tmp
------ ------ ------
0
1
2
3 5 4
src dst tmp
------ ------ ------
1
0 2
3 5 4
src dst tmp
------ ------ ------
0 2 1
3 5 4
src dst tmp
------ ------ ------
0
2 1
3 5 4
src dst tmp
------ ------ ------
0
2 1
3 5 4
src dst tmp
------ ------ ------
2 0 1
3 5 4
src dst tmp
------ ------ ------
1
2 0
3 5 4
src dst tmp
------ ------ ------
0
1
2
3 5 4
src dst tmp
------ ------ ------
0
1
2 4
3 5
src dst tmp
------ ------ ------
1
2 4
3 5 0
src dst tmp
------ ------ ------
1
2 4
3 5 0
src dst tmp
------ ------ ------
0
1
2 4
3 5
src dst tmp
------ ------ ------
0
1
4
3 5 2
src dst tmp
------ ------ ------
1
0 4
3 5 2
src dst tmp
------ ------ ------
0 4 1
3 5 2
src dst tmp
------ ------ ------
0
4 1
3 5 2
src dst tmp
------ ------ ------
3 0
4 1
5 2
src dst tmp
------ ------ ------
0
3
4 1
5 2
src dst tmp
------ ------ ------
0
3
4
1 5 2
src dst tmp
------ ------ ------
3
0 4
1 5 2
src dst tmp
------ ------ ------
2
3
0 4
1 5
src dst tmp
------ ------ ------
2
3
4
1 5 0
src dst tmp
------ ------ ------
1
2
3
4
5 0
src dst tmp
------ ------ ------
0
1
2
3
4
5
戻る