テクめも

プログラミング関連のちょっとしたTipsなどを書いています。

アルゴリズム

Pythonで優先度付きキューを使う

Pythonでの優先度付きキューはheapqを使うとできます。 import heapq 最小ヒープ はじめに、リストをキューに優先度付きキューに変換します。 que = [3, 1, 5, 2] heapq.heapify(que) 先頭に最小値がきます。(先頭以外はソートされているわけではありません…

Pythonでn番目のフィボナッチ数を求める

フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13, ... と続く数列です。 このn番目の値をPythonで求めるには以下のようなにすれば良いです。 単純な方法 def fib(n): if n < 2: return n else: return fib(n - 2) + fib(n - 1) キャッシュを使う方法 標準モジュ…