2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Упростить выражение (быстро вычислить, для программистов)
Сообщение08.10.2011, 16:19 
Программистам дали сегодня задачу быстро вычислить выражение
$$
S(n,m,x)=\sum_{k_1+k_2+\cdots+k_m=n} \sin(k_1 x) \sin(k_2 x)\cdots \sin(k_m x), k_i \geq 0.
$$
Скорее всего ето выражение допускает существенное упрощение, но пока не ясно какое. Наверное в Кнута есть решение.

 
 
 
 Re: Упростить выражение
Сообщение08.10.2011, 16:41 
Если программистам, то скорее всего, решать надо без упрощения, но с применением динамического программирования. Каковы ограничения на n и m?

 
 
 
 Re: Упростить выражение
Сообщение08.10.2011, 16:55 
Ограничения такие
$$
1 \leq n  \leq 30,\\
1 \leq  m  \leq 1000000000 (10^9),\\
0  \leq X \leq 6.28 < 2\pi
$$

 
 
 
 Re: Упростить выражение
Сообщение08.10.2011, 17:08 
Что вы можете сказать про сумму если $n < m$?

 
 
 
 Re: Упростить выражение
Сообщение08.10.2011, 17:22 
venco в сообщении #490667 писал(а):
Что вы можете сказать про сумму если $n < m$?


Она равна нулю, поскольку среди $k_i$ обязательно присутствуют нули и тогда соответствующий синус также равен нулю.

 
 
 
 Re: Упростить выражение
Сообщение08.10.2011, 17:27 
Ну вот, остался только случай $n=m$. А там совсем просто.
Странно, конечно, ведь самый интересный случай - $n>m$. Вы не перепутали условия?

-- Сб окт 08, 2011 10:28:24 --

Ааа! Вы уже исправили условия. Так интереснее.

-- Сб окт 08, 2011 10:29:22 --

Ну а теперь применяйте ДП. Сложность получится $n^2$.

 
 
 
 Re: Упростить выражение
Сообщение08.10.2011, 17:50 
спасибо

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group