うみねこまつり

めっちゃなきごえがうるさい

f:id:kabegiwakun:20210503175239j:image

2021-05-02

Detroit Become Human

やった。
おそらくなかなかのバッドエンド。

2021-03-23

シンエヴァンゲリオンみた

おわりましたね

序盤の発電するやつすき

2021-03-21

幅優先探索

以下を実装した。
ja.wikipedia.org

これ

github.com

2021-03-16

再帰２分探索

def binary_search(max_index, min_index):
  mid_index = (max_index + min_index) // 2
  if array[mid_index] == value:
    return(mid_index)
  return(binary_search(mid_index - 1, min_index) \
    if value < array[mid_index] else binary_search(max_index, mid_index + 1))

if __name__ == '__main__':
  array = [1,3,5,11,12,13,17,22,25,28,]
  value = 28
  min_index = 0
  max_index = len(array) - 1

  print(binary_search(max_index,min_index))

2021-03-15

再帰での配列の要素数のカウント

def count_num(num_list):
  if len(num_list) == 0:
    return(0)
  else:
    return(1 + count_num(num_list[1:]))

print(count_num([1,2,3,4,]))

2021-03-14

選択ソート

github.com

2021-03-13

ある名前があり、その人の電話番号を電話帳で調べるときの計算量

最近アルゴリズムの本を読んでいて、その中で以下の問題があった。

ある名前があり、その人の電話番号を電話帳で調べたい。このときの計算量はなにか。

答えはO(log n)

ただ、それの解説が書いていなく、しばらく悩んでいた。いろいろ考えて、ようやく答えにたどり着いた。たぶん。

なぜ計算量がO(log n)になるのか？

昔々の電話帳というのは、五十音順でいろんな人の電話番号が掲載されていた。
たとえば夏本さんの電話番号を探そうと思ったら、とりあえず電話帳の真ん中らへんを開いてみる。そしたら田中さんの電話番号がのっていた。じゃあ、「な」から始まる人はもう少し先の方のページなんだなぁと思って、更に先の方のページを適当に開く、そしたら布川さんの電話番号がのっていたので、少し行き過ぎてしまったなということですこしページを戻る。みたいな探し方をすることになるはず。

これが二分探索。ということでO(log n) だと思う。

電話帳というものがあまり想像できず、苦労した。
紙の辞書から特定の単語を探す、とかならかんたんに答えにたどり着いたかもしれない。

これ