Logicky BLOG

Logickyの開発ブログです

  • Javascript
  • Python
  • PHP
  • Go
  • OS・サーバ
  • 機械学習
  • つくったもの
  • 数学
  • アルゴリズム
  • Logicky

アルゴリズム

Python3 - 素因数分解

素因数分解 正の整数 n を素因数分解するための最も単純な方法は、2 から順に √n までの素数で割っていく方法である(Trial division(英語版))。しかし、n が大きくなると、この方法では困難である。 結果 [3, 79, 519507173] 参考:Python Finding Prime…

Python3 - 素数

エラトステネスの篩 エラトステネスの篩 結果 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,…

Python3 - アルゴリズム(重み付きグラフ・最短経路探索・ダイクストラのアルゴリズム)

参考:欲張り法 (greedy strategy) 重み付きグラフ networkxでつくった重みグラフ networkxのコードサンプル 上記は重み付きのグラフです。これはnetworkxで書きました。コードは下記です。 import numpy as np import matplotlib.pyplot as plt import netw…

Python3 - ヒープをnetworkxではなくgraphvizで書いてみる

networkxだときれいに表示できない。posに表示スタイルを設定するようですが、spring_layout、spectral_layout、shell_layoutとかありますが、全部キレイな木を表示してくれる感じじゃない。外部のdotファイルとかいうのを読み込むとできるようですが、graph…

Python3 - ヒープ

ヒープはノードに常に子供が2個あって、子供より親は小さい値を持ちます。ヒープは配列で表せます。配列の0番目は一番上の根ノードです。あとは、k番目のノードの子供は、左が2k+1、右が2k+2番目になります。挿入は最後に挿入して、親ノードと比較して必要に…

Python3 - アルゴリズム(グラフ)

参考:http://www.geocities.jp/m_Hiroi/light/pyalgo05.html グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行…

Python3 - NetworkXでグラフを表示する

https://networkx.github.io/ インストール https://github.com/networkx/networkx/ $ pip install networkx $ pip install decorator Decoratorというのも必要っぽい。両方ともすでに入ってた。 サンプルコード import networkx as nx G=nx.Graph() G.add_n…

Python3 - アルゴリズム(累乗)・計算量

累乗 pow0は遅いやつ。計算量はループをn回回すので、O(n)という。pow1は速いやつ。計算量はO(log n)らしい。 def pow0(x, n): value = 1 for i in range(n): value *= x return value def pow1(x, n): if n == 0: return 1 value = pow1(x, int(n / 2)) val…

ベルマン方程式

ベルマン方程式は、動的計画法(動的な最適化問題)の最適性の必要条件を表す方程式らしい。必要条件は、再帰を使って部分を解くことで全体が解ける状態にあることと、メモ化を使うことです。最適化問題とは、集合内のすべての数値を、ある関数にいれたとき…

Python3 - 動的計画法(フィボナッチ数列)

動的計画法は、分割統治法とメモ化を合わせた方法のことらしい。分割統治法は、問題を細分化して、細かい部分を順に解いていくことで全体を解明するようなことの総称らしい。 分割統治法は、コード的には下記のようになり、再帰することになる。 function co…

greedyアルゴリズム(貪欲法)

greedyアルゴリズムは、全部をN回試して、報酬の平均が最も高いやつを選択するというアルゴリズムです。 当たりか外れがでる機械が4個あって、どれが一番当たり率が高いか分からないのでgreedyアルゴリズムでやってみる想定にします。機械はa~dまであってそ…

codeIQをやってみた

The Essence of Programming 結城 浩さんからのアルゴリズムの問題をやってみました。簡単だと思ったのですが、アルゴリズムとかまだ勉強できてないので合ってるのか分かりません。ミスしてる可能性もあります。一応確認したら出来てる感じでしたが。ただ、…

  • Javascript
  • Python
  • PHP
  • Go
  • OS・サーバ
  • 機械学習
  • つくったもの
  • 数学
  • アルゴリズム
  • Logicky