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


Считаете, что Ubuntu недостаточно дружелюбна к новичкам?
Помогите создать новое Руководство для новичков!

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

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

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Здравствуйте, продолжаю изучать алгоритмы, написал программу для поиска макс.подмассива, но она не работает, подскажите почему.
Код: Python
  1. __author__ = 'denis'
  2. m = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
  3.  
  4.  
  5. def find_max_crossing_subarray(a, low, mid, high):
  6.     left_sum = -1e308
  7.     s = 0
  8.     for i in range(mid, low, -1):
  9.         s += a[i]
  10.         if s > left_sum:
  11.             left_sum = s
  12.             max_left = i
  13.     right_sum = -1e308
  14.     s = 0
  15.     for j in range(mid, high, 1):
  16.         s += a[j]
  17.         if s > right_sum:
  18.             right_sum = s
  19.             max_right = j
  20.     return max_left, max_right, left_sum + right_sum
  21.  
  22.  
  23. def find_max_subarray(a, low, high):
  24.     if high == low:
  25.         return low, high, a[low]
  26.     else:
  27.         mid = (low + high) / 2
  28.         left_low, left_high, left_sum = find_max_subarray(a, low, mid)
  29.         right_low, right_high, right_sum = find_max_subarray(a, mid, high)
  30.         cross_low, cross_high, cross_sum = find_max_crossing_subarray(a, low, mid+1, high)
  31.         if left_sum >= right_sum and left_sum >= cross_sum:
  32.             return left_low, left_high, left_sum
  33.         if right_sum >= left_sum and right_sum >= cross_sum:
  34.             return right_low, right_high, right_sum
  35.         else:
  36.             return cross_low, cross_high, cross_sum
  37.  
  38. min, max, sum = find_max_subarray(m, 0, 15)
  39.  
  40. print(min, max, sum)
  41.  
по ошибке я понял, что достигается предел глубины рекурсии, но сомневаюсь что нужно 1000 итераций для массива на 16 элементов

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

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6016
  • 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
  1. __author__ = 'denis'
  2. a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
  3.  
  4. s = 0
  5. ans = a[0]
  6. ans_l = 0
  7. ans_r = 0
  8. min_sum = 0
  9. min_pos = -1
  10. [code = python]
  11. for i in range(len(a)):
  12.     s += a[i]
  13.     cur = s - min_sum
  14.     if cur > ans:
  15.         ans = cur
  16.         ans_l = min_pos + 1
  17.         ans_r = i
  18.     if s < min_sum:
  19.         min_sum = s
  20.         min_pos = i
  21.  
  22. print(ans, ans_l, ans_r)
  23.  
Код: Python
  1. __author__ = 'denis'
  2. a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
  3.  
  4. answer = 0
  5. answer_l = 0
  6. answer_r = 0
  7. s = 0
  8. minus_pos = -1
  9.  
  10. for i in range(len(a)):
  11.     print(j)
  12.     s += a[i]
  13.     if s > answer:
  14.         answer = s
  15.         answer_l = minus_pos + 1
  16.         answer_r = i
  17.     if s < 0:
  18.         s = 0
  19.         minus_pos = i
  20.  
  21. print(answer, answer_l, answer_r)
  22.  

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

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6016
  • Windows10, i3wm on Debian9, Manjaro20.0
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #4 : 31 Июль 2015, 09:08:53 »
Не увлекайтесь рекурсией, не здорово это:
Код: Python
  1. def max_sum_part(my_list):
  2.     max_sum = 0
  3.     list_length = len(my_list)
  4.     r_border = list_length + 1
  5.     for i in range(list_length):
  6.         for j in range(i + 1, r_border):
  7.             sum_part = sum(my_list[i:j]):
  8.             if sum_part > max_sum:
  9.                 max_sum, left, right = sum_part, i, j - 1
  10.     return (max_sum, left, right)
Или можно сократить используя генераторы:
Код: Python
  1. def max_sum_part(my_list):
  2.     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!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12075
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
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 - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн Azure

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

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12075
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
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 - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн Azure

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

Оффлайн Sly_tom_cat

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

Оффлайн Azure

  • Модератор раздела
  • Старожил
  • *
  • Сообщений: 6016
  • Windows10, i3wm on Debian9, Manjaro20.0
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #12 : 31 Июль 2015, 18:57:13 »
Это не я, это Вики
Код: Python
  1. def max_subarray(A):
  2.         max_ending_here = max_so_far = A[0]
  3.         for x in enumerate(A[1:]):
  4.                 if max_ending_here < 0:
  5.                         max_ending_here = x[1]
  6.                         start = x[0]
  7.                 else:
  8.                         max_ending_here += x[1]
  9.                 if max_so_far < max_ending_here:
  10.                         max_so_far, left, right = max_ending_here, start, x[0]
  11.         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!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12075
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: поиск максимального подмассива
« Ответ #14 : 31 Июль 2015, 20:53:48 »
DenisVASI, я же поправил и запустил твой код. Правда в python3. Если у тебя не работает. То скопируй из моего сообщения и третьем питоне запусти - должно работаь.

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

 

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