2014 dxdy logo

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

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





Начать новую тему Ответить на тему
 
 Работа с массивами.
Сообщение18.12.2014, 16:41 


18/04/14
157
sbp
Пусть имеется массив, состоящий из $N$ чисел: $A[1],...,A[N]$
Необходимо построить массив $B$, состоящий из $N$ чисел, по следующему правилу:
$B[i] = A[1] \cdot ...\cdot A[i-1]\cdot A[i+1]\cdot ...\cdot A[N]$

Ограничения:
Время работы алгоритма: $O(N)$
Память: $O(N)$
Нельзя использовать операцию деления.


Подскажите, хотя бы идею, чтобы достичь время работы O(N)

Самое простое, что приходит в голову. Это просто перебрать, для каждого нового элемента $B$, $N-1$ элемент из массива $A$. Но тогда сложность будет $O(N^2)$

 Профиль  
                  
 
 Re: Работа с массивами.
Сообщение18.12.2014, 16:50 
Заслуженный участник


04/03/09
642
Строите два вспомогательных массива
$C[i]=A[1]\cdot...\cdot A[i]$
$D[i]=A[i+1]\cdot...\cdot A[N]$
Делается это линейно.
Потом перемножаете нужные элементы этих двух массивов, получаете $B[i]$.
Не очень-то олимпиадная задачка, как мне кажется.

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

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



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

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


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

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