2014 dxdy logo

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

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




 
 Простая задача о произведении элементов
Сообщение30.06.2010, 13:40 
Аватара пользователя
Привет.

Я знаю решение этой задачи, но интересно узнать как и за какое время решите Вы.

Задача:

Неформальное описание:

Есть массив $In[N]$ содержащий $N$ элементов (от $0$ до $N -1$). Нужно составить функцию, которая получая на вход массив $In[N]$ на выходе даёт $Out[N]$, где каждый элемент массива $Out[N]$ будет равен произведению всех элементов $In[N]$ кроме текущего элемента. Например, $Out[0]$ будет содержать произведение от $In[1]$ до $In[N-1]$, а $Out[1]$ будет содержать произведение от элементов $In[0]$ и от $In[2]$ до $In[N-1]$.

Формальное описание:

$In = \left\{ In_i | \forall i : In_i \in \mathbb{Z} \right\}$

$Out = \left\{ Out_i | \forall i : Out_i \in \mathbb{Z} \wedge Out_i = \prod_{\forall i : i \neq j, In_i, Out_j}In_i\right\}$

Нужен алгоритм функции $f : In \to Out$

В решении не должен использоваться оператор деления и время выполнения должно быть $O(n)$.

 
 
 
 Re: Простая задача о произведении элементов
Сообщение30.06.2010, 14:02 
цикл(цикл_конец,цикл_начало)

 
 
 
 Re: Простая задача о произведении элементов
Сообщение30.06.2010, 14:13 
Аватара пользователя
master в сообщении #336418 писал(а):
цикл(цикл_конец,цикл_начало)


Если я правильно понял, то Ваше решение требует $O(n^2)$ (то есть $N$ раз обходится $N - 1$ элементов), а нужно $O(n)$.

P.S. Решение я знаю, просто интересно посмотреть на другие возможные решения.

 
 
 
 Re: Простая задача о произведении элементов
Сообщение30.06.2010, 15:35 
Аватара пользователя
1. Составляем вспомогательный массив $a$. $a[i]$ - произведение всех $in[i]$ от $0$ до $i - 1$ (или $1$, если таковых нет).
2. Составляем вспомогательный массив $b$. $b[i]$ - произведение всех $in[i]$ от $i + 1$ до $N - 1$ (или $1$, если таковых нет).
3. Цикл по $i$. $out[i] = a[i] * b[i]$.

 
 
 
 Re: Простая задача о произведении элементов
Сообщение30.06.2010, 15:50 
Аватара пользователя
r-aax

Да, это то самое решение.

 
 
 
 Re: Простая задача о произведении элементов
Сообщение01.07.2010, 09:11 
а по моему в конечном итоги то же самое

 
 
 
 Re: Простая задача о произведении элементов
Сообщение01.07.2010, 11:42 
Быть может сначала перемножить все элементы масива IN, а потом полученный результат делить на соответствующий элемент.

 
 
 
 Re: Простая задача о произведении элементов
Сообщение01.07.2010, 14:35 
Аватара пользователя
ГАЗ-67 писал(а):
Быть может сначала перемножить все элементы масива IN, а потом полученный результат делить на соответствующий элемент.
creative в сообщении #336410 писал(а):
В решении не должен использоваться оператор деления...

 
 
 
 Re: Простая задача о произведении элементов
Сообщение01.07.2010, 19:56 
Аватара пользователя
С императивным решением всё ясно, а как на счёт функционального.

Я только-только начал изучать Haskell, интересно как будет выглядеть решение на нём.

 
 
 
 Re: Простая задача о произведении элементов
Сообщение04.07.2010, 04:26 
2creative
Цитата:
начал изучать Haskell, интересно как будет выглядеть решение на нём.

Если с делением, то можно наверное написать так:
Используется синтаксис Haskell
    show (map (\x -> product array / x) array)
 

Увы, не работает -- что-то не то с делением (если заменить на умножение, то компилируется успешно).

Алгоритм r-aax'а может выглядеть так:
Используется синтаксис Haskell
    my_product _ [] = []
    my_product factor (x:xs) = factor : my_product (factor*x) xs

    a = my_product 1 array
    b = reverse (my_product 1 (reverse array))

    show (map (\(x, y) -> x*y) (zip a b))
 

 
 
 
 Re: Простая задача о произведении элементов
Сообщение04.07.2010, 11:34 
Ага, пример с делением можно переписать так:
Используется синтаксис Haskell
    show $ map (div $ product array) array
 


А лямбду из второго примера можно заменить более лаконичным uncurry (*).

 
 
 
 Re: Простая задача о произведении элементов
Сообщение04.07.2010, 20:33 
Аватара пользователя
Используется синтаксис Haskell
import Data.List

test xs = zipWith (*) (map product $ inits xs) (map product $ tail $ tails xs)

 
 
 
 Re: Простая задача о произведении элементов
Сообщение05.07.2010, 00:51 
Здорово. Я про inits/tails и вовсе не знал. :)

 
 
 
 Re: Простая задача о произведении элементов
Сообщение06.07.2010, 15:36 
Аватара пользователя
Ну, надо сказать, что Ваш my_product - он точно линеен по времени и памяти, а мое не факт, что соптимизируется.

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


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