Форум русскоязычного сообщества Ubuntu


Получить помощь и пообщаться с другими пользователями Ubuntu можно
на irc канале #ubuntu-ru в сети Freenode
и в Jabber конференции ubuntu@conference.jabber.ru

Автор Тема: поиск максимального подмассива  (Прочитано 3092 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Здравствуйте, продолжаю изучать алгоритмы, написал программу для поиска макс.подмассива, но она не работает, подскажите почему.
Код: (python) [Выделить]
__author__ = 'denis'
m = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]


def find_max_crossing_subarray(a, low, mid, high):
    left_sum = -1e308
    s = 0
    for i in range(mid, low, -1):
        s += a[i]
        if s > left_sum:
            left_sum = s
            max_left = i
    right_sum = -1e308
    s = 0
    for j in range(mid, high, 1):
        s += a[j]
        if s > right_sum:
            right_sum = s
            max_right = j
    return max_left, max_right, left_sum + right_sum


def find_max_subarray(a, low, high):
    if high == low:
        return low, high, a[low]
    else:
        mid = (low + high) / 2
        left_low, left_high, left_sum = find_max_subarray(a, low, mid)
        right_low, right_high, right_sum = find_max_subarray(a, mid, high)
        cross_low, cross_high, cross_sum = find_max_crossing_subarray(a, low, mid+1, high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        if right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum

min, max, sum = find_max_subarray(m, 0, 15)

print(min, max, sum)
по ошибке я понял, что достигается предел глубины рекурсии, но сомневаюсь что нужно 1000 итераций для массива на 16 элементов

Пользователь решил продолжить мысль 30 Июля 2015, 16:26:00:
добавление этого кода не помогло :
Код: (python) [Выделить]
import sys
sys.setrecursionlimit(100000)
« Последнее редактирование: 30 Июля 2015, 16:26:00 от DenisVASI »

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6017
  • Windows10, i3wm on Debian9, Manjaro20.0
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #1 : 30 Июля 2015, 17:22:53 »
Будет проще если Вы объясните условие задачи (что-то подобное я уже встречал и делалось оно на порядок проще)
В Линукс можно сделать ВСЁ что угодно, достаточно знать КАК !

Оффлайн alsoijw

  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #2 : 30 Июля 2015, 17:36:37 »
DenisVASI, как это макс.подмассив?
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #3 : 30 Июля 2015, 19:37:27 »
подмассив с максимальной суммой элементов, т.е a = [-1, 4, -3, 5, -1], максимальным будет 4, -3, 5
или другой пример использующий этот алгоритм http://habrahabr.ru/post/129576/ ,кстати эта программа тоже не работает
 

Пользователь решил продолжить мысль [time]30 Июль 2015, 20:41:30[/time]:
Azure, вы правы можно проще, но есть я хочу знать рекурсивное решение,
к тому-же если я правильно понимаю этот алгоритм работает за время n lg n, а приведенные ниже варианты за n^2, хотя могу ошибаться, я ведь только учусь ;)
Код: (python) [Выделить]
__author__ = 'denis'
a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

s = 0
ans = a[0]
ans_l = 0
ans_r = 0
min_sum = 0
min_pos = -1
[code = python]
for i in range(len(a)):
    s += a[i]
    cur = s - min_sum
    if cur > ans:
        ans = cur
        ans_l = min_pos + 1
        ans_r = i
    if s < min_sum:
        min_sum = s
        min_pos = i

print(ans, ans_l, ans_r)
Код: (python) [Выделить]
__author__ = 'denis'
a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

answer = 0
answer_l = 0
answer_r = 0
s = 0
minus_pos = -1

for i in range(len(a)):
    print(j)
    s += a[i]
    if s > answer:
        answer = s
        answer_l = minus_pos + 1
        answer_r = i
    if s < 0:
        s = 0
        minus_pos = i

print(answer, answer_l, answer_r)

Пользователь решил продолжить мысль [time]30 Июль 2015, 20:52:55[/time]:
Вот оригинал текста задачи: http://rghost.ru/7vlNsqn6b#
« Последнее редактирование: 30 Июля 2015, 20:29:45 от DenisVASI »

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6017
  • Windows10, i3wm on Debian9, Manjaro20.0
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #4 : 31 Июля 2015, 09:08:53 »
Не увлекайтесь рекурсией, не здорово это:
Код: (python) [Выделить]
def max_sum_part(my_list):
    max_sum = 0
    list_length = len(my_list)
    r_border = list_length + 1
    for i in range(list_length):
        for j in range(i + 1, r_border):
            sum_part = sum(my_list[i:j]):
            if sum_part > max_sum:
                max_sum, left, right = sum_part, i, j - 1
    return (max_sum, left, right)
Или можно сократить используя генераторы:
Код: (python) [Выделить]
def max_sum_part(my_list):
    return max((sum(a[i:j]),i,j - 1) for i in range(len(a)) for j in range(i + 1, len(a) + 1))
« Последнее редактирование: 31 Июля 2015, 09:41:56 от Azure »
В Линукс можно сделать ВСЁ что угодно, достаточно знать КАК !

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #5 : 31 Июля 2015, 11:02:20 »
Не увлекаюсь, но в книге целая глава этому посвящена, мне хочется знать как она работает.Тем более мой код не работает.Раз не работает, значит есть пробел в знаниях, вот и подскажите где он, пожалуйста)

Пользователь решил продолжить мысль 31 Июля 2015, 11:12:17:
И ещё, а чем она(рекурсия) так плоха? Недавно общался с хаскелистом, так он говорит что у нее репутация как у goto в мире функциональных яп.
« Последнее редактирование: 31 Июля 2015, 11:12:17 от DenisVASI »

Оффлайн SkinnyJack

  • Любитель
  • *
  • Сообщений: 53
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #6 : 31 Июля 2015, 11:52:33 »
Не увлекаюсь, но в книге целая глава этому посвящена, мне хочется знать как она работает.Тем более мой код не работает.Раз не работает, значит есть пробел в знаниях, вот и подскажите где он, пожалуйста)

Пользователь решил продолжить мысль [time]31 Июль 2015, 12:12:17[/time]:
И ещё, а чем она(рекурсия) так плоха? Недавно общался с хаскелистом, так он говорит что у нее репутация как у goto в мире функциональных яп.

Скорее всего проблема в условиях выхода из рекурсии. Прогоните по шагам.

Рекурсия, в принципе, не может быть плохой или хорошей. Это инструмент, как и goto. Другое дело, что можно переполнить стэк при большом уровне вложенности, к тому же, неуместное использование рекурсии, как и goto, приводит к излишней запутанности кода(это, наверное, и имел в виду ваш знакомый). Посмотрите на ту же реализацию алгоритма вычисления факториала, на quicksort, на алгоритмы обхода бинарных деревьев(которые сами по себе рекурсивны) - там рекурсия смотрится органично и не мешает восприятию. Уж не знаю  что у вас там за книжка, но настоятельно рекомендую "Алгоритмы + струкуры данных = программы" Никлауса Вирта.

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12123
  • Xubuntu 20.04
    • Просмотр профиля
    • Github
Re: поиск максимального подмассива
« Ответ #7 : 31 Июля 2015, 12:11:17 »
Я вот не понял зачем в этой задаче рекурсия?  :idiot2:

Все три предложенных решения (после исправления незначительных ошибок) работают и дают одинаковый результат, причем однопроходный вариант - быстрее:

(43, 7, 10)

Execution time : 0.000191 s.

(43, 7, 10)

Execution time : 0.000179 s.

(43, 7, 10)

Execution time : 0.000023 s.

(Нажмите, чтобы показать/скрыть)
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: https://help.ubuntu.ru/wiki/uefiboot

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6017
  • Windows10, i3wm on Debian9, Manjaro20.0
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #8 : 31 Июля 2015, 14:47:48 »
А еще проще не изобретать велосипед:
Код: (python) [Выделить]
def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
В Линукс можно сделать ВСЁ что угодно, достаточно знать КАК !

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12123
  • Xubuntu 20.04
    • Просмотр профиля
    • Github
Re: поиск максимального подмассива
« Ответ #9 : 31 Июля 2015, 15:07:36 »
Azure, это решение дает только саму максимальную сумму. Как оттуда вытащить хоть один из индексов - я не понял. А без индексов поиск максимума дает только пол ответа.
У DenisVASI, решение тоже линейное время для решения требует, но дает полноценный ответ.

« Последнее редактирование: 31 Июля 2015, 15:10:30 от Sly_tom_cat »
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: https://help.ubuntu.ru/wiki/uefiboot

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6017
  • Windows10, i3wm on Debian9, Manjaro20.0
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #10 : 31 Июля 2015, 18:49:22 »
Как оттуда вытащить хоть один из индексов - я не понял. А без индексов поиск максимума дает только пол ответа.
Ну надо чуть доработать ;)
Код: (python) [Выделить]
def max_subarray(A):
        max_ending_here = max_so_far = A[0]
        i=0
        for x in A[1:]:
                i+=1
                if max_ending_here < 0:
                        max_ending_here = x
                        start_here = i
                else:
                        max_ending_here += x
                if max_so_far < max_ending_here:
                        max_so_far, left, right = max_ending_here, start_here, i
        return max_so_far, left, right
« Последнее редактирование: 31 Июля 2015, 18:51:51 от Azure »
В Линукс можно сделать ВСЁ что угодно, достаточно знать КАК !

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12123
  • Xubuntu 20.04
    • Просмотр профиля
    • Github
Re: поиск максимального подмассива
« Ответ #11 : 31 Июля 2015, 18:56:16 »
Azure, ну по сути и получили решение как у DenisVASI.
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: https://help.ubuntu.ru/wiki/uefiboot

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6017
  • Windows10, i3wm on Debian9, Manjaro20.0
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #12 : 31 Июля 2015, 18:57:13 »
Это не я, это Вики
Код: (python) [Выделить]
def max_subarray(A):
        max_ending_here = max_so_far = A[0]
        for x in enumerate(A[1:]):
                if max_ending_here < 0:
                        max_ending_here = x[1]
                        start = x[0]
                else:
                        max_ending_here += x[1]
                if max_so_far < max_ending_here:
                        max_so_far, left, right = max_ending_here, start, x[0]
        return max_so_far, left + 1, right + 1
« Последнее редактирование: 31 Июля 2015, 18:58:58 от Azure »
В Линукс можно сделать ВСЁ что угодно, достаточно знать КАК !

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #13 : 31 Июля 2015, 20:24:21 »
Книга: Алгоритмы - построение и Анализ, 3 издание, Томас Кормен.
Если кому не лень скачайте скан этой книги, и прочитайте стр.93-98. Там автор даёт пояснение почему его вариант как он считает лучше, я извиняюсь за излишнюю настойчивость, но на мой изначальный вопрос так ответа и не дали, где в моём коде ошибка? Найти иные решения я и сам сумел, проблема ведь именно в этой программе. Я не собираюсь пихать рекурсию везде, но я хочу сейчас понять как работает она в этой программе, я думал что понял, написал код, он не работает, опять же почему(код не работает)? А так всем спасибо, кто уделил внимание :)
Я понял что рекурсия тут может и не очень уместна, но раз этот код не работает, значит у меня есть пробел в знания, только даже ради этого стоит понять где там ошибка, тут ведь проблема где-то в записи кода, а не в моем понимании работы этого алгоритма, а значит и знания которые я тут получу будут распространяться на все мои будущие программы, так что помогите)


Пользователь решил продолжить мысль [time]31 Июль 2015, 21:34:50[/time]:
http://scanlibs.com/algoritmyi-postroenie-i-analiz-3-e-izdanie/  - вот, можно тут взять
« Последнее редактирование: 31 Июля 2015, 20:41:38 от DenisVASI »

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12123
  • Xubuntu 20.04
    • Просмотр профиля
    • Github
Re: поиск максимального подмассива
« Ответ #14 : 31 Июля 2015, 20:53:48 »
DenisVASI, я же поправил и запустил твой код. Правда в python3. Если у тебя не работает. То скопируй из моего сообщения и третьем питоне запусти - должно работаь.

В целом у питона вполне внятные сообщения об ошибках. Как правило там очень четко написано - что не так, и иногда даже написано как надо исправить.
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: https://help.ubuntu.ru/wiki/uefiboot

 

Страница сгенерирована за 0.097 секунд. Запросов: 25.