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

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

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

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

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

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

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

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

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

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

Рекурсивный и итеративный метод - C++
помогите пожалуйста написать программу для итеративного способа вычисления. нужно вычислить элементы последовательности a(n) = a(n...

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

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

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

СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя - C++
Помогите ребят. Не могу построить алгоритмы для этих методов Язык C++

Метод медиан из трех элементов VS улучшенный быстрый метод сортировки(метод Бентли-Макилроя) - C++
Здравствуйте! Дали весьма интересное задание. Сравнить два вышеуказанных метода сортировки для массива из 10000 элементов, результаты...

Мой код - метод бисекции, метод секущих (метод хорд) - C++
Всем привет!!! Изучаем в институте С++. Сделал код, и там, и там одна и та же проблема - при любых вбиваемых значениях программа делает...

рекурсивный алгоритм - C++
В общем я уже намучился с этим заданием... Дело такое, алгоритм составлен, но не совсем такой, какой нужен #include <iostream> #include...

Рекурсивный алгоритм - C++
помогите пожалуйста Представить в рекурсивный алгоритм Цикл пока ((proverka=1) и (k>1) ) Если A > A То Начало ...

Рекурсивный алгоритм - C++
Даны натуральные числа "N" и "M" надо решить с помощью с++ не могу переставить с этим кодом с++ #include <stdio.h> #include...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 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
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,444
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     Рекурсивный метод
Ответ Создать тему
Опции темы

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