初等整数論には題材が豊富だ。今度はエラトスセネスの篩をやってみよう。以下に引数を指定すると、2からその引数までの間にある素数を表示する関数、eratosthenesを作成する。

eratosthenes.py

def deletemultiples(pn,L):
for i in L:
if i != 0 and i != pn:
if i % pn == 0:
L[i-2] = 0
return L
def eratosthenes(n):
L = range(2,n+1)
for i in L:
if i != 0:
L = deletemultiples(i,L)
for i in L:
if i != 0:
print i,

実行結果。

>>> eratosthenes(10)
2 3 5 7
>>> eratosthenes(100)
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
>>> eratosthenes(1000)
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

アルゴリズムはもっとやりようあるけど一応出来た。forループに使っているリストを、forループの中でいじれるのか心配だったけど、どうやらやってもいいみたい。助かった。

スライシングも非常に便利。リストや文字列に対して使えます。文字列の処理なんかには重宝しそうです。

とりあえず使ってみましょう。

また標準出力から文字列を読み取り、受け取った文字列の8文字までを結果として返す関数と、9文字目以降を*でマスクして返す関数を作ってみる。

cutletters.py

def cutletters(s,x):
return s[:x]
def maskletters(s,x):
cutlength = len(s) - x
if cutlength > 0:
s = s[:x]
s = s + '*' * cutlength
return s
else:
return s
while(1):
s = raw_input()
if s == '':
break
print cutletters(s,8)
print maskletters(s,8)

実行すると以下のようになる。

C:\Python24>python.exe cutletters.py
Michael Jordan
result1 : Michael
result2 : Michael ******
abcdefghijklmnopqrstu
result1 : abcdefgh
result2 : abcdefgh*************
hatena
result1 : hatena
result2 : hatena

マスクの方はもう少しスマートな書き方があるのかも。

追記：

こうすればもっとスマートだ。うん。リスト万歳。

def maskletters(s,x):
L = list(s)
L[x:] = ['*'] * (len(s) - x)
return ''.join(L)

僕のプログラミング経験にはMap関数に値するものは出てこなかった。非常に便利な機能である。さっそく使ってみよう。

n個の中からx個を取り出すときの組み合わせを求める関数を以下のように定義する。

def factorial(x):
if x == 1:
return 1
else:
return x * factorial(x - 1)
def combination(x,n):
return factorial(n) / (factorial(n - x) * factorial(x))

map関数を用いて以下のように実行すると、5個から3個、8個から4個、10個から5個の計算結果をリストの形でいっぱつで返してもらうことが出来る。

>>> map(combination,[3,4,5],[5,8,10])
[10, 70, 252]

うーん便利。コード書く量大分減らせそう。

結城さんからトラックバックを頂いた。Haskellもかなりシンプルに書けるんですね。いつか勉強するときがくるかもしれないです。

さて、しばらくは標準出力から取得した文字列で遊んでみることとする。

countwords.py

def countwords(s):
count = 0
space = " "
index = -1
for i in range(len(s)):
if i > index:
if s[i] != space:
for j in range(i,len(s)):
if (s[j] == space) or (j == len(s) - 1):
count += 1
index = j
break
return count
while(1):
s = raw_input()
if s == '':
break
c = countwords(s)
if c > 1:
print 'The string has %d words' % (c)
else:
print 'The string has just %d word' % (c)

実行結果

C:\Python24>python.exe countwords.py
This is a pen
The string has 4 words
My Name is John
The string has 4 words
It's nice to meet   you!
The string has 5 words

空白が多かったときなどの処理に気をつけなければならなかったので、少し苦戦。

しかし遊びのプログラムは本当に楽しい。

じゃあ次は標準入力から文字列を受け取るプログラム。受け取った後表示するだけでは芸がないので、文字列の長さもついでに返すようにしてみる。空白を受け取った場合は終了と判断する。

stdinput.py

while(1):
s = raw_input()
if s == '':
break
print 'What you have just typed is \'%s\'' % (s)
print 'The length of the string is %d' % (len(s))

実行結果。

C:\Python24>python.exe stdinput.py
hatena
What you have just typed is 'hatena'
The length of the string is 6
What is your name?
What you have just typed is 'What is your name?'
The length of the string is 18

これは色々拡張して遊べそうだ。

宣言どおり始めてみよう。とりあえず基本からやるってことで、ユークリッド互除法を書いてみる。うろ覚えで書いてみると、こんな感じ？

def euclid(x,y):
if x == y:
return x
else:
if x > y:
return euclid(x - y,y)
else:
return euclid(y,x)

結果は合っているようだが、見た目がイマイチ？Wikipedia見てみたら、そのまんまPythonの例が出てた。

def gcd(m,n):
while n != 0:
t = m%n
m = n
n = t
return abs(m)

美しいです。

Foundations of Python Network Programming

• 作者: John Goerzen
• 出版社/メーカー: Apress
• 発売日: 2004/08/30
• メディア: ペーパーバック
• クリック: 59回
• この商品を含むブログ (13件) を見る

これは良書だと思う。特に英語表現が非常に平易なのが素晴らしい。PythonとNetworkの世界を少しだけ知っている人であれば、多少英語が苦手でもスイスイと読みこなせてしまうだろう。そういう意味では知識的には既に知っていても、「英語の技術書」入門として読んでみても良いかと。

取り上げられている内容としては、簡単に挙げてみると

• Sockets（Client, Server）
• HTML、XMLのParse
• Email
• FTP, SSL
• CGI, mod_python, SimpleXMLRPCServer
• Forking, Threading

のような感じ。それぞれが浅く広く解説されているので「とりあえずPythonでネットワークプログラムしたいなぁ」という人がまず手に取ってみるような本だと思う。

まだ日本語版は出ていない模様。翻訳しようかしら。

という訳で、前回のエントリの解法を見直す。

各歩数のパターンにて、1段飛ばしで昇る回数は以下のように決まっている。

15歩のパターンのとき　→　1段飛ばしで昇ることはない
14歩のパターンのとき　→　1回だけ1段飛ばしで昇る
13歩のパターンのとき　→　2回だけ1段飛ばしで昇る
・
・
・

というような具合である。つまり

1段飛ばしする回数 = 段数 – 歩数

となる。

ここで8歩のパターンの一つをもう一度足し算で表してみる。

2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 = 15

とすると、これは「8個の中から7つを選ぶパターンがいくつあるか」という問題と同義であることに気付く。つまり「8歩中、7つの1段飛ばしをどこに入れれば良いのか」というのを数えていけば良い。

これはいわゆる以下の式で求められる。x歩パターンのとき、n個の1段飛ばしがあるとすると、

となります。懐かしいですね。これを15歩から8歩の各パターンで計算してあげ足し合わせれば、15段を昇るパターンがいくつあるのかを計算できそうです。この方針でプログラムを書いてみました。

def factorial(x):
if x == 1:
return 1
else:
ans = x * factorial(x - 1)
return ans
def Kaidan(Dan):
hit = 0
a = 0
for j in range(Dan,int(Dan - 0.5) / 2,-1):
a = Dan - j
if a == 0 or a == j:
ptn = 1
else:
ptn = factorial(j) / (factorial(j - a) * factorial(a))
hit += ptn
print hit
if __name__ == '__main__':
Kaidan(15)

これだと現実的な速度です（笑）。

しかしこの問題の答えが再帰構造になっているのって、実際に計算値を並べていけば気付くけど、なぜそうなっているのかが全然理解出来ない。誰か教えて下さい。

なんかすげー面白そうな番組が始まったんですね。テレビは来週から見始めるとして、Danさんのエントリに問題が載ってたので解いてみよう。ついでに最近Javaと共に勉強しているPythonの修行にも丁度良さそうなので、プログラムはPythonで書いてみる。

自分で解いてみたい方は以下はネタバレになりますのでご注意を。

問題

15段の階段があります。階段を一段づつ上ってもOK、一段飛ばしで上ってもOKとして、この階段の上り方が何通りあるか答えなさい。

要するに、一回に1段か2段進めるという訳ですね。そして上るまでの歩数に注目すると、「最多で15歩、最小で8歩」ということになる。

15歩のときの昇るときの様子は以下のように表せる。
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 15

8歩で昇るときの様子の一例は以下のように表せる。
2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 = 15

この8歩の方に注目してみれば、「8歩で昇るパターン」には8通りあることはすぐ分かると思います。つまり1段昇るのを1歩目〜8歩目のどこにもってきても良いからです。15のパターンは上に上げた1つのパターンしかありません。

さて8歩や15歩と同じように、9歩〜14歩でもこのように「1と2の組み合わせ」で15になるパターンがいくつあるのかを考えれば、この問題の答えが見つかりそうです。

とりあえず、プログラムを使って超強引に解いてみます。超強引とは15歩〜8歩、つまり1と2の数が15個〜8個の足し算に対して答えが15になるパターンを数えていきます。

def ListSum(L):
t = 0
for i in L:
t += i
return t
def PlusOne(L):
L[0] = L[0] + 1
for i in range(len(L)):
if L[i] == 3:
L[i] = 1
L[i + 1] = L[i + 1] + 1
def Kaidan(Dan):
hit = 0
for j in range(Dan,int(Dan - 0.5) / 2,-1):
L = [1] * j
flg = 1
while flg:
sum = ListSum(L)
if sum == Dan:
hit += 1
if sum == j * 2:
flg = 0
if flg == 1:
PlusOne(L)
print hit
if __name__ == '__main__':
Kaidan(15)

解法、プログラム共に全然エレガントじゃない（笑）。しかも実行してみると分かると思うけど、20段くらいで使い物にならない速度です。

速度が遅い原因は「ありえないパターン」についても調べまくっているからであると思う。ありえないパターンとは、例えば8歩で昇るパターンの場合、1が2つ入ることはありえない。1が1つじゃないと15まで届きませんからね。

この辺を考慮して、次回改善策を披露します。

他の人は数学的に解いてるなあ…

番組のホームページは以下。「99.9%は仮説」の著者、竹内薫氏も出演している模様。
http://www.fujitv.co.jp/b_hp/komanechi/index.html