「写像12相」で典型的な数え上げ問題のパターン総整理
条件を満たすものが何通りあるか数える問題、すなわち数え上げ問題には様々なものがありますが、「\(n\) 個の玉を \(x\) 個の箱に分ける方法は何通りか」などといった、典型的なものはある程度パターン化して解くことができます。 ...
自然数nをk個の0以上の整数に分割する方法の総数を求めるアルゴリズム
以下の2つを混同しそうですが、ここでは \(p_{\leq k}(n)\) を求めることを考えます。
\(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できな ...自然数nをk個の1以上の整数に分割する方法の総数を求めるアルゴリズム
以下の2つを混同しそうですが、ここでは \(p_k(n)\) を求めることを考えます。
\(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) ...ベル数を求めるアルゴリズム：第2種スターリング数の和を効率的に計算する
ベル数は「写像12相」と呼ばれるものを通して学ぶと、他の数え上げ問題との関わりが分かり全体像がスッキリします。ぜひ確認してみることをおすすめします。
「写像12相」で典型的な数え上げ問題のパターン総整理
...
第2種スターリング数を求めるアルゴリズム
第2種スターリング数は「写像12相」と呼ばれるものを通して学ぶと、他の数え上げ問題との関わりが分かり全体像がスッキリします。ぜひ確認してみることをおすすめします。
「写像12相」で典型的な数え上げ問題のパターン総整理
平方数の判定をするアルゴリズム
Nが自然数の2乗で表現できるとき、平方数と言います。
平方数の例4 (= 2×2)9 (= 3×3)
16 (= 4×4)
25 (= 5×5)
アルゴリズム
以下の方法以外にも色々な求め方 ...
Nの約数の個数を求めるアルゴリズム
素因数分解を用いることで、約数の個数を簡単に求めることができます。
アルゴリズムNの約数の個数：
N を素因数分解するそれぞれの指数に1を足す
「2.」で得られたものを全てかけ合わせる
パスカルの三角形による二項係数(nCk)の計算
以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)
二項係数(nCk)の偶奇判定のアルゴリズム
Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。
アルゴリズムLucasの定理をそのまま利用したアルゴリズム：
\({}_{n_i}\mathrm ...二項係数(nCk)を素数(p)で割った余りの計算（Lucas の定理）
Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さい場合は十分高速です。
Lucas の定理任 ...