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

Отдельное вычисление суммы каждой последовательности (Рекурсивный метод) - C++

Восстановить пароль Регистрация
 
gulllak
44 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 66
07.03.2014, 20:55     Отдельное вычисление суммы каждой последовательности (Рекурсивный метод) #1
Помогите, написал код по примеру учителя, но не совсем понимаю как происходит вычисление и как работает рекурсия, в с++ небольшой опыт есть, но пытаясь идти по ходу программы и вычислять параллельно на листике запутываюсь.
Вот допустим последовательность из 5 элементов:
1) [25; -4; 9; 16; -4] далее как я понимаю последовательность делится на Z1...center и Zcenter+1...n Получили ([25, -4, 9]=>[25,-4] и [9]=>[25],[-4] и [9]) и ([16, -4]=>[16] и [-4])
2) Вычисляем рекурсивно макс. сумму подпоследовательности в левой MaxSubSum3(a, left, center) и правой MaxSubSum3(a, center + 1, right) части.
3) Вычисляем рекурсивно макс. сумму подпоследовательности проходящей через центр подпоследовательности Z
{...,Zcenter,Z(center+1),...}
4) Получаем сумму sum(Левой части, правой части, центра)
Суть в том что я не понимаю как это все по коду происходит.

Вот мой код:
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
#include <stdio.h>   
#include <stdlib.h>   
#include <iostream>   
using namespace std;
 
 
 
 
int MaxSubSum3(int a[], int left, int right)
{
    int sum;
    if (left == right)
        sum = a[left]>0 ? a[left] : 0;
    else {
        int center = (left + right) / 2;
        cout << "center= " << center << endl;
        int leftsum, rightsum;
        leftsum = MaxSubSum3(a, left, center);
        rightsum = MaxSubSum3(a, center + 1, right);
 
        cout << "MaxLeftSum= " << leftsum << endl;
        cout << "MaxRightSum= " << rightsum << endl;
        cout << "Center= " << center << endl;
        int leftmidsum = 0, rightmidsum = 0;
        int S1 = 0, S2 = 0;
        for (int i = center; i >= left; i--)
        {
            leftmidsum += a[i];
            if (leftmidsum>S1)
                S1 = leftmidsum;
        } 
        for (int i = center + 1; i <= right; i++)
        {
            rightmidsum += a[i];
            if (rightmidsum>S2)
                S2 = rightmidsum;
        }  
        cout << "MaxLeftBorderSum= " << S1 << endl;
        cout << "MaxRightBorderSum= " << S2 << endl;
        sum = S1 + S2;
        if (sum<leftsum)  sum = leftsum;
        if (sum<rightsum) sum = rightsum;
 
    }  
    return sum;
 
 
}
 
void main()
 
{
    setlocale(0, "Rus");
    int a[10];
    cout << "Пожалуйста введите размер массива " << endl;
    int n;
    cin >> n;
    cout << "Пожалуйста введите элементы в массив" << endl;
    for (int i = 0; i<n; i++)
        cin >> a[i];
    cout << "Наш массив: " << endl << endl;
    cout << "----------------------" << endl;
    for (int i = 0; i<n; i++)
        cout << "  " << a[i];
    cout << endl;
    cout << "----------------------" << endl;
    cout << endl;
 
 
    cout << "Ввод данных успешен! " <<endl << endl;
    int sum = MaxSubSum3(a, 0, n - 1);
    cout << "Сумма каждой последовательности:  " << sum << endl;
    system("pause");
}
Добавлено через 45 минут
Как работает рекурсия так и не могу понять(((
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2014, 20:55     Отдельное вычисление суммы каждой последовательности (Рекурсивный метод)
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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