プロジェクトオイラー Problem3

「プロジェクト　オイラー」の問題をpythonでやってみます。


出典：Project Euler（日本語翻訳サイト）
参考：サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 3
13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。

私の解答例は以下のとおりです。
－－－－－

def f(n):
	a, p, b, q = 2, n, n, n
	while a<=b:
		if q%a: a += (a%2 + 1)
		else: p, b, q = a, b/a, q/a
	return p
	
print f(600851475143)

－－－－－

処理本体は関数fに記述し、答えをprint文で出力します。

やり方は最大素数の候補pを、その最小値候補aと最大値候補bで挟み、その範囲を狭くしていって、最小値候補a≦最大値候補bが成り立たなくなったら終了というものです。

１．whileループの前の変数初期化
　以下の４つの変数を１行で初期化しています。
・a：最大素因数の最小値候補です。初期値は最小の素数である2です。
・p：求める素因数です。引数そのものが素数である場合が最大なので初期値はnです。
・b：最大素因数の最大値候補です。初期値は引数nです。
・q：割り切れるかの判定対象値です。初期値は引数nです。

次にwhileループの中の処理です。
２．割り切り判定
　%演算子は割り算の余りを返し、論理判定では0がFalse、0以外がTrueと判定されます。
　if文の条件式q%aでは、Trueが割り切れない場合で、Falseが割り切れる場合です。

３．判定対象値qが最小値候補aで割り切れないとき
　最小値候補aを次に大きい値に進めて、whileループの先頭に戻ります。
　最小値候補aは素数を小さい順に試せばいいのですが、処理を簡単にするためにここでは「２と３以上の奇数」を順に試しています。
　この方法で素数は必ず含みますが、9や15などの素数ではない数でも割り切れるか余分に判定することになります。
　
　(a%2 + 1)は、2で割り切れると1、2で割り切れないと2になります。

　a += でaに次々に加算していきます。
　最初にa=2の場合、a=2+1=3が次の最小候補値aになります。
　次にa=3の場合、a=3+2=5というように、この後は3以上の奇数が順に最小値候補aになります。

４．判定対象値qが最小値候補aで割り切れるとき
　以下の設定をして、whileループの先頭に戻ります。
・p：最大素因数候補pは、割り切ることができたその割った値aです。
・b：最大素因数の最大値候補bは、割り切れた数の分だけ小さな値b/aで十分です。
・q：この割り切り判定の商q/aが次の判定対象値です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
6857


（追記）
・20120716
　ソースコード部分にSyntaxHighlighterを導入
　
　

プロジェクトオイラー 問２

プロジェクトオイラーの問題をpythonでやってみます。
出典：
英語サイトは、Project Euler でネット検索してください。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。


問２
フィボナッチ数列の項は前の2つの項の和である。 最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項の値が400万を超えない範囲で、偶数値の項の総和を求めよ。


注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の解答例は以下のとおりです。
－－－－－

L, t = [1, 2], 0
while L[1]<4000000:
	if not L[1]%2: t += L[1]
	L = [L[1], sum(L)]
print t

－－－－－

リストLは２つの要素を持つ配列で、L[0]に２つ前の値、L[1]に１つ前の値を格納しています。
変数ｔには合計する対象の値を累積していきます。
１行目でこのリストと変数の初期設定をしています。


%演算子は割り算の余りを返し、
２で割ったあまりが０か１かで奇数か偶数かを判定します。


論理判定では０がFalse、０以外がTrueと判定されます。
偶数の場合、余りは０なので、
L[1]%2がFalseのときに、変数tにL[1]を累積します。


累積し終わったら、次の準備として、
現在の１つ前の値と次のフィボナッチ数を、新たなL[0]、L[1]として格納し処理を続けます。


別解です。フィボナッチ数の計算部分を関数にしてみました。

def p(n):
	L = [1, 2]
	while L[1]<n:
		yield L[1]
		L = [L[1], sum(L)]
	
print sum([i for i in p(4000000) if not i%2])

－－－－－
関数pは、nまでのフィボナッチ数を小さい順に１つずつ返します。
returnでは値を１度返したら終わりですが、
yieldでは値を一つずつ返し、for文の中で値を取り出すことができます。

sum関数の中の配列[]の意味は以下のとおりです。
関数p(4000000)の１つずつの戻り値iのうち、偶数（not i%2）だけを格納した配列

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
4613732


（追記）
・20120716　ソースコード部分にSyntaxHighlighterを導入
・20130120　ネタバレ注意の追記など

プロジェクトオイラー 問１

プロジェクトオイラーの問題をpythonでやってみます。
出典：
英語サイトは、Project Euler でネット検索してください。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。


問１
10未満の自然数のうち、3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり、これらの合計は 23 になる。
同じようにして、1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。



注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の解答例は以下のとおりです。
－－－－－

def p(n,m): return sum([i for i in xrange(0, n, m)])
print p(1000, 3)+p(1000, 5)-p(1000, 15)

－－－－－

１行目の関数p(n,m)の意味は以下の通りです。

０からｎまでのｍ刻みの整数を発生させて、
そのすべての値を小さい順に要素に持つリストを作成し、
そのリスト内の値の合計値を返します。

つまり、「ｎ未満のｍの倍数の合計」を返します。

２行目で、1000未満の３の倍数の合計と、同じく５の倍数の合計を足し、
重複して足してしまった１５の倍数の合計を引いて、コンソールに表示します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
233168

（追記）
・20120716　ソースコード部分にSyntaxHighlighterを導入
・20130120　ネタバレ注意の追記など

京都市の通り名住所の案内文言（３） 方角情報複数

実際の京都市内の住所を例にして、通り名住所の案内文言をたどってみましょう。
前回の続きです。

京都市上京区西町　（３つの西町のうち、郵便番号「602-8374」の西町）

・一条通御前西入上る　（いちじょうどおり　おんまえ　にしいるあがる）

「通り名１＋通り名２＋方角文言」というのが京都市内の通り名住所の基本形ですが、この方角文言が「西入る」「上る」と２つあるパターンです。

このように方角文言が複数つながっている場合は、その順番に道案内の文章として解釈します。
つまりこの場合、西に進んでから北に進む、という意味です。
どのくらい西で、どのくらい北か、という距離情報は含まれていません。

なので、「一条通御前西入上る」という住所表記の意味は以下の通りです。

一条通という東西の通りに沿って、御前通り（おんまえどおり）という南北の通りとの交差点から西に進み、その後、北に進んだあたり。

・一条通御前西入上る西入（いちじょうどおり　おんまえ　にしいるあがるにしいる）
　これも上記と同様で、

一条通という東西の通りに沿って、御前通り（おんまえどおり）という南北の通りとの交差点から西に進み、その後、北に進み、さらに西に進んだあたり。

距離情報が無いと、これでたどりつけるのか？　と心配になりますが、
昔から使われてきた住所なので大丈夫なのでしょう。
もしたどり着けないのならば距離情報を付加しているはずです。
では、続きは次回。

京都市の通り名住所の案内文言（２） 距離情報

実際の京都市内の住所を例にして、通り名住所の案内文言をたどってみましょう。
前回の続きです。

京都市上京区西町　（３つの西町のうち、郵便番号「602-8374」の西町）

・一条通御前３丁目西入　（いちじょうどおり　おんまえ　３ちょうめ　にしいる）
　
「通り名１＋通り名２＋方角文言」という基本形に、「３丁目」が付いています。
この「数字＋丁目」は、昔の距離の単位としての「町」に由来しています。
ややこしいのですが、市区町村や大字などの領域名の接尾語の「町」ではなく、距離の単位の「町」です。
距離の単位の場合に限り、「丁」とも表記してきたものです。

（参考）
町(単位) (wikipedia)

１丁　＝　１０９．０９ｍ、「目」は序数（順番を表す数）の接尾語なので、
「３丁目」は、距離として、１丁の３つ目、現在の３００ｍくらいということです。

なので、「一条通御前３丁目西入」という住所表記の意味は以下の通りです。

一条通という東西の通りに沿って、御前通り（おんまえどおり）という南北の通りとの交差点から約３００ｍ西に進んだあたり。

では、続きは次回。

京都市の通り名住所の案内文言（１）

実際の京都市内の住所を例にして、通り名住所の案内文言をたどってみましょう。

例えば、京都市上京区西町。
上京区には郵便番号の異なる３つの西町がありますが、そのうちの１つ、
郵便番号「602-8374」の西町を例にします。

場所はここです。

大きな地図で見る

（郵便番号簿から抜粋）
西町（一条通御前西入、一条通紙屋川東入、一条通天神道西入、一条通御前３丁目西入、一条通御前西入上る、一条通御前西入上る西入、一条通御前西入２丁目、一条通御前西入２丁目上る、一条通御前西入２丁目下る、一条通御前西入２筋目下る、一条通御前西入３丁目、一条通御前西入３丁目上る、一条通御前西入３丁目下る、一条通御前西入３筋目、一条通御前西入下る、一条通御前西入下る３丁目、一条通紙屋川東入上る、一条通紙屋川東入下る、天神道一条上る、天神道一条下る、天神道仁和寺街道上る）の郵便番号

・一条通御前西入（いちじょうどおり　おんまえ　にしいる）
これは基本形。
一条通という東西の通りと、御前通り（おんまえどおり）という南北の通りの交差点から西側で、一条通りに面している辺り。
東西と南北のどちらの通りを先に言うかというと、建物の入り口が面している通りから始めるのが基本です。この例では、一条通りに面していることになります。
御前通りの「御前」とは何の前かと言うと、北野天満宮、天神様のまん前。
北野天満宮の正面の参道に通じていることが通り名の由来です。

・一条通紙屋川東入（いちじょうどおり　かみやがわ　ひがしいる）
これも基本形。
一条通という東西の通りと、紙屋川通り（かみやがわどおり）という南北の通りの交差点から東側で、一条通りに面している辺り。

・一条通天神道西入（いちじょうどおり　てんじんみち　にしいる）
これも基本形。
一条通という東西の通りと、天神道（てんじんみち）という南北の通りの交差点から西側で、一条通りに面している辺り。
通り名は必ずしも「通り」が付くとは限りません。この例のように「道」というものもあります。
天神道は北野天満宮の西側に接する通りです。

続きは次回。

python:ドキュメント作成ツール pydoc（２）

前回に続いてpydocです。（出力例）


１．使用準備
python2.1以降の標準ツールなので、わざわざインストールしなくても、python本体がインストールしてあれば使用可能です。


私はpydoc.pyを実行するバッチファイルを作成し、そのショートカットのアイコンをデスクトップに置いて、このアイコンにチェックしたいpythonファイルをドラッグ＆ドロップして実行しています。
ここではこの方法をご紹介します。


テキストファイルに以下の例のように書いて「pydoc.bat」として保存し、そのショートカットのアイコンをデスクトップに置きます。


@echo off
python.exe C:\Python26\Lib\pydoc.py -w %1
pause


マシンによって「pydoc.py」のあるフォルダが異なりますので、２行目には本当に「pydoc.py」があるパスを書きます。
「%1」はコマンドプロンプトでの第１引数のことで、ショートカットのアイコンにドラッグ＆ドロップしたファイルのフルパスがセットされます。
パラメータ「-w」でhtml版の説明書を出力することを指定します。


このようにして作成するドキュメントのファイル名は、ソースの拡張子「.py」を「.html」に変えたファイル名になります。


例）c:\python26\user\keisan.py
→　c:\python26\user\keisan.html


２．使用されるコメント文
pydocは、pythonソース、クラスや関数のヘッダ部分のコメントからhtml版使用手引きを作成します。取り出されるコメントは以下とおりです。


・ソースのヘッダ
　pythonソースで最初の命令後までの全コメント文が出力されます。


・importしているモジュール名


・クラスや関数のヘッダ
class文やdef文の行と、その前後の命令語との間にあるコメント文が使用されます。
命令語と命令語の間のコメントは出力されません。


・インヘリタンス（クラスの継承）をすると継承元クラスの説明も出力されます。


以上です。