Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Такая вот задачка...  (Прочитано 21594 раз)
0 Пользователей и 1 Гость смотрят эту тему.
ysv_
Помогающий

ua
Offline Offline

« : 21-10-2003 17:47 » 

Любителям поломать голову посвящается.

Есть одномерный массив целых чисел длинной N. Необходимо найти подмассив, сумма элементов которого будет максимальной для данного массива.

Пример.
1) Массив : 1 7 -5 3 -5 7
Максимальная сумма у подмассива: 1 7
2)  Массив : 1 7 -5 3 -5 9
Максимальная сумма у подмассива: 9

Какие будут  :idea:  :?:
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #1 : 21-10-2003 18:36 » 

Хм.
Вопрос - длина подмассива какая???
Принцип построения помассива - сумма чисел составляющие числа, или еще как-то, пока я например, так и не понял откуда берутся 17 и 9 - потому как если брать длину 3 то в первом случае получается 17 во втором 19 - а никак не 9...
В общем непонятна пока задачка. :?:
Записан

А птичку нашу прошу не обижать!!!
grozny
Гость
« Ответ #2 : 21-10-2003 20:22 » 

классическая задачка  Отлично

Гром, обрати внимание - числа положительные и отрицательные. Т.е. добавление отрицательного числа УМЕНЬШАЕТ сумму.

А подмассив - понятно - математическое подмножество массива. Т.е. если в массиве только положительные числа, то ответ тривиален, искомый подмассив есть сам массив, если числа только отрицательные - то подмассив состоит из одного эл-та, а именно - наименьшего (по модулю) числа.
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #3 : 21-10-2003 20:49 » 

grozny, 1 7 -5 3 -5 7
Так это минусы ... я думал тире  Отлично  :oops:
Только непонятно как тут
Цитата

 2) Массив : 1 7 -5 3 -5 9
Максимальная сумма у подмассива: 9

 9-ка оказалась...
Если это 1 и 7 то тогда сумма 9 - если 17 - то тогда 17, как и впервом случае - в общем поточнее не помешает все равно.
Записан

А птичку нашу прошу не обижать!!!
grozny
Гость
« Ответ #4 : 21-10-2003 23:15 » 

отрицательные тире  Отлично я сперва тоже не понял, что весь смысл - в появлении отрицательных чисел. А сами по себе значения мало важны.

Алгоритм решения достаточно прост, более того можно сразу за проход и мин и макс найти.

Если уточнить, то решение должно быть "оптимальным", т.е. не квадратичным перебором. Кстати, на собеседованиях дают

Чуть не забыл - полагаю, мы ищем НЕПРЕРЫВНЫЙ подсписок с максимальной суммой членов?
Записан
Sashok
Молодой специалист

us
Offline Offline
Пол: Мужской

« Ответ #5 : 22-10-2003 04:52 » 

Я тоже так полагаю.

Гром, полагаю, что ysv неправильно выразился. Он имел ввиду не "Максимальная сумма у подмассива: 1 7", а "Максимальная сумма у подмассива: (1, 7)"
Записан

Если бы окружающие нас объекты содержали столько же ошибок, сколько программы, цивилизация обрушилась бы от первого порыва ветра...
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #6 : 22-10-2003 06:59 » 

grozny, примитивная задачка...
днако все ж ошибка - как и сказал Sashok у товарища есть... "ошибки", и не только в постановке задачи но и в результатах им же показанных, или мы его не правильно понимаем, но где же он сам Не понял
Записан

А птичку нашу прошу не обижать!!!
ysv_
Помогающий

ua
Offline Offline

« Ответ #7 : 22-10-2003 11:46 » 

Ну вот и я!
1. Длина подмассива наперед неизвестна.
2. Я числа разделял пробелами, так что 1 7 -- это (1, 7), а 9 -- (9).
3. ИМХО, подмассив не может быть не непрерывным. Тогда это будет множество подмассивов.
4. Действительно, требование к алгоритму - количество операций O(N), то есть возрастает линейно при увеличении длины массива. После чего эта задача превращается в несовсем примитивную Улыбаюсь.
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #8 : 22-10-2003 11:51 » 

ysv_, О понял - теперича можно и писать - еще вопросик, числа от 0 до 9 или есть другие ограничения, скажем MAX_INT :?:
Записан

А птичку нашу прошу не обижать!!!
Serega
Гость
« Ответ #9 : 22-10-2003 12:14 » 

IMHO ограничения на числа не важны
Простейшее решение: построить дерево подмассивов и найти в нем узел с максимальмым весом (сложность O(N*log(N)))
Что-нить более интересное придумаю к вечеру  Вот такой я вот
Записан
ysv_
Помогающий

ua
Offline Offline

« Ответ #10 : 22-10-2003 13:05 » 

Цитата

IMHO ограничения на числа не важны

Sereqa абсолютно прав!

Цитата

Простейшее решение: построить дерево подмассивов и найти в нем узел с максимальмым весом (сложность O(N*log(N)))

Что-то у меня оценка вызывает сомнение. Поиск - да. А построение дерева?
Записан
Diletant
Помогающий

de
Offline Offline

« Ответ #11 : 22-10-2003 13:10 » 

Во втором случае ответ неверный. Максимальная сумма будет у подмассива
 1 7 -5 3 -5 9. Сам массив - он тоже подмассив.
Записан
Serega
Гость
« Ответ #12 : 22-10-2003 13:26 » 

В дереве 2N узлов, N*Log(N) > 2N для N > 4, вот и оценка
Записан
Serega
Гость
« Ответ #13 : 22-10-2003 13:29 » 

Надо вспомнить динамическое програмирование, есть поиск в дереве быстрее N*Log(N) (у нас всетаки не произвольное дерево)
Но сейчас моя память занята другим Отлично
Записан
ysv_
Помогающий

ua
Offline Offline

« Ответ #14 : 22-10-2003 13:42 » 

Цитата

Во втором случае ответ неверный. Максимальная сумма будет у подмассива
1 7 -5 3 -5 9. Сам массив - он тоже подмассив.

Diletant прав. Чего-то я в примерах проехал. Наверно уставший был. Жаль

Правильно так:
1) Массив : (1, 7, -5, 1, -5, 7)
Максимальная сумма у подмассива: (1, 7)
2) Массив : (1, 7, -5, 1, -5, 9)
Максимальная сумма у подмассива: 9
Записан
ysv_
Помогающий

ua
Offline Offline

« Ответ #15 : 22-10-2003 13:48 » 

Цитата

В дереве 2N узлов, N*Log(N) > 2N для N > 4, вот и оценка

А почему 2N?

Цитата

Надо вспомнить динамическое програмирование, есть поиск в дереве быстрее N*Log(N) (у нас всетаки не произвольное дерево)

Решается без использования динамического программирования. В принципе достачно школьных знаний. О :!:
Записан
Serega
Гость
« Ответ #16 : 22-10-2003 14:42 » 

Цитата: ysv_
А почему 2N?

Ошибся я, (N**2)/2
Да, оценка не утешительная  Отлично
Записан
grozny
Гость
« Ответ #17 : 22-10-2003 22:11 » 

Цитата: ysv_

Diletant прав. Чего-то я в примерах проехал. Наверно уставший был. Жаль

Правильно так:
1) Массив : (1, 7, -5, 1, -5, 7)
Максимальная сумма у подмассива: (1, 7)
2) Массив : (1, 7, -5, 1, -5, 9)
Максимальная сумма у подмассива: 9


Гм. Если "подмассив" может разрываться, т.е. состоять из эл-том с неподряд идущими индексами, то ответ тривиален - все положительные элементы формируют такой "подмассив". И тогда ответ никак не 9. Ответ 9 получается только в том случае, если мы ищем непрерывный (по индексам) подмассив. Так что опять непонятки.

В данном случае поиск по дереву неуместен, так что сложность далеко не квадратична.

В случае непрерывных подмассивов решение не менее просто, чем в случае "прерывных".
Нам нужен всего один проход по массиву, во время которого мы формируем список всех положительно определённых "обрывков" (по дороге суммируя). И затем ищем максимум тех сумм. Всё. Т.е. О(N).

Вот если "прерывные" подмассивы и мы должны отыскать макимальную сумму в подмассивах M эл-тов длиной, вот тогда только небольшой фан со сложностью и квадратичным перебором
Записан
ysv_
Помогающий

ua
Offline Offline

« Ответ #18 : 23-10-2003 07:25 » 

Подмассивы - непрерывны.
Цитата

В случае непрерывных подмассивов решение не менее просто, чем в случае "прерывных".
Нам нужен всего один проход по массиву, во время которого мы формируем список всех положительно определённых "обрывков" (по дороге суммируя). И затем ищем максимум тех сумм. Всё. Т.е. О(N).

Ответ неправилен!
Пример:
(-3, 6, -5, 2, -1) - по твоему методу grozny - получаем (6), правильный ответ - (6, -5, 2). Вот!
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #19 : 23-10-2003 10:27 » 

Массив из 1 го элемента тоже массив - сумма 6-5+2 = 3 - так что ответ грозного правилен.
Записан

А птичку нашу прошу не обижать!!!
ysv_
Помогающий

ua
Offline Offline

« Ответ #20 : 23-10-2003 13:02 » 

Да неудачное опровержение Жаль.
Что-то я торможу  :oops:
Но все же опровержение метода grozny есть - (-3, 6, -5, 7, -1).
По методу grozny (7), правильно (6, -5, 7) - сумма=8.
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #21 : 23-10-2003 16:39 » 

Ну тогда надо уточнять более точно условие задачи Жаль я думаю сразу оговаривать о сумме любого непрерывного подмассива, тогда это простой перебор всех сочетаний - есть формула... идущих подряд.

А второй вариант - говорить о точных разделителях - скажем отрицательное число...

В твоем варианте я так понимаю ограничителей нет...
Записан

А птичку нашу прошу не обижать!!!
ysv_
Помогающий

ua
Offline Offline

« Ответ #22 : 23-10-2003 17:54 » 

Цитата

Ну тогда надо уточнять более точно условие задачи  я думаю сразу оговаривать о сумме любого непрерывного подмассива, тогда это простой перебор всех сочетаний - есть формула... идущих подряд.

Да имеется ввиду сумма любого непрерывного подмассива. Наверное я зря привел примеры Жаль. У меня такое впечатление, что они только все запутали.

Но все же говорить что подмассив непрерывный ИМХО все ровно, что сказать масло масляное.

А вот откуда возникла мысль о разделителях, мне не понятно :?

Нащет формулы - как правильно заметил Серега это порядка N^2 операций. Так что неподходит Жаль
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #23 : 23-10-2003 18:36 » 

:idea: люди, есть дубовый метод перебора, вот алгоритм на пальцАх:

имеется два указателя - p1 и p2 (начало и конец текущего подмассива).
имеется переменные MaxSumm, MaxP1, MaxP2 под хранение максимальной суммы и начала/конца такого подмассива
инитка: оба укля - на начало массива, MaxSumm=0
1) считаем сумму элементов между уклями
2) если сумма>MaxSumm, то сохраняем p1, p2 и новую макс. сумму подмассива
3)p2++
4)если p2 упёрся в стенку,то  {p1++;p2=p1+1} идём на 5), иначе идём на 1)
5)если p1 не упёрся в стенку,то идём на 1)
6)длина == MaxP2 -MaxP1, сумма == MaxSumm,
7) Отлично
Записан

ysv_
Помогающий

ua
Offline Offline

« Ответ #24 : 24-10-2003 10:18 » 

Итак первая часть задачи решена Улыбаюсь. Единственное замечание - в качестве инита следует взять первый элемент массива ( а вдруг все элементы - отрицательны).
Оценив кол-во операций для этого алгоритма получим N^2. Собственно решение такого типа имел в виду Грозный.
Цитата

Алгоритм решения достаточно прост, более того можно сразу за проход и мин и макс найти.

А теперь нужно найти алгоритм, который делает тоже самое за порядка N операций.
Записан
ysv_
Помогающий

ua
Offline Offline

« Ответ #25 : 27-10-2003 12:21 » new

А вот и решение:

#include <stdio.h>

//int arr[]={-1, 3, -5, 3, 3, -8, 4, 7, -2, 3};
int arr[]={1, 7, -5, 3, -5, 9};

struct subsum
{
  int pos;
  int len;
  int sum;
} max, max_end;

int main(int argc, char** argv)
{
  int i, s;
  max_end.pos=0; max_end.len=1; max_end.sum=arr[0];
  max=max_end;
  for (i=1; i<(sizeof(arr)/sizeof(arr[0])); ++i)
  {
    s=arr;
    max_end.sum+=s; ++max_end.len;
    if (max_end.sum<s)
    {
      max_end.pos=i; max_end.len=1; max_end.sum=s;
    }
    if (max_end.sum>max.sum) max=max_end;
  }
 
  printf("Max. sum=%d has subarray (%d", max.sum, arr[max.pos]);
  for (i=max.pos+1; i<max.pos+max.len; ++i)
  {
    printf(", %d", arr);
  }
  printf(")\n");
}
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines