Главное меню
Мы солидарны с Украиной. Узнайте здесь, как можно поддержать Украину.

Ответ

Обратите внимание: данное сообщение не будет отображаться, пока модератор не одобрит его.
Ограничения: максимум вложений в сообщении — 3 (3 осталось), максимальный размер всех файлов — 300 КБ, максимальный размер одного файла — 100 КБ
Снимите пометку с вложений, которые необходимо удалить
Перетащите файлы сюда или используйте кнопку для добавления файлов
(Удалить вложения)
Вложения и другие параметры
Проверка:
Оставьте это поле пустым:
Наберите символы, которые изображены на картинке
Прослушать / Запросить другое изображение

Наберите символы, которые изображены на картинке:

√36:
ALT+S — отправить
ALT+P — предварительный просмотр

Сообщения в этой теме

Автор RawonaM
 - апреля 18, 2012, 10:35
J'ai réussi.

Код Выделить
from numpy import *

poli1 = [1, 2]
poli2 = [3, 4]

f1 = fft.fft(poli1,  len(poli1)*2,  -1)
f2 = fft.fft(poli2,  len(poli2)*2,  -1)

result = []

for i in range(len(f1)):
    result.append(f1[i]*f2[i])

print fft.ifft(result)


Цитата: output[  3.+0.j  10.+0.j   8.+0.j   0.+0.j]

Et c'est vrai que (1+2x)(3+4x)=3+10x+8x2+0
Автор RawonaM
 - декабря 30, 2011, 23:57
Да, это оно, только дискретное.
Чтобы перемножить два многочлена нужно произвести конволюцию коэффициентов. Допустим есть два многочлена размером n, если производить конволюцию в лоб, то нужно произвести n2 умножений.
Преобразование Фурье позволяет быстро вычислить произвольное количество точек на функции. Находим 2n точек у обоих многочленов, перемножаем их по одному, потом из новых 2n точек делаем обратное преобразование Фурье и получаем результат - помножение двух многочленов.
Собственно получаем результат конволюции, а это всего лишь частный случай.
Автор Квас
 - декабря 30, 2011, 23:49
Цитата: RawonaM от декабря 30, 2011, 23:24
А вы знаете про преобразование Фурье? :)

[tex]F[\varphi](\xi) = \int \varphi(x) e^{i(\xi, x)} dx[/tex]

8-)

Правда, эта штука у меня ассоциируется с матфизикой, и не знаю, чем может облегчить перемножение многочленов тот факт, что преобразование Фурье переводит свёртку в произведение. Поэтому я подумал, что речь может идти о другом преобразовании.
Автор RawonaM
 - декабря 30, 2011, 23:24
А вы знаете про преобразование Фурье? :)
Автор RawonaM
 - декабря 30, 2011, 23:24
Цитата: Квас от декабря 30, 2011, 23:05
Не нашёл в справке, что такое fft и ifft.
http://docs.scipy.org/doc/numpy/reference/routines.fft.html

Нужно поставить пакет numpy.  В Убунту это просто, на винде нужно колдовать.
Ну или самому написать fft (Fast Fourier Transform, там всего 10 строк кода).
Автор Квас
 - декабря 30, 2011, 23:05
Питон! :=

Не нашёл в справке, что такое fft и ifft.
Автор RawonaM
 - декабря 30, 2011, 22:15
Не получается.
Вот код на питоне:

Код Выделить
a = [1, 2, 3]
b = [1, 2, 3]

poli1 = fft(a,  2*len(a))
poli2 = fft(b,  2*len(b))

poli3 = []

for i in range(0, len(poli1)):
    poli3.append(poli1[i] * poli2[i])
   
print poli3
print ifft(poli3, (len(a)-1)*(len(b)-1))


Вот вывод:
Цитировать[(36+0j), (-18.499999999999993-4.3301270189221563j), (1.4999999999999993-2.5980762113533169j), (4.0000000000000018-1.352477158045318e-14j), (1.4999999999999993+2.5980762113533169j), (-18.500000000000014+4.3301270189222274j)]

[  5.75000000-1.73205081j   9.70753175-4.97548095j  13.00000000+0.4330127j
   7.54246825+6.27451905j]

Что я делаю не так?