Download presentation
Presentation is loading. Please wait.
1
11621 : Small Factors ★★☆☆☆ 題組：Problem Set Archive with Online Judge
解題者：陳鵬宇 解題日期：2018年3月9日 題意：Fast Fourier Transform algorithm (FFT)是一個常見用於離散傅立葉轉換(DFT)的演算法，其中又以Radix-2 FFT為最廣泛使用，但其有一缺點為樣本數(k)可能超過至實際訊號數(n)的兩倍，意味著有近100%的overload，所以另一演算法Radix-2/3 FFT algorithm使用2與3為基數，欲找出最接近的樣本數使得{k = 2^i · 3^ j , i, j 屬於N}且k>=n，此題目的即為為每一個input找出相對應的k值。
2
題意範例： 100 108 //(2^2*3^3) 108 108 //(2^2*3^3) 1000 1024 //(2^10) 1025 1152 //(2^7*3^3)
//(2^10*3^1) 解法：先分別計算i,j， i與j為大於或等於input的最小2與3的指數，再以i,j最為雙重for迴圈的極值條件找出大於或等於input的最小數，然後記錄下來並印出即可。 解法範例：無 討論：無
Similar presentations
