プログラミングのお題スレ Part21

**デフォルトの名無しさん** · 2022/11/13(日) 19:00:36.84

プログラミングのお題スレです。

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

※前スレ
プログラミングのお題スレ Part20
https://mevius.5ch.net/test/read.cgi/tech/1624028577/

**デフォルトの名無しさん** · 2023/06/20(火) 15:17:12.61

お題　Fourier 変換

長さが2べきの複素数の列が与えられます
(複素数はDouble型２つのタプルで表現するとする)
そのFourier変換である同じ長さの列を計算する関数を実現して下さい
またそれを利用して同じ長さの畳み込み積を計算する関数を実現して下さい

(但し書き)
長さNの数列(aₙ)のFourier変換F(aₙ)とは第k項が
Σ[n=0,N-1] (cos(2πkn/N) + isin(2πkn/N))aₙ
である列を与える変換とする
その逆変換F⁻¹(aₙ)は第k項が
1/NΣ[n=0,N-1] (cos(-2πkn/N) + isin(-2πkn/N))aₙ
で与えられる変換である
数列(aₙ)と(bₙ)の畳み込み積とは
F⁻¹( F(aₙ) × F(bₙ) )
で与えられる積である、ただしこの×は各項毎の積で与えられる列である

**デフォルトの名無しさん** · 2023/06/20(火) 15:17:18.47

(例)
・F (a,b,c,d) = (a+b+c+d, a+bi-c-di,a-b+c-d,a-bi-c+di)
・F(1,2,3,0,0,0,0,0) =
6.0 :+ 0.0
2.4142135623730954 :+ 4.414213562373095
(-1.9999999999999996) :+ 2.0
(-0.4142135623730949) :+ (-1.5857864376269046)
2.0 :+ 0.0
(-0.4142135623730949) :+ 1.585786437626905
(-2.0000000000000004) :+ (-2.0)
2.4142135623730945 :+ (-4.414213562373096)
・1,2,3,0,0,0,0,0と4,5,6,0,0,0,0,0の畳み込み積
=
3.999999999999999 :+ 2.6645352591003757e-15
12.999999999999998 :+ (-1.6730659520119792e-15)
28.0 :+ (-5.773159728050814e-15)
27.0 :+ (-5.432361405589022e-15)
18.0 :+ (-8.881784197001252e-16)
1.7763568394002505e-15 :+ 3.656004566188772e-15
1.7763568394002505e-15 :+ 3.9968028886505635e-15
0.0 :+ 3.4494227914122297e-15