The Blind Watchmaker

京都在住のcyobiによる雑記帳です 

--.--.--[--] スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
    --:--  Top

2009.12.26[土] ハノイの塔

 フリーマーケットで木製のパズルを見つけ、購入しました。古典的なパズルのひとつでである、ハノイの塔です。

hanoi0.jpg

 このハノイの塔は、ディスクの山を他の棒へと移動させるパズルです。移動させるには以下の制約があります。

1.ディスクは1枚ずつ他の棒へ移動できる。
2.一番上のディスクのみ移動できる。
3.小さなディスクの上に、大きなディスクを置くことはできない。

 3枚のディスクで実演すると、

hanoi1.jpg
hanoi2.jpg
hanoi3.jpg
hanoi4.jpg
hanoi5.jpg
hanoi6.jpg
hanoi7.jpg
hanoi8.jpg

7回で移動することができます。ディスクの枚数がn枚とすると、2のn乗から1を引くと移動回数になります。ディスクが64枚では、移動が終了した時、世界の終焉を迎えるという話を聞いたことがあります。ちなみに64枚では(2の64乗-1回なので18446744073709551615(1844京6744兆737億955万1615)回かかります。1枚移動させるのに1秒かかったとして計算すると、5.845420461×10の11乗年(約5845億年)となります。宇宙のはじまりが約137億年前なので、途方もない年月が必要となります。

 コンピューターで計算するとどのくらいになるか気になったので、cでプログラムを作りました。3枚のディスクで走らせた結果です。時間は簡易計算なのであまり精度は高くありません。3枚では計測不可能でしたが、16枚では109.06秒かかりました。ちなみに64枚で行うと計算上、約9億7275年かかります。私のPCは古いため遅いので、かなり時間がかかるみたいです。速いPCとプログラムを工夫すれば数百年でできるのではないでしょうか。

hanoic.jpg


 あまりきれいでないソースを、以下に置いておきます。


#include "stdio.h"
#include <time.h>
unsigned x;

void hanoi(long n,int a,int b,int c)
{
  if (n==1){
     x++;
     printf("%5d %2d のディスクを %c → %c に移動\n",x,n,a,b);
  }else{
     hanoi(n-1,a,c,b);
     x++;
     printf("%5d %2d のディスクを %c → %c に移動\n",x,n,a,b);
     hanoi(n-1,c,b,a);
  }
}


void main(void){
  x=0;
  unsigned int in;
  printf("Input Disc Number \n");
  scanf("%d",&in);
  clock_t start,end;
  start = clock();

  hanoi(in,'A','C','B');

  end = clock();
  printf("%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);//処理時間

}
Comment







(編集・削除用)


管理者にだけ表示を許可
Trackback
http://lawine.blog75.fc2.com/tb.php/278-cba8edcc
カレンダー
08 | 2017/09 | 10
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
プロフィール

cyobi

Author:cyobi
日常を綴った雑記帳です。
タイトル通り自然淘汰されるか、進化するかお楽しみに!

検索フォーム
ブロとも申請フォーム
QRコード
QRコード
Pagetop
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。