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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
А1екс
0 / 0 / 0
Регистрация: 06.12.2009
Сообщений: 7
#1

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

06.12.2009, 19:58. Просмотров 1021. Ответов 10
Метки нет (Все метки)

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

В двумерном массиве A[N][M] поменять местами строки,в которых сумма элементов максимальна и минимальна. C++
В последовательности найти наиболее длинную последовательность подряд идущих нулей C++
C++ Создать массив A(n) и найти длину самойдлиной последовательности подряд идущих элементов
C++ Найти последовательности из трех элементов, сумма которых больше 10
C++ Найти в последовательности чисел два подряд идущих нуля
C++ Найти коэффициенты разложения, при которых сумма минимальна
Рекурсивная функция, которая находит позицию начала последовательности из 10 чисел, сумма которых минимальна C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
06.12.2009, 21:33     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #2
Цитата Сообщение от А1екс Посмотреть сообщение
найти подпоследовательность подряд идущих элементов
Какая длина последовательности подряд идущих элементов должна быть?
А1екс
0 / 0 / 0
Регистрация: 06.12.2009
Сообщений: 7
06.12.2009, 23:28  [ТС]     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #3
любая
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.12.2009, 08:18     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #4
Пример можно ?

Если длина любая - то находишь минимум массива.
Это будет подпоследовательность подряд идущих элементов, сумма которых минимальна, причем длина подпоследовательности имеют длину 1.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2009, 08:34     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #5
для длины подпоследовательности от 2-х и более элементов, сумма которых минимальна:
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream.h>
#include <windows.h>
#include<conio.h>
 
void posl_min(int *mas, int n, int i, int &i_start, int &count, int count_temp, bool fl, bool &fl1)
{
    if(mas[i]==mas[i+1])
    {
        if(fl)
        {
            count_temp++;
        }
        if(!fl)
        {
            fl=true;
            count_temp=2;
        }       
    }
    if((mas[i]!=mas[i+1] || i==n-2) && fl)
    {
        if(!fl1)
        {
            fl1=true;
            i_start=i-count_temp+1;
            count=count_temp;
        }
        if(mas[i]*count_temp<count*mas[i_start] && fl1)
        {
            i_start=i-count_temp+1;
            count=count_temp;
        }
        if(i==n-2 && fl)
            i_start++;
        fl=false;
    }
    i++;
    if(i<n-1)
        posl_min(mas, n, i, i_start, count, count_temp, fl, fl1);
}   
 
 
void main()
{
    int *mas, n, i=0, i_start=0, count=0, count_temp;
    bool fl=false, fl1=false;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå Г°Г*çìåðГ*îñòü ïîñëåäîâГ*òåëüГ*îñòè: "<< endl;
    cin>>n;
    mas=new int[n];
    cout<<"Ââåäèòå ýëåìåГ*ГІГ» ïîñëåäîâГ*òåëüГ*îñòè: "<< endl;
    for(i=0; i<n; i++)
    {
       cout<<"["<<i<<"]= ";
       cin>>mas[i];
    }
    cout<<"èñõîäГ*Г*Гї ïîñëåäîâГ*òåëüГ*îñòü:"<<endl;
    for(i=0; i<n; i++)
       cout<<mas[i]<<" ";
    cout<<endl;
    i=0;
    posl_min(mas, n, i, i_start, count, count_temp=0, fl, fl1);
    if(!fl1)
        cout<<"Ïîäðÿä èäóùèõ ýëåìåГ*òîâ Г*ГҐГІ";
    else
    {
        cout<<"Ïîäðÿä èäóùèå ýëåìåГ*ГІГ» Г± ìèГ*ГЁГ¬Г*ëüГ*îé ñóììîé: "<<endl;
        for(i=i_start; i<i_start+count; i++)
            cout<<mas[i]<<" ";
    }
    cout<<endl;
    getch();
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 05:53     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #6
Цитата Сообщение от Deniel Посмотреть сообщение
valeriikozlov а где здесь рекурсия????
Давайте попробуем ее найти!
Может быть в определении функции void posl_min() в строке 38 моего кода? Такая рекурсия не подойдет?
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
11.12.2009, 18:19     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #7
valeriikozlov, А что это за ситуация у Вас получается, когда Подряд идущих элементов нет??? Я так понимаю, что количество элементов матрицы равно 0?!
Вот реализация этой проги в моем понимании для любой длины последовательности (от 1 и до n):
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
36
37
38
39
40
41
#include <iostream.h>
#include <conio.h>
 
void posl_min(int* InputArray,int Length,int &min,int &Begin_Index,int &End_Index)
{
  for (int i = 0; i < Length; i++)
  {
     int Sum=0;
     for (int j=i; j < Length; j++) Sum+=InputArray[j];
     if (Sum<min)
     {
        min = Sum;
        Begin_Index=i;
        End_Index=Length-1;
     }
     posl_min(InputArray,Length-1,min,Begin_Index,End_Index);
  }
}
 
int main()
{
    int n;
    cout<<"Kolichestvo elementov posledovatelnosti: ";
    cin>>n;
 
    int *Array = new int[n];
    cout<<"Vvedite elementu posledovatelnosti:\n";
    for (int i = 0; i < n; i++)
        cin>>Array[i];
 
    int min = Array[0],B=0,E=0;
    posl_min(Array,n,min,B,E);
 
    cout<<"Posledovatelnost podriad iduwix elementov, summa kotorux minimalna,\n"<<
          "sostoit iz "<< E-B+1 <<" elementov(a):\n";
    for (int i=B; i<=E; i++)
       cout<<Array[i]<<" ";
    cout<<" = "<<min;
    getch();
    return 0;
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 19:04     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #8
manfeese,
Вот условие:

Цитата Сообщение от А1екс Посмотреть сообщение
В данной последовательности чисел найти подпоследовательность подряд идущих элементов, сумма которых минимальна. Реализовать с помощью рекурсивной функции.
подряд идущие элементы подпоследовательности, а не последовательности. Т.е.:
1. Есть последовательность элементов.
2. В этом наборе элементов (о которм говорится в п.1), есть какие-то подпоследовательности (а может быть их и нет совсем). Тот кто написал условие задачи, он эти подпоследовательности описывает так: "подпоследовательности подряд идущих элементов". Я это воспринял это как "подпоследовательности подряд идущих одинаковых элементов", иначе не вижу смысла!
Кстати он не жаловался на некорректное решение.
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
11.12.2009, 19:26     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #9
Я с вами согласен!!! Условие просто описано не корректно...
В моем понимании это звучит так:
Есть некая последовательность, скажем из 4 элементов{5,4,-1,9}. Всего в этой последовательности находится 10 подпоследовательностей, подряд идущих элементов:
Код
5
4
-1
9
5,4
4,-1
-1,9
5,4,-1
4,-1,9
5,4,-1,9
Ну вот из этих подпоследовательностей и надо выбрать ту, в которой их сумма манимальна, то есть -1;

Добавлено через 12 минут
Выражение "...подряд идущих элементов..." еще не означает одинаковых!!!
В примере, что я привел, допустим, подпоследовательность подряд идущих элементов 4,-1,9 последовательности 5,4,-1,9 подряд идущими считаються:
"-1" - элемент идущий за "4"
"9" - элемент идущий за "-1"
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 19:47     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #10
Выражение "...подряд идущих элементов..." еще не означает одинаковых!!!
Я с этим согласен. И писал, что это я сам принял такое решение считать именно так.

В примере, что я привел, допустим, подпоследовательность подряд идущих элементов 4,-1,9 последовательности 5,4,-1,9 подряд идущими считаються:
"-1" - элемент идущий за "4"
"9" - элемент идущий за "-1"
Я с этим не согласен (вернее согласен, но тут просто явная ошибка в написании условия), потому что тогда получается что подпоследовательность всего одна и она является всей последовательностью. А вообще-то по этому поводу спорить бессмысленно. Истину мог бы открыть в этом случае только один человек, но ему уже задачу решили, и вряд ли он сюда снова заглянет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2009, 20:25     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна
Еще ссылки по теме:

C++ Найти подпоследовательность из подряд идущих элементов с наибольшей суммой
Найти в массиве подпоследовательность из подряд идущих элементов с наибольшей суммой C++
Найти два соседних элемента массива, сумма которых минимальна C++
Найти стороны, при которых их сумма минимальна C++
Найти в последовательности, количество пар подряд идущих отрицательных элементов C++

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

Или воспользуйтесь поиском по форуму:
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
11.12.2009, 20:25     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна #11
Цитата Сообщение от valeriikozlov Посмотреть сообщение
получается что подпоследовательность всего одна
Почему одна???
Цитата Сообщение от manfeese Посмотреть сообщение
Какая длина последовательности подряд идущих элементов должна быть?
Цитата Сообщение от А1екс Посмотреть сообщение
любая
А насчет спорить дальше, я с вами согласен, все же не будем. Может все же автор заглянет как-то и разъяснит ситуацию ))))

Добавлено через 33 минуты
Условие рекурсии немного переделал...
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
36
37
38
39
40
41
42
43
44
#include <iostream.h>
#include <conio.h>
 
void posl_min(int* InputArray,int Length,int &min,int &Begin_Index,int &End_Index)
{
  for (int i = 0; i < Length; i++)
  {
     int Sum=0;
     //if (Length-i>1) // Условие для ограничения размера подпоследовательности
     for (int j=i; j < Length; j++) Sum+=InputArray[j];
     if (Sum<min)
     {
        min = Sum;
        Begin_Index=i;
        End_Index=Length-1;
     }
    if (i == 0)
       posl_min(InputArray,Length-1,min,Begin_Index,End_Index);
  }
}
 
int main()
{
    int n,Min_Index=0;
    cout<<"Kolichestvo elementov posledovatelnosti: ";
    cin>>n;
 
    int *Array = new int[n];
    cout<<"Vvedite elementu posledovatelnosti:\n";
    for (int i = 0; i < n; i++)
        cin>>Array[i];
 
    int min = Array[0],B=0,E=0;
    posl_min(Array,n,min,B,E);
 
    cout<<"Posledovatelnost podriad iduwix elementov, summa kotorux minimalna,\n"<<
          "sostoit iz "<< E-B+1 <<" elementov(a):\n";
    for (int i=B; i<=E; i++)
       cout<<Array[i]<<" ";
    cout<<" = "<<min;
 
    getch();
    return 0;
}
Yandex
Объявления
11.12.2009, 20:25     Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна
Ответ Создать тему
Опции темы

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