【Python】HDDに眠る大量の計算プログラム群を晒す
気が向いたら書くというテンションで適当に書き連ねた計算プログラムが結構な量あるので晒します。
モンテカルロ法で円周率計算
pi.py
import numpy as np
rng,p,n=np.random.default_rng(),0,100000
for i in range(1,n+1):
if rng.random()**2+rng.random()**2<=1:p+=1
if i!=0 and i%(n//10)==0:print(p*4/i)
たぶん、他の全てを気にせずとにかく行数を減らして書いてみた的なやつ。可読性が終わっている。
モンティ・ホール問題の検証
monthi.py
import random
s=0
ss=0
N=100000
for i in range(N):
r=random.randint(0,2)
q=random.randint(0,2)
t=q
while t==r or t==q:
t=random.randint(0,2)
if q==r:s+=1
qq=q
while q==qq or q==t:
q=random.randint(0,2)
if q==r:ss+=1
print(s/N)
print(ss/N)
即席で書いたやつ。変数名がこれ以上ないくらいダメ。今となってはコメントアウトをつける気にもならない……。
まあ、出力から3分の2になるらしいことはわかる。
エラトステネスのふるい
sosu.py
def sosu(n):
num=[0 for i in range(n+1)]
for i in range(2,n+1):
num[i]=1
for i in range(2,n+1):
if num[i]==1:
p=i*2
while p<=n:
num[p]=0
p+=i
return num
昔は暇になるたびに書いていた気がする。理屈は簡単なのに、それなりに早い。実用性はともかく、素数判定法の中では一番好きかもしれない。
ダイクストラ法
djik.py
#初期化
V=["a","b","c","d","e","s","t"] #頂点集合
d={} #始点からの最短距離
prev={} #最短経路を辿る時の前の頂点
for i in V:
d[i]=100 #最短経路には暫定で100を代入
prev[i]=None #最短経路を辿る時の前の頂点はすべてなし
d["s"]=0 #始点の最短距離は0
Q=V #Qに頂点集合をコピー
length={ #辺の情報
"a":{"b":6,"e":6,"s":3},
"b":{"a":6,"c":4,"t":3},
"c":{"b":4,"d":3,"t":1},
"d":{"c":3,"e":2,"s":4},
"e":{"a":6,"d":2,"t":5},
"s":{"a":3,"d":4},
"t":{"b":3,"c":1,"e":5}
}
#本計算
while(len(Q)!=0): #Qが空でなくなるまで繰り返し
u=Q[0] #始点からの最短経路が最小であるような集合Q内の点uを得る
for i in Q:
if d[u]>d[i]:
u=i
Q.remove(u) #Qからuを削除
for v in length[u].keys(): #uから辺がつながっているそれぞれの頂点vに対して
if d[v]>d[u]+length[u][v] : #vの最短経路がuの最短経路+uとvを繋ぐ辺の長さより大きいなら
d[v]=d[u]+length[u][v] #vの最短経路はuの最短経路+uとvを繋ぐ辺の長さ
prev[v]=u #vの最短経路を辿る時の前の頂点はu
#表示
print("t < ",end="")
e="t"
while e!="s":
e=prev[e]
print("%c < "%(e),end="")
print("\n最短経路の長さは"+str(d["t"]))
wikiだかなんだかをみて疑似コードをPythonに直した記憶。表示部分が下手。
自分がジェネレータではなく書式指定子を使うという時期が存在したことに驚いた。ジェネレータの方がどう考えても書きやすいし見やすい。
ハノイの塔
hanoi.py
def hanoi(n,from_,middle,to):
if n==0:return None
hanoi(n-1,from_,to,middle)
print(f"{from_}:#{n} -> {to}")
hanoi(n-1,middle,from_,to)
return None
再帰が苦手なのを克服するために書いたテストコードその1。from_の命名がちょっと気持ち悪い。
マージソート
merge.py
def merge(A):
if len(A)<=1:
return A
B=A[:len(A)//2]
C=A[len(A)//2:]
B=merge(B)
C=merge(C)
n,i,j=0,0,0
while j<len(C) and i<len(B):
if B[i]<=C[j]:
A[n]=B[i]
i+=1
else:
A[n]=C[j]
j+=1
n+=1
while i<len(B):
A[n]=B[i]
i+=1
n+=1
while j<len(C):
A[n]=C[j]
j+=1
n+=1
return A
再帰が苦手なのを(略)その2。ドツボにハマって数時間悩んだ。クイックソートより難しいんですけど……。
リストを三つ作る関数ブロックが再帰するのでメモリ効率は多分最悪。再帰にもっと慣れたらより良いものがかけるとは思うが、いつになることやら。
クイックソート
quick.py
def quick(A):
if len(A)<=1:
return A
p=A[0]
left=[i for i in A if i<p]
middle=[i for i in A if i==p]
right=[i for i in A if i>p]
return quick(left)+middle+quick(right)
再帰が(略)その3。本当はリストの連結は重いから使いたくないが、この書き方が一番シンプルだから仕方なく使った。連結処理とかメモリ解放系の処理を排除したアルゴリズムをインプレースとか言うらしい。