ではプログラムです。
続きは次回に
#include <stdio.h>
#include <math.h>
#define PEGS 4
#define MAX 100
int hanoi4(int, int, int, int, int, int);
int hanoi3(int, int, int, int);
void move(int, int);
void initPeg(int);
void printPeg(void);
int isqrt(int);
int peg[PEGS][MAX + 1];
int main(void) {
int size, count, h;
int xlist[10];
fprintf(stderr, "ハノイの塔の大きさは(1-%d):", MAX);
scanf("%d", &size);
initPeg(size);
printf("大きさ%dの%dペグのハノイの塔の移動方法は以下の通りです。\n---\n", size, PEGS);
printPeg();
count = hanoi4(size, 0, 3, 1, 2, 0);
printf("---\n以上%d手です。\n", count);
return(0);
}
int hanoi4(int n, int from, int to, int other1, int other2, int flag) {
int count = 0;
int h3, h4;
/* 最適分割数の計算 */
h3 = (isqrt(1 + 8 * n) - 1) / 2;
if((flag == 1) && (h3 * (h3 + 1) != 2 * n)) { h3++; }
h4 = n - h3;
if(h4 > 0) {
count += hanoi4(h4, from, other1, other2, to, flag);
}
count += hanoi3(h3, from, to, other2);
if(h4 > 0) {
count += hanoi4(h4, other1, to, other2, from, flag);
}
return(count);
}
int hanoi3(int n, int from, int to, int other) {
int count = 1;
if(n == 1) {
move(from, to);
} else {
count += hanoi3(n - 1, from, other, to);
move(from, to);
count += hanoi3(n - 1, other, to, from);
}
return(count);
}
void move(int from, int to) {
int n = peg[from][peg[from][0]];
printf("%04dを%cから%cへ動かす\n", n, (char)(0x41 + from), (char)(0x41 + to));
peg[to][++peg[to][0]] = n;
peg[from][peg[from][0]--] = 0;
printPeg();
}
void initPeg(int n) {
int i, j;
for(j = 0; j <= n; j ++) {
peg[0][j] = n - j + 1;
for(i = 1; i < PEGS; i ++) {
peg[i][j] = 0;
}
}
peg[0][0] = n;
}
void printPeg(void) {
int i, j, max = 0;
printf(" ");
for(i = 0; i < PEGS; i++) {
printf(" | ");
if(max < peg[i][0]) {
max = peg[i][0];
}
}
for(j = max; j > 0; j--) {
printf("\n ");
for(i = 0; i < PEGS; i++) {
if(peg[i][j] == 0) {
printf(" | ");
} else {
printf("%05d ", peg[i][j]);
}
}
}
printf("\n ");
for(i = 0; i < PEGS; i++) {
printf("--%c-- ", (char)(0x41 + i));
}
printf("\n\n");
}
int isqrt(int x) {
int i;
for(i = 0; i * i <= x; i++);
return(--i);
}
続きは次回に