ハノイの塔のプログラムの作り方

質問

学校でハノイの塔を組むことになったのですが、具体的なプログラムがわかりません。教えてください。

回答No.2

Tacosan · ベストアンサー

ハノイの塔を解く＊実際に動く＊プログラムをだしてみましょうか.
gcc -std=c99 でコンパイル, 実行できることを確認しています.
但し, このプログラムをそのまま提出するとまず間違いなく疑われることになるでしょう.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef unsigned long long uint64;
const int maxDisks = CHAR_BIT * sizeof (uint64);

int bitpos(uint64 bits)
{
int pos = 0;

if (bits & 0xFFFFFFFF00000000ULL) {
pos += 32;
bits >>= 32;
}

if (bits & 0xFFFF0000ULL) {
pos += 16;
bits >>= 16;
}

if (bits & 0xFF00ULL) {
pos += 8;
bits >>= 8;
}

if (bits & 0xF0ULL) {
pos += 4;
bits >>= 4;
}

if (bits & 0xCULL) {
pos += 2;
bits >>= 2;
}

if (bits & 0x2ULL) {
pos += 1;
bits >>= 1;
}

return pos;
}

void doHanoi(int disks)
{
if (disks >= maxDisks) {
fprintf(stderr, "Error: # of disks should be less than %uz\n", maxDisks);
return;
}

int numberOfDisks[3] = {
disks, 0, 0,
};
uint64 maxCounts = (1ULL << disks)-1;

int diskPos[maxDisks];
for (int i = 0; i < maxDisks; i++) {
diskPos[i] = 0;
}

for (uint64 count = 0; count < maxCounts; ) {
uint64 oldcount = count++;
uint64 changed = count ^ oldcount;
changed ^= changed >> 1;
int disk = bitpos(changed);

int level = --numberOfDisks[diskPos[disk]];
int newPos = ((disk % 2 == 0) ? diskPos[disk]+2 : diskPos[disk]+1) % 3;

printf("Move %d from %d (%d) to %d (%d)\n", disk, diskPos[disk], level, newPos, numberOfDisks[newPos]++);
diskPos[disk] = newPos;
}
}

int main(int ac, char *av[])
{
if (av[1] == 0) {
fprintf(stderr, "Usage: %s <# of disks>.\n", av[0]);
return EXIT_SUCCESS;
}

int disks = atoi(av[1]);

doHanoi(disks);

return EXIT_SUCCESS;
}

回答No.4

Tacosan

「ゲームをする」とはどういう意味でしょうか?
ユーザーが実際に円盤を動かせるようにするということ? もしそうだとしたら, 「どの円盤を」「どこに」動かすか, どのように指示するという仕様なんですか? そうでないとしたら, 実際にどのような動作を要求しているのか, きちんと書いてもらえますか?
そうそう, 対象となる処理系もちゃんと書いてください.
もちろん, 「書いたからといって解いてもらえるとは限らない」んだけどね.

お礼

ありがとうございました。

回答No.3

Tacosan

あ～間違えた....
関数 bitpos が 64ビットであることに依存しているので,
const int maxDisks = CHAR_BIT * sizeof (uint64);
は
const int maxDisks = 64;
に変更してください.

補足

実際にゲームをするプログラムがほしいのですが・・教えてもらえますか？

回答No.1

shimix

どうぞ・・

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94

＃まさか「動くソースが必要」なんてことはないですよね？