Last active
January 2, 2016 21:49
-
-
Save inakagawa/8366435 to your computer and use it in GitHub Desktop.
『アルゴリズムを学ぼう』より、
a) (a ** k) % m を求める
b) vが配列vsに入っているかを検索する
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int powmod(int a, int k, int m){// a^k をm で割った余りを求める | |
long t=1; | |
for (int i=1; i<k; ++i) // loopして | |
t = (t * a) % m; | |
return (int)t; | |
} | |
int powmod(int a, int k, int m){// kが巨大な場合を考えて、再帰的にkを分割 | |
if (k == 0) | |
return 1; | |
long t = powmod(a, k/2, m);// 2つに分割した結果 | |
if (k % 2 == 1) | |
t = t * a % m; | |
return (int) t; | |
} | |
// -------- | |
// 配列から値を検索する | |
public boolean contains(int v, int[] vs){ | |
for (int i=0; i<vs.length; i++){ | |
if (vs[i] == v) return true; | |
} | |
return false; | |
} | |
// 二分探索 | |
// a.中央の数を見る | |
// b1.検索数vより小さいなら、左を検索 | |
// b2.検索数vより大きいなら、右を検索 | |
// b3.一致するなら、indexを返す | |
// 再帰使わなくても大丈夫ですよ? | |
public boolean contains(int v, int[] vs){ | |
if (vs.length == 0) return false; | |
int left = 0, right = vs.length; | |
while (left + 1 < right) { | |
//int mid = (left + right) / 2; | |
int mid = left + (right - left) / 2; | |
if (v < vs[mid]) | |
right = mid; | |
else | |
left = mid; | |
} | |
return v == vs[left]; //該当しなかったら、外れのleftが残っている | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
p35. 計算量の話。