![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
The First Person!
Форумчанин
Регистрация: 07.08.2007
Сообщений: 228
|
![]()
У меня тут возник вопрос по поводу одной задачи. Ее нужно решать с помощью математических расчетов? Или моделировать ситуацию и смотреть результат? Но, тут проблема с размером массива.
Вот, собственно, задача:
Программа обычно делает то что вы ей сказали сделать, а не то что бы вы хотели, чтобы она сделала.
|
![]() |
![]() |
![]() |
#2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
![]()
Можно решать математически, но это довольно геморный способ (имею ввиду решение, у которого сложность даже ниже, чем log(n), близко к О(1)), а сдесь прокатит и обычное моделирование в одном измерении (считать за О(1) целую линию в вертикальном или горизонтальном направлении), тогда получим О(N) относительно ширины области покрытия.
Последний раз редактировалось LeBron; 15.01.2010 в 22:07. |
![]() |
![]() |
![]() |
#3 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
![]()
Ради интереса решил. У меня получилась логарифмическая сложность.
ЗЫ Никакого массива не использовал. Последний раз редактировалось Carbon; 15.01.2010 в 21:30. |
![]() |
![]() |
![]() |
#4 |
The First Person!
Форумчанин
Регистрация: 07.08.2007
Сообщений: 228
|
![]()
Чтобы решать в общем виде массивом нужно создать массив a[200000][200000]. Но это слишком большой, как быть?
Программа обычно делает то что вы ей сказали сделать, а не то что бы вы хотели, чтобы она сделала.
|
![]() |
![]() |
![]() |
#5 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
![]()
Кинуть своё решение?
|
![]() |
![]() |
![]() |
#6 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
![]()
Если надо за линейное время (не самый оптимальный, но, как мне показалось, самый простой способ решения) - тогда линейный массив.
Если чуть пошевелить мозгами, то в таком случае можно и вообще без массива, ведь мы будем на ходу суммировать результаты с текущим ответом. |
![]() |
![]() |
![]() |
#7 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
![]()
Ладно. Мой вариант:
Код:
Последний раз редактировалось Carbon; 16.01.2010 в 18:05. |
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Принцип действия увеличения репутации | Neeter | О форуме и сайтах клуба | 3 | 14.05.2009 08:08 |
Принцип поисковых систем | Romanbl4 | Свободное общение | 7 | 23.08.2007 18:31 |
принцип PHP | ErWe | PHP | 3 | 11.05.2007 20:06 |