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

рекурсия - C++

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

C++ Рекурсия
C++ Рекурсия
Рекурсия! C++
Рекурсия C++
Рекурсия C++
Рекурсия C++
C++ Рекурсия
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
manfeese
 Аватар для manfeese
128 / 127 / 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
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
07.12.2009, 08:18     рекурсия #4
Пример можно ?

Если длина любая - то находишь минимум массива.
Это будет подпоследовательность подряд идущих элементов, сумма которых минимальна, причем длина подпоследовательности имеют длину 1.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 05:53     рекурсия #6
Цитата Сообщение от Deniel Посмотреть сообщение
valeriikozlov а где здесь рекурсия????
Давайте попробуем ее найти!
Может быть в определении функции void posl_min() в строке 38 моего кода? Такая рекурсия не подойдет?
manfeese
 Аватар для manfeese
128 / 127 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2009, 19:04     рекурсия #8
manfeese,
Вот условие:

Цитата Сообщение от А1екс Посмотреть сообщение
В данной последовательности чисел найти подпоследовательность подряд идущих элементов, сумма которых минимальна. Реализовать с помощью рекурсивной функции.
подряд идущие элементы подпоследовательности, а не последовательности. Т.е.:
1. Есть последовательность элементов.
2. В этом наборе элементов (о которм говорится в п.1), есть какие-то подпоследовательности (а может быть их и нет совсем). Тот кто написал условие задачи, он эти подпоследовательности описывает так: "подпоследовательности подряд идущих элементов". Я это воспринял это как "подпоследовательности подряд идущих одинаковых элементов", иначе не вижу смысла!
Кстати он не жаловался на некорректное решение.
manfeese
 Аватар для manfeese
128 / 127 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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
 Аватар для manfeese
128 / 127 / 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     рекурсия
Ответ Создать тему
Опции темы

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