0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
1

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

30.01.2011, 16:19. Показов 1264. Ответов 2
Метки нет (Все метки)

Возможно, кто-то уже решал такую задачу как подпрограмму, или еще где.
А, может, кто-то сходу видит, как это сделать.

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

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

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

А то беда. Сессия уже выжала все силы. Сам себе в зеркале не улыбаюсь уже
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.01.2011, 16:19
Ответы с готовыми решениями:

Рекурсивный метод
Помогите доделать пожалуйста #include <iostream> #include<math.h> #include<conio.h> ...

Рекурсивный и итеративный метод
помогите пожалуйста написать программу для итеративного способа вычисления. нужно вычислить...

Рекурсивный метод нахождения корня
Здравствуйте. В университете дали задание: "Вычислить значение Х = корень из а используя формулу...

Сортировка выборкой. Рекурсивный метод
Код моей функции, но он мне не нравится из-за трех переменных. Ненавижу что-то добавлять. Так как...

2
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
30.01.2011, 19:34 2
Лучший ответ Сообщение было отмечено TonyKing как решение

Решение

Цитата Сообщение от 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;
}
1
Эксперт С++
5825 / 3476 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
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);
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.01.2011, 19:34
Помогаю со студенческими работами здесь

Рекурсивный метод вычисления определителя матрицы
суть в том, что не получается реализовать рекурсивный метод Determinant в классе Matrix. ...

Рекурсивный метод для вывода на экран последовательности
Дано натуральное число n. Разработать рекурсивный метод для вывода на экран следующей...

Разработать рекурсивный метод для вывода символами треугольника
****** ***** **** *** ... * Рекурсия обязательна.Помогите пжс

Рекурсивный метод, выводящий все возможные разложения натурального числа n на множители
Разработать рекурсивный метод для вывода на экран всех возможных разложений натурального числа n на...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru