ハノイの塔を解く(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’: ‘木’} >>> […]

Python でテクストファイルを読み書きする。

With と For iterater を使うとファイルを明示的にクローズしないでもよいそうだ。 例題でやっているのはTest.txtというファイルから一行ずつ読み込んでリストを作成し、それをリストオブジェクトのSortedメソドで並び替えをしたのち、test2.txtというファイルに書き戻す、という作業。 なんか簡単にできるし(簡単だけど)、コメントを入れなくても読み解きやすい感じ。このあたりがPythonの強みか。 a_list=[] with open(“test.txt”, mode=”r”,encoding=’utf-8′) as a_file: for a_line in a_file: a_list.append(a_line.rstrip()) a_list = sorted(a_list) with open(“test2.txt”, mode=”w”, encoding=’utf-8′) as a_file: for a_line in a_list: a_file.write(a_line+’\n’)

Pythonの関数定義とパラメーター

Python3 をいじっていく中で、気が付いたことをこのプログにぼちぼち書き留めておこうと思う。 Pythonの関数定義ではパラメーターも戻り値もタイプを指定しない。C++,Java,Pascalなどの知識のある学習者には異常に見えるが、Python は loosely typed language なんである。 >>> def foo(a,b,c): return a*100 + b*10 + c >>> foo(3,2,1) 321 パラメーターに初期値を持たせることができる。 パラメーターを指定しない場合はその初期値が使用される。 >>> def bar(a=1, b=1, c=1): return a*100 + b*10 + c >>> bar() 111 >>> bar(3) 311 >>> bar(3,4) 341 >>> bar(3,4,1) 341 さらにはパラメーターを明示すれば、カッコ内に現れる順序を気にする必要がなくなる。 >>> foo (a=5,c=2,b=1) 512 >>> bar(c=3,b=2) 123 >>> bar(c=9) 119 >>> bar(c=6,b=4,a=2) 246

Ruby と Python

どちらもInterpreter Languageだが、ひとつを選べと言われたらどちらを覚えたほうがよいのだろう。  日本ではRubyがかなり人気があるようだが、WorldwideのUser BaseではPythonのほうが多い。 多いと言ってもPHPとかに比べるとかなり少ない。 Ruby # Old “coke” program from 80’s Basic programming book in Ruby answer = Random.rand(1..100) count,guess = 0,0 puts ‘I am thinking about number between 1 and 100. Can you guess?’ while (answer != guess) guess = gets.to_i count += 1 if guess > answer puts “#{guess} is too high” elsif guess < answer puts "#{guess} is too low" else puts "you got it right in #{count} try!" end end Python """Old "coke" program from 80's Basic programming book, in Python""" import random answer = random.randrange(1,100) print ("I am thinking a number between 1 and 100. Hope you can guess") guess, count = 0,0 while (answer != […]