2014 dxdy logo

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

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




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


01/04/10
910
Привет.

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

Задача:

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

Есть массив $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 
Заблокирован


12/08/09

1284
Самодуровка
цикл(цикл_конец,цикл_начало)

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


01/04/10
910
master в сообщении #336418 писал(а):
цикл(цикл_конец,цикл_начало)


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

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

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


23/05/10
145
Москва
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 
Аватара пользователя


01/04/10
910
r-aax

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

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


12/08/09

1284
Самодуровка
а по моему в конечном итоги то же самое

 Профиль  
                  
 
 Re: Простая задача о произведении элементов
Сообщение01.07.2010, 11:42 


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

 Профиль  
                  
 
 Re: Простая задача о произведении элементов
Сообщение01.07.2010, 14:35 
Заслуженный участник
Аватара пользователя


01/08/06
3116
Уфа
ГАЗ-67 писал(а):
Быть может сначала перемножить все элементы масива IN, а потом полученный результат делить на соответствующий элемент.
creative в сообщении #336410 писал(а):
В решении не должен использоваться оператор деления...

 Профиль  
                  
 
 Re: Простая задача о произведении элементов
Сообщение01.07.2010, 19:56 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Простая задача о произведении элементов
Сообщение04.07.2010, 04:26 
Заслуженный участник


26/07/09
1559
Алматы
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 
Заслуженный участник


26/07/09
1559
Алматы
Ага, пример с делением можно переписать так:
Используется синтаксис Haskell
    show $ map (div $ product array) array
 


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

 Профиль  
                  
 
 Re: Простая задача о произведении элементов
Сообщение04.07.2010, 20:33 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Используется синтаксис Haskell
import Data.List

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

 Профиль  
                  
 
 Re: Простая задача о произведении элементов
Сообщение05.07.2010, 00:51 
Заслуженный участник


26/07/09
1559
Алматы
Здорово. Я про inits/tails и вовсе не знал. :)

 Профиль  
                  
 
 Re: Простая задача о произведении элементов
Сообщение06.07.2010, 15:36 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group