Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
TF
0 / 0 / 0
Регистрация: 20.03.2013
Сообщений: 94
#1

Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной - C++

31.10.2013, 22:21. Просмотров 458. Ответов 7
Метки нет (Все метки)

массив из случайных целых чисел от -1000 до 1000. задача найти непрерывную часть этого массива чтобы сумма элементов была максимальной
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2013, 22:21     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
Посмотрите здесь:

Представить заданное число в виде произведения двух натуральных чисел, чтобы их сумма была максимальной - C++
Помогите с задачей пожалуйста,очень срочно!!! Задано натуральное число x. Необходимо представить его в виде произведения x = a • b (a и b –...

Отсортировать строки массива так, чтобы первой шла строка, сумма элементов которой была меньше, чем остальных - C++
Добрый день, помогите, пожалуйста найти ошибку. Нужно создать двумерный массив, размером 5 х 7 (пять строк, семь столбцов). Заполнить...

Найти непрерывную последовательность положительных чисел, сумма элементов которой максимальна - C++
Знайти таку нерозривну послыдовнысть позитивних чисел сума елементыв якый максимальна

Найти ту непрерывную последовательность положительных чисел, сумма элементов которой максимальна - C++
Найти ту непрерывную последовательность положительных чисел, сумма элементов в которой максимальная

Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна - C++
В произвольном массиве нужно найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна. ...

Найти в диапазоне от 10 до 99 такие 3 последовательные числа, чтобы сумма их цифр была равна 15 - C++
Например: 13 14 15. 1+3+1+4+1+5=15.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IchimaruGin
61 / 61 / 24
Регистрация: 14.07.2013
Сообщений: 289
Завершенные тесты: 1
01.11.2013, 00:51     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #2
Цитата Сообщение от TF Посмотреть сообщение
чтобы сумма элементов была максимальной
и как понять ваше условие? по сравнению с чем сума скольких елементов должна быть максимальной? В каком смысле неприрывную?
SatanaXIII
Супер-модератор
Эксперт С++
5594 / 2628 / 240
Регистрация: 01.11.2011
Сообщений: 6,469
Завершенные тесты: 1
01.11.2013, 10:55     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #3
IchimaruGin, я думаю так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
 
int main()
{
const int n = abs(-1000) + 1 + 1000;
int arr[n];
 
for( int i=0; i<n; i++ )
  arr[i] = rand();
 
int currSumm,
    numBegin=arr[0],
    numEnd=arr[0],
    summ=0;
 
for( int begin=0; begin<n; begin++ )
  {
  currSumm = 0;
  for(int end=begin; end<n; end++ )
    {
    currSumm += arr[end];
    if( currSumm > summ )
      {
      summ = currSumm;
      numBegin = begin; // Хрен его знает зачем
      numEnd = end;     //
      }
    }
  }
cout << summ;
cin.ignore();
        return 0;
}
ct0r
Игогошка!
1768 / 670 / 42
Регистрация: 19.08.2012
Сообщений: 1,284
Завершенные тесты: 1
01.11.2013, 11:35     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #4
Цитата Сообщение от SatanaXIII Посмотреть сообщение
numBegin=arr[0],
* * numEnd=arr[0],
Наверное не arr[0], а просто -1?

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

SatanaXIII тоже предложил не самый лучший алгоритм - у него O(n*n). А задача решается с помощью динамического программирования - один раз проходим циклом по массиву, на каждой позиции находя максимальный подмассив, кончающийся на этой позиции. Тогда сложность - О(n).
SatanaXIII
Супер-модератор
Эксперт С++
5594 / 2628 / 240
Регистрация: 01.11.2011
Сообщений: 6,469
Завершенные тесты: 1
01.11.2013, 12:03     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #5
Цитата Сообщение от ct0r Посмотреть сообщение
Наверное не arr[0], а просто -1?
Почему?

Цитата Сообщение от ct0r Посмотреть сообщение
решается с помощью динамического программирования - один раз проходим циклом по массиву, на каждой позиции находя максимальный подмассив, кончающийся на этой позиции. Тогда сложность - О(n).
Зато проигрыш в памяти.
Потом все равно потребуется еще один проход, но уже по созданному массиву.
ct0r
Игогошка!
1768 / 670 / 42
Регистрация: 19.08.2012
Сообщений: 1,284
Завершенные тесты: 1
01.11.2013, 12:51     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #6
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Почему?
Ну потому что иначе странно - ты инициализируешь по сути случайными значениями массива, а потом пихаешь туда индексы.

Цитата Сообщение от SatanaXIII Посмотреть сообщение
Зато проигрыш в памяти.
Потом все равно потребуется еще один проход, но уже по созданному массиву.
Там нету проигрыша в памяти, потому что мы ничего не создаем:
http://en.wikipedia.org/wiki/Maximum_subarray_problem
Кстати, даже если бы понадобился еще один проход, то это все равно О(n), а не O(n*n).
И даже если бы использовалась дополнительная память, то производительность все равно в 90% случаев важнее.
SatanaXIII
Супер-модератор
Эксперт С++
5594 / 2628 / 240
Регистрация: 01.11.2011
Сообщений: 6,469
Завершенные тесты: 1
01.11.2013, 13:18     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #7
Цитата Сообщение от ct0r Посмотреть сообщение
Ну потому что иначе странно - ты инициализируешь по сути случайными значениями массива, а потом пихаешь туда индексы.
Действительно.
Только не -1, а 0. n то у нас больше чем ноль - защита не нужна.

Цитата Сообщение от ct0r Посмотреть сообщение
Maximum_subarray_problem
Спасибо. Почитал.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2013, 13:40     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
Еще ссылки по теме:

В дереве найти такой пусть, чтобы сумма узлов была равна заданному числу - C++
Задача: В дереве найти такой пусть, чтобы сумма узлов была равна 50. В целом, понятно. У меня вышло найти тот узел, в котором эта...

Гипотеза Гольдбаха: найти два таких простых числа, чтобы их сумма была равна заданному - C++
Гипотеза Гольдбаха заключается в том, что всякое четное число большее 2х можно представить в виде суммы двух простых чисел. По заданному...

Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна - C++
В данной последовательности чисел найти подпоследовательность подряд идущих элементов, сумма которых минимальна. Реализовать с помощью...

Рекурсия: удалить из дерева часть вершин, чтобы оставшееся дерево стало пирамидой - C++
Рекурсия .Удалить из дерева часть вершин так чтобы оставшееся дерево стало пирамидой


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
zitxbit
Master C/C++
87 / 739 / 75
Регистрация: 11.04.2012
Сообщений: 971
01.11.2013, 13:40     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной #8
Вот мой вариант решения задачи. Алгоритм - получение методом перебора всех под-последовательностей элементов с каждой позиции в массиве. Далее вычисление суммы элементов каждой из под-последовательностей, далее нахождение наибольшей суммы.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
#define N 10
 
int main(int argc, char* argv[])
{
    int A[N] = { 0 };
    for (int i = 0; i < N; i++)
    {
        A[i] = rand() % 2000 - 1000;
        printf("%d ",A[i]);
    }
 
    printf("\n\n");
 
    int max = 0, pos = 0, len = 0;
    for (int t = 0; t < N; t++)
    {
        int cnt = 0;
        while (cnt < N)
        {
            int k = t, sum = 0;
            while (k <= cnt) sum+=A[k++];
            if (sum > max) { max = sum; pos = t; len = cnt-pos+1; }
 
            cnt++;
        }
    }
 
    printf("sum = %d pos = %d len = %d\n",max,pos,len);
 
    _getch();
}
http://codepad.org/MKOuhrDx
Миниатюры
Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной  
Yandex
Объявления
01.11.2013, 13:40     Рекурсия: найти непрерывную часть массива, чтобы сумма элементов была максимальной
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru