3分プログラミング

二分探索 バイナリサーチ

簡単でかつ効果が高いのでよく使うサーチ. 意外と境界条件でバグりがち.味噌は,右側を配列の外において置く. #include<iostream> #include<vector> using namespace std; int main() { int d, n; cin >> d; cin >> n; vector<int> v(n); for (int i=0; i<n; ++i) cin>>v[i]; int l=0, r=v.siz</n;></int></vector></iostream>…

線形探索と番兵アルゴリズム

番兵アルゴリズムはただの書き方の問題だと思ってたけど,高速化のテクニックだった,という話. forでvectorの要素を回す時に,毎回比較演算が行われるけど,それが勿体無いという場合に,絶対に止まるよに番兵を置いておいて無限ループで回すというのが番…

Euler Projecect 1

100以下の整数のうち,3か5の倍数の和. Ruby 最もシンプルにただ全部舐めていくだけ. sum = 0 100.times do |i| if i%3==0 or i%5==0 sum += i end end p sum

ランダムウォーク

お題 X軸上をランダムに動く点の軌跡を求める.1ステップで±1か,動かないか. python 一歩ずつやってもいいけど,ガバッと乱数作ってnumpyのcumsumを使う方法でもいい. import numpy as np move = np.random.randint(-1,2,100) # generate 100 random in…

ディレクトリ内のあるファイル群に処理を適用する

お題 あるディレクトリ配下のあるファイル群(例えば拡張子がrbのファイルに対してなど)に何か処理を適用する場合.スクリプトを書くときに良くあるのかな. Ruby Dir::glob("/home/nobunaga/codes/*.rb").each do |f| func(f) end python pythonもほぼ同様…

順列の作成

お題 N個の配列からM個の並びを全て列挙する.所謂縦列. python itertoolsを使う.自分で何もやっていないけど,pythonを使う意味はそこだから別に気にしない. import itertools if __name__ == "__main__": a = [0,1,2,3,4,5,6,7,8,9] for p in itertools…

ルーレット選択

お題 GAとかで使うルーレット選択を書く.いわゆる重み付きランダム選択.重みWがx:y:z=1:2:3の場合,x=1/6, y=2/6, z=3/6の確率で生成する.色んな言語で累積和,2分探索,乱数を扱う良い練習問題なのかな. python やり方としては重みの累積和の配列を作…