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

Рекурсивный метод - C++

Восстановить пароль Регистрация
 
TonyKing
 Аватар для TonyKing
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
30.01.2011, 16:19     Рекурсивный метод #1
Возможно, кто-то уже решал такую задачу как подпрограмму, или еще где.
А, может, кто-то сходу видит, как это сделать.

Динамическим методом мне уже помогли тут, за что огромное спасибо.

Теперь нужно рекурсивным..

Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины. Если таких несколько, то из них нужно выбрать ту, у которой наибольшая сумма чисел.

А то беда. Сессия уже выжала все силы. Сам себе в зеркале не улыбаюсь уже
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2011, 16:19     Рекурсивный метод
Посмотрите здесь:

Рекурсивный метод для вывода на экран последовательности C++
Рекурсивный минимум C++
Рекурсивный и итеративный метод C++
C++ Сортировка выборкой. Рекурсивный метод
рекурсивный спуск C++
C++ рекурсивный алгоритм
C++ Рекурсивный способ и не рекурсивный способ
C++ Рекурсивный алгоритм F

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.01.2011, 19:34     Рекурсивный метод #2
Цитата Сообщение от TonyKing Посмотреть сообщение
Сам себе в зеркале не улыбаюсь уже
Найдите силы улыбнуться.
Если честно, то вижу что рекурсия здесь не самый оптимальный вариант, но если просите, то например так:
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>
using namespace std;
int *mas_res, i_res=0, *mas_temp, N, *mas, Sum=0;
void rec(int a, int len, int sum)
{
    int i;
    if((len>i_res) || (len==i_res && Sum<sum))
    {
        for(i=0; i<len; i++)
            mas_res[i]=mas_temp[i];
        Sum=sum;
        i_res=len;
    }
    for(i=a+1; i<N; i++)
        if(mas[a]<=mas[i])
        {
            mas_temp[len]=mas[i];
            rec(i, len+1, sum+mas[i]);
        }
}
 
int main()
{
    int i;
    cout<<"N= ";
    cin>>N;
    mas=new int[N];
    mas_res=new int[N];
    mas_temp=new int[N];
    for(i=0; i<N; i++)
    {
        cout<<"["<<i<<"]= ";
        cin>>mas[i];
    }
    for(i=0; i<N; i++)
    {
        mas_temp[0]=mas[i];
        rec(i, 1, mas[i]);
    }
    for(i=0; i<i_res; i++)
        cout<<mas_res[i]<<" ";
    cout<<endl;
    return 0;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
30.01.2011, 19:34     Рекурсивный метод #3
Проверяй:
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>
 
#define SIZE 10
 
void findSubseq(int*, int*, int**, int**, int*, int*);
void printSubseq(int*, int*, size_t);
 
int main()
{
    int seq[SIZE] = {1, 2, 1, 4, 5, 6, 5, 8, 9, 10};
    int* start = seq;
    int* end = seq;
    
    puts("Initital sequence");
    
    printSubseq(seq, seq + SIZE - 1, 0);
    puts("Its maximal not descending subsequence:");
    findSubseq(seq, seq + SIZE - 1, &start, &end, seq, seq);
    printSubseq(start, end, 0);
    
    exit(0);
}
 
int sum(int* start, int* end)
{
    if(start > end)
    return 0;
    return *start + sum(start + 1, end);
}
 
int compareSubseq(int* s1start, int* s1end,
          int* s2start, int* s2end)
{
    int len1, len2, sum1, sum2;
    len1 = s1end - s1start + 1;
    len2 = s2end - s2start + 1;
    if(len1 < len2)
    return -1;
    if(len2 < len1)
    return 1;
    sum1 = sum(s1start, s1end);
    sum2 = sum(s2start, s2end);
    if(sum1 < sum2)
    return -1;
    if(sum2 < sum1)
    return 1;
    return 0;
}
 
void findSubseq(int* start, int* end, int** maxStart, int** maxEnd, int* currStart, int* currEnd)
{
    if(start > end)
    {
    if(compareSubseq(*maxStart, *maxEnd, currStart, currEnd) < 0)
    {
        *maxStart = currStart;
        *maxEnd = currEnd;
    }
    
    return;
    }
        
    if(*start < *currEnd)
    {
    if(compareSubseq(*maxStart, *maxEnd, currStart, currEnd) < 0)
        findSubseq(start + 1, end, &currStart, &currEnd, start + 1, start + 1);
    else
        findSubseq(start + 1, end, maxStart, maxEnd, start + 1, start + 1);
    }
    findSubseq(start + 1, end, maxStart, maxEnd, currStart, start);
}
 
void printSubseq(int* start, int* end, size_t cnt)
{
    if(start > end)
    {
    printf("}[%2d]\n", cnt);
    return;
    }
    
    if(!cnt)
    fputs("{ ", stdout);
    
    printf("%d ", *start);
    printSubseq(start + 1, end, cnt + 1);
}
Yandex
Объявления
30.01.2011, 19:34     Рекурсивный метод
Ответ Создать тему
Опции темы

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