ハノイの塔を解く(Solving Towers of Hanoi)

ハノイの塔というのはパズルだが、リカージョンというアルゴリズムによくなじむのでプログラミングの教科書に出ていることがある。 自分がこれを見たのは”Oh Pascal!”というパスカルの入門書で30年くらい前に発行された学生向けの教科書だ。 パズルの内容はこんな具合。 1.3本の棒が立っている。仮にこれを右からA,B,Cとする。 2.Aには真ん中に穴のあいた円盤が積み上げてある。円盤の直径は底にあるものが一番大きく、上に行くほど小さくなる。 3.一度に一個ずつこのこの円盤を取り出して他の棒に移すことができる。最終的には全部の円盤をCに移したい。 4.ただし、大きな円盤を小さな円盤の上に置くことはできない。 Hanoiの塔というのはこの”金の”円盤を64枚積み上げたものだそうで、このパズルが解けたときには世の中が終焉を迎える、というオトロしい落ちがついている。 これをコンピュータープログラムを使って解くとどうなるか、という話である。 パターンを見つけるために少ない枚数で実際に解くことを試みる。 Disk(円盤)の数が一枚の時には簡単だ。円盤をAからCに移せばよい。 Move(1disk from A to C) = Move a Disk from A to C では2枚の時にはどうなるか Move(2disks from A to C) = Move a Disk from A to B Move a Disk from A to C Move a Disk from B to C ここで棒Bを使うことになる。 つまり、まず上の円盤を棒AからBに移し、下の円盤をAからCへ、最後にBに移してあった円盤をCに移して完成だ。 Move (2 disks from A to C) = Move (2 disks from A to C using B) 3枚はどうか。 すでに2枚を動かす方法はわかっているのその方法を使ってまずは2枚をBに動かしておき、最後の一枚をAからCに移動、さらに2枚を動かす方法を使ってBからCに移動するという方法で動かせる。 Move(3 disks from A to C using B) = Move(2 disks from A to B using C) Move a disk from A to C Move (2 disks from B to c using A) 4枚の場合も同様に考えられるのでパターンとしては (n-1)枚の円盤をAからBに移す。最後の円盤をAからCに移動し、その後(n-1)枚の円盤をBからCに移す。 ということになる。 Move (n disks from A to C using B) […]

Python、comprehension を使った一括処理

Pythonには” … for … in”という構文を使った、一括でメンバー要素を処理する機能がある。Comprehensionと呼ばれ、リスト、セット、辞書に使える。 リストの使用例 >>> a_list =list(range(10)) >>> a_list [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> a_list = [x**2 for x in a_list]  –List comprehension >>> a_list [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] If を使い、要素のFilteringをしてから処理することもできる。下はリスト中、偶数だけを処理して新しいリストを作成した例。  >>> a_list = list(range(10)) >>> a_list = [x**2 for x in a_list if (x%2 ==0)] >>> a_list [0, 4, 16, 36, 64] Python Dictionary の キーと値をスワップして新しい辞書を作る。 >>> week_dict={‘Mon’:’月’,’Tue’:’火’,’Wed’:’水’,’Thu’:’木’,’Fri’:’金’,’Sat’:’土’,’Sun’:’日’} >>> youbi_dict={value:key for key,value in week_dict.items()} >>> youbi_dict {‘木’: ‘Thu’, ‘土’: ‘Sat’, ‘月’: ‘Mon’, ‘火’: ‘Tue’, ‘水’: ‘Wed’, ‘日’: ‘Sun’, ‘金’: ‘Fri’} >>> week_dict {‘Mon’: ‘月’, ‘Fri’: ‘金’, ‘Tue’: ‘火’, ‘Sat’: ‘土’, ‘Sun’: ‘日’, ‘Wed’: ‘水’, ‘Thu’: ‘木’} >>> […]

Python3 の文字列 覚書

Python3ではstring = unicode string をアレーとして考えてslice するときもマルチバイト文字を気にする必要がない。 >>> s = ‘pythonに、どっぷりつかる’ >>> len(s) 15 >>> s[8:] ‘どっぷりつかる’ >>> s[:6] ‘python’ >>> s[:7]+s[8:12] ‘pythonにどっぷり’ >>> ただ、よいことばかりではなく、fileなどからのIO処理では読み込まれるのがバイト列になるため変換をしてあげる必要がある。 Python 2.7では必要なかったのでPython2.xのプログラムを移植するときに注意が必要。encode()としてunicodeのバイト列表示、decode()でUnicodeのバイト列をUnicodeの文字列表示 >>> s.encode() b’python\xe3\x81\xab\xe3\x80\x81\xe3\x81\xa9\xe3\x81\xa3\xe3\x81\xb7\xe3\x82\x8a\xe3\x81\xa4\xe3\x81\x8b\xe3\x82\x8b’ >>> b’python\xe3\x81\xab\xe3\x80\x81\xe3\x81\xa9\xe3\x81\xa3\xe3\x81\xb7\xe3\x82\x8a\xe3\x81\xa4\xe3\x81\x8b\xe3\x82\x8b’.decode() ‘pythonに、どっぷりつかる’ >>> 最初のバイト列がUnicode以外の文字列の場合はencodingを指定 >>> chara = b’\x63\x6c\x69\x63\x68\xe9′ >>> print(chara) b’clich\xe9′ >>> print(chara.decode(‘latin-1’)) cliché