2016-01-01から1ヶ月間の記事一覧

Berlekamp-Massey のアルゴリズム

線形の漸化式(整数係数で最高次の係数は 1 とする)に従う数列が与えられたとき、もとの漸化式の特性方程式を見つける方法があるというのを某所で知った。 例えば、フィボナッチ数列の何項か(例えば 1, 2, 3, 5, 8)が与えられたとき、特性方程式 を求めるとか…