fft(s1s2s3s4 . . .) = fft(s1s3s5 . . .) + fft(s2s4s6 . . .),
pri čemer + pomeni navadno stikanje nizov. Zgornja rekurzivna definicija velja za vse vhodne nize dolžine 2 ali več; za vhodne nize dolžine 1 pa nimamo česa premešati in definiramo kar fft(s1) = s1.
Primer 1:
Koda: Izberi vse
fft(sadje) = fft(sde) + fft(aj)
= (fft(se) + fft(d)) + (fft(a) + fft(j))
= ((fft(s)+fft(e))+d)+(a+j)
= sedaj
Primer 2 (izpeljavo preskočimo):
Koda: Izberi vse
fft(kokain_crv) = krik_ovnac
Dokaži Sovi, da fft ni prav dobra šifra. Napiši program, ki dešifrira poljuben niz, zašifriran s fft.
Vhodna datoteka: v prvi vrstici je število n (1 ≤ n ≤ 100), število šifriranih spo- ročil. Vsaka od naslednjih n vrstic vsebuje po eno šifrirano sporočilo yi, sestavljeno izključno iz malih črk angleške abecede ter podčrtajev. Sporočila ne bodo daljša od 1024 znakov. V 30 % testnih primerov bodo vse dolžine sporočil potence števila 2.
Izhodna datoteka: vanjo po vrsti izpiši vseh n izvornih sporočil xi, vsako v svoji vrstici. To, da je xi „izvorno sporočilo“, pomeni, da velja zveza fft(xi) = yi.
Primer vhodne datoteke:
Koda: Izberi vse
9
sedaj
krik_ovnac
tutla_orask
avion_desno
desna_avtor
enak_nitro
lesk_oktav
uhan_serje
star_mivka
Pripadajoča izhodna datoteka:
Koda: Izberi vse
sadje
kokain_crv
tolsta_kura
adonis_oven
danost_reva
enkrat_oni
lokast_vek
usnjar_ehe
smrkav_ati