Простая задача о произведении элементов

[creative]

Привет.

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

Задача:

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

Есть массив $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)$.

[master]

цикл(цикл_конец,цикл_начало)

[creative]

master в сообщении #336418 писал(а):

цикл(цикл_конец,цикл_начало)

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

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

[r-aax]

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]$.

[creative]

r-aax

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

[master]

а по моему в конечном итоги то же самое

[ГАЗ-67]

Быть может сначала перемножить все элементы масива IN, а потом полученный результат делить на соответствующий элемент.

[worm2]

ГАЗ-67 писал(а):

Быть может сначала перемножить все элементы масива IN, а потом полученный результат делить на соответствующий элемент.

creative в сообщении #336410 писал(а):

В решении не должен использоваться оператор деления...

[creative]

С императивным решением всё ясно, а как на счёт функционального.

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

[Circiter]

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))
 

[Circiter]

Ага, пример с делением можно переписать так:

Используется синтаксис Haskell

    show $ map (div $ product array) array
 

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

[Xaositect]

Используется синтаксис Haskell

import Data.List

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

[Circiter]

Здорово. Я про inits/tails и вовсе не знал. :)

[Xaositect]

Ну, надо сказать, что Ваш my_product - он точно линеен по времени и памяти, а мое не факт, что соптимизируется.