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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Задача 1)фамилии студентов, которые имеют две и больше двоек в сессию на заданном пользователем факультете и удалить их http://www.cyberforum.ru/cpp-beginners/thread1113645.html
Задача Создать массив структур, каждая из которых состоит из следующих элементов: факультет, курс, группа, фамилии студентов, экзаменационные оценки. Реализовать запросы, определив: 1)фамилии студентов, которые имеют две и больше двоек в сессию на заданном пользователем факультете и удалить их 2)факультет на котором на первом курсе наибольшее количество отличников. НЕ МОГУ СДЕЛАТЬ первое...
C++ C \ C++ и AS 3.0 Привет. Подскажите, имеется ли возможность взаимодействия С\С++ и AS 3.0. http://www.cyberforum.ru/cpp-beginners/thread1113639.html
Задача на Timus Online Judge, C++. Решена, но C++
Решил задачу, но выдает ошибку WA на 2 тесте. Не могу даже представить, в чем дело. Задача: 1100. Таблица результатов Ограничение времени: 1.0 секунды Ограничение памяти: 16 МБ Старое программное обеспечение для проведения соревнований использует пузырьковую сортировку для создания таблицы результатов. Однако сейчас команд слишком много, и программное обеспечение работает слишком медленно....
C++ Opencv размеры обучающих образцов
Будет ли приемлемым результат обучения в случае одинаковых размеров и позитивных и негативных обучающих образцов ?
C++ Длинная арифметика. Сложение http://www.cyberforum.ru/cpp-beginners/thread1113606.html
Есть класс BigInt со скрытыми переменными uint32* m_integer и uint32 m_length, которые отвечают за само число и его длину соответственно. Я реализовал оператор +. Укажите, пожалуйста, на ошибки в реализации (кроме <cstring>) -- как можно было сделать лучше (быстрее)? BigInt BigInt::operator+(const BigInt& rhs) const { if (m_length == 0 || rhs.m_length == 0) throw "Empty number in...
C++ Генерация случайных чисел Здравствуйте, появилась такая проблема: при генерации случайного числа функцией rand(); мне нужно сгенерировать 5 случайных чисел, но они все одинаковые, если написать вот так: srand(time(NULL)); то числа будут меняться только при перезапуске, но всё равно все будут одинаковые подробнее

Показать сообщение отдельно
gulllak
44 / 0 / 0
Регистрация: 09.10.2012
Сообщений: 66
07.03.2014, 20:55     Отдельное вычисление суммы каждой последовательности (Рекурсивный метод)
Помогите, написал код по примеру учителя, но не совсем понимаю как происходит вычисление и как работает рекурсия, в с++ небольшой опыт есть, но пытаясь идти по ходу программы и вычислять параллельно на листике запутываюсь.
Вот допустим последовательность из 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 минут
Как работает рекурсия так и не могу понять(((
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 10:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru