Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

NTT(数論変換)を使って2つの多項式の積を求めるプログラム

Python

「『アルゴリズムC 第3巻』の「41 高速フーリエ変換」をPythonで」、「FFTを使って2つの多項式の積を求めるプログラム」に引き続き、NTT(数論変換)を使って2つの多項式の積を求めるプログラムを作ってみました。

2つの多項式の積を求めるプログラム(convolution_ntt.py)

実行結果

p(x) = 1 + x + x^{2} , q(x) = 2 - x + x^{2} のとき、 r(x) = p(x) * q(x)を求めてみます。 実行結果は以下の通りです。当然ですが、FFTを使ったものと同じ結果となっています。

% python convolution_ntt.py
1 1 1
2 -1 1
2
1
2
0
1

参考

FFTを使って2つの多項式の積を求めるプログラム

Python

昨日に引き続き、FFTを使って2つの多項式の積を求めるプログラムを作ってみました。

2つの多項式の積を求めるプログラム(convolution_fft.py)

実行結果

p(x) = 1 + x + x^{2} , q(x) = 2 - x + x^{2} のとき、 r(x) = p(x) * q(x)を求めてみます。 実行結果は以下の通りです。少し見にくいですが、 r(x) = 2 + x + 2x^{2} + x^{4} となっています。

% python convolution_fft.py
1 1 1
2 -1 1
2
1
2
0
1

参考

『アルゴリズムC 第3巻』の「41 高速フーリエ変換」をPythonで

Python

『アルゴリズムC 第3巻』の第41章「高速フーリエ変換」で紹介されているアルゴリズムをPythonで作ってみました。

2つの多項式の積を求めるプログラム(41_FFT.py)

p(x) = 1 + x + x^{2} , q(x) = 2 - x + x^{2} のとき、 r(x) = p(x) * q(x)を求めてみます。

実行結果

実行結果は以下の通りです。少し見にくいですが、 r(x) = 2 + x + 2x^{2} + x^{4} となっています。

% python 41_FFT.py
2
1
2
0
1

関連

アルゴリズムC 第3巻

アルゴリズムC 第3巻

Amazon

令和6年度春期 応用情報午後問3

情報処理技術者試験 Python

令和6年度春期 応用情報技術者試験(AP)の午後問題3は、

に関する問題でした。

最短距離の算出プログラム(r06h_ap_pm3_1.py)

まずは、問題文中の図2で紹介されている最短距離の算出プログラムを作ってみました。

実行結果

% python r06h_ap_pm3_1.py
17

最短経路も出力するプログラム(r06h_ap_pm3_2.py)

最短距離の算出プログラムに最短経路も出力する機能を付け加えたものです。(図3,図4)

実行結果

% python r06h_ap_pm3_2.py
4
2
1
0
17

優先度付きキューを用いて性能を改善したプログラム(r06h_ap_pm3_3.py)

ノードの個数が少ないと効率の悪さを実感することはありませんが、問題文で紹介されているアルゴリズムは、更新起点ノードを求める処理の効率がよくありません。そこで、優先度付きキューを用いて書き換えてみました。

実行結果

% python r06h_ap_pm3_3.py
4
2
1
0
17

関連