Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
1

Массив: Найти такую неразрывную последовательность положительных чисел, сумма элементов у которой максимальная.

11.04.2013, 16:40. Просмотров 1733. Ответов 21
Метки нет (Все метки)

Найти такую неразрывную последовательность положительных чисел, сумма элементов у которой максимальная.

ну вот я сделал, но только будет работать, если есть только один отрицательный элемент.
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
#include<iostream>
#include<conio.h>
using namespace std;
 
int main()
 {
          const int n=8;
          int i,a[n],z,c,p,d,k;
          
          cout<<"vvod elem massiva"<<endl;
          for (i=0;i<n;i++)
           cin>>a[i];
           z=0; c=0;
           for (i=0;i<p;i++)
            if (a[i]>0)
            z=z+a[i];
        else p=i; k=0;
         for (i=p+1;i<n;i++)
           if (a[i]>0) 
         d=d+a[i];
         if (z>d)
         
          for (i=0;i<p;i++)
          cout<<a[i]<<"    ";
          else  
           
          for (i=p+1;i<n;i++)
          cout<<a[i]<<"    ";
          
        getch();
       return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.04.2013, 16:40
Ответы с готовыми решениями:

Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна
В произвольном массиве нужно найти такую непрерывную последовательность...

Найти ту непрерывную последовательность положительных чисел, сумма элементов которой максимальна
Найти ту непрерывную последовательность положительных чисел, сумма элементов в...

Найти непрерывную последовательность положительных чисел, сумма элементов которой максимальна
Знайти таку нерозривну послыдовнысть позитивних чисел сума елементыв якый...

Дано двумерный массив целых чисел. Найти номер строки, в которой сумма отрицательных нечетных элементов наибольшая
помогите Пожалуста с задачей я не знаю как правильно прописать, чтоб он выводил...

Найти строку матрицы, в которой сумма положительных элементов максимальна
Разработать программу, которая формирует двумерный массив L размером N x M...

21
yoghurt92
375 / 346 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
11.04.2013, 16:50 2
myxayan, а выводить только сумму или еще индексы?
0
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
11.04.2013, 16:51  [ТС] 3
не, вот надо вывести просто ряд элементов, у которых сумма максимальна, хотя думаю сумма тоже не помешает)
0
yoghurt92
375 / 346 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
11.04.2013, 17:08 4
myxayan, ща посмотрю)

Добавлено через 14 минут
myxayan, вот посмотри, вдруг что-то не так, скажи)

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
#include <iostream>
#include <iomanip>
#include <array>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <functional>
using namespace std;
 
bool pred(int elem){
    return elem > 0;
}
 
int main()
{
    array<int, 10> coll;
 
    cout << "Enter the array: ";
    for(int i = 0; i < 10; ++i)
        cin >> coll[i];
 
    cout << "\nSource array: " << setw(15 - strlen("Source array"));
    copy(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "));
 
    int max, num;
    array<int, 10>::iterator pos1, pos2, pos3, pos4,
        it = coll.begin();
 
    pos1 = find_if(coll.begin(), coll.end(), pred);
 
    if(pos1 != coll.end()){
        pos2 = find_if(pos1 + 1, coll.end(), not1(ptr_fun(pred)));
 
        pos3 = pos2;
        max = accumulate(pos1, pos2, 0);
 
        while(it != coll.end()){
            pos3 = find_if(pos3, coll.end(), pred);
 
            if(pos3 != coll.end()){
                pos4 = find_if(pos3 + 1, coll.end(), not1(ptr_fun(pred)));
 
                num = accumulate(pos3, pos4, 0);
 
                if(max < num){
                    max = num;
                    pos1 = pos3;
                    pos2 = pos4;
                }
                
                if(pos4 != coll.end()){
                    it = pos4; 
                    ++it;
                    pos3 = it;
                }
                else
                    break;
            }
            else
                break;
        }
 
        if(pos2 != coll.end()){
            cout << "\nNumber of elements: ";
            copy(pos1, pos2, ostream_iterator<int>(cout, " "));
        }
    }
 
    cout << "\n\n";
    return 0;
}
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 17:11 5
myxayan, эта задача делается через 2 указателя, и при малых n через квадратную динамику. Скажите ограничения на задачу (время память max n)
0
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
11.04.2013, 17:14  [ТС] 6
Ternsip, да знаю, учитель сказала, что нужно 1 положительный эл. запомнить и последний, и потом както чудить, но я както не додумал.
и не знаю как запомнить первый, такто последний вроде запоминается, у меня это p.
C++
1
else p=i;
но а так не знаю, что дальше..
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 17:17 7
myxayan, повторюсь, скажите ограничения.
0
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
11.04.2013, 17:19  [ТС] 8
yoghurt92, хм, но мне кажется, что учитель заметит, чтото тут сильно расписано, мы только в феврале начали изучать с++, закончили циклы недавно.
и еще я через dev c++ пишу, так он выдает ошибки разные.
0
Миниатюры
Массив: Найти такую неразрывную последовательность положительных чисел, сумма элементов у которой максимальная.  
yoghurt92
375 / 346 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
11.04.2013, 17:23 9
myxayan, сейчас перепишу просто.
0
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
11.04.2013, 17:25  [ТС] 10
Ternsip, что такое квадратная динамика? хх
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 17:27 11
myxayan, это когда вы делаете полный перебор очень быстро, запоминая ответ (сумму) с i по j клетки. Но вы проигнорировали меня и не сказали ограничения.
0
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
11.04.2013, 17:36  [ТС] 12
просто занят еще другой программой.
Цитата Сообщение от Ternsip Посмотреть сообщение
(время память max n)
в самой задачи ограничений нет, и учитель не говорил ничего.
даже впервые услышал от вас.
время - вроде никаких нет ограничений, но для такой задачи вроде много времени и не надо.
память - тоже самое
max -любое число максимальное.
n - тоже в принципе любое, но я вот сделал 8.
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 18:04 13
myxayan, Способ решения из раздела "Ленивое программирование"
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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <tuple>
 
using namespace std;
 
const int NMAX = 100;
vector < vector <int> > ans(NMAX, vector <int> (NMAX, -1));
vector < int > a(NMAX);
int bi = 0, bj = 0;
 
int solv(int i, int j){
    if (i > j)
        return 0;
    if (ans[i][j] != -1)
        return ans[i][j];
    ans[i][j] = solv(i+1, j) + a[i];
    if (ans[bi][bj] < ans[i][j]){
        bi = i;
        bj = j;
    }
    return ans[i][j];
}
 
 
int main(){         
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    ans[0][0] = a[1];
    for (int i = 0; i < n; i++)
        solv(0, i);
    printf("from %d to %d sum = %d", bi+1, bj+1, ans[bi][bj]); // один-индексация
    return 0;
}
0
yoghurt92
375 / 346 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
11.04.2013, 18:06 14
myxayan,

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
#include <iostream>
#include <iomanip>
using namespace std;
 
int main()
{
    const int size(10);
    int mas[size], sum(0),
        num(0), idx, jdx, idx_s, jdx_s;
 
    cout << "Enter the array: ";
    for(int i = 0; i < size; ++i)
        cin >> mas[i];
 
    cout << "\nSource array: " << setw(15 - strlen("Source array"));
    for(int i = 0; i < size; ++i)
        cout << mas[i] << ' ';
 
    for(int i = 0; i < size; ++i){
        if(mas[i] > 0){
            idx = i;
            break;
        }
    }
 
    if(idx < size){
        for(int i = 0; i < size; ++i){
            if(mas[i] < 0){
                jdx = i;
                break;
            }
        }
    }
 
    idx_s = jdx;
    for(int i = idx; i < jdx; ++i)
        sum += mas[i];
 
    while(idx_s < size){
        for(int i = idx_s; i < size; ++i){
            if(mas[i] > 0){
                idx_s = i;
                break;
            }
        }
 
        if(idx_s < size){
            bool flag(false);
            for(int i = idx_s; i < size; ++i){
                if(mas[i] < 0){
                    jdx_s = i;
                    flag = true;
                    break;
                }
            }
 
            if(!flag)
                jdx_s = size;
        }
 
        num = 0;
        for(int i = idx_s; i < jdx_s; ++i)
            num += mas[i];
 
            if(sum < num){
                sum = num;
                idx = idx_s;
                jdx = jdx_s;
            }
                
            if(jdx_s == size)
                break;
            else
                idx_s = jdx_s;
    }
 
 
    cout << "\nNumber of elements: ";
    for(int i = idx; i < jdx; ++i)
        cout << mas[i] << ' ';
 
 
    cout << "\n\n";
    return 0;
}
1
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
11.04.2013, 18:12  [ТС] 15
Спасибо)
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 18:15 16
myxayan, Если вам помогли, есть кнопочка (+1 Спасибо)
0
yoghurt92
375 / 346 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
11.04.2013, 18:26 17
Ternsip, я посмотрел вашу программу и ввел 10 чисел 1 2 3 4 -5 6 7 8 -9 10, должно выдать 6 7 8, но ваша программа выдает от 1 до 9 элемента, это же не правильно...
0
Ternsip
664 / 192 / 29
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 18:28 18
yoghurt92, оу я и забыл, что числа должны быть положительными в промежутке, спасибо) сейчас пофикщю
0
myxayan
3 / 3 / 8
Регистрация: 16.10.2012
Сообщений: 93
11.04.2013, 18:30  [ТС] 19
Точно забыл, сейчас будет +1)
0
yoghurt92
375 / 346 / 113
Регистрация: 17.05.2012
Сообщений: 1,049
11.04.2013, 18:33 20
Ternsip, да все мы не идеальны)
0
11.04.2013, 18:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2013, 18:33

Выполнить сортировку элементов в той строке матрицы сумма элементов в которой максимальная
как я могу писать эту задачу. Задана матрица целых чисел. Выполнить сортировку...

Вывести номер строки в массиве, сумма чисел которой максимальная
Пользователь вводит элементы двумерного массива. Необходимо вывести номер...

Найти такую точку, сумма расстояний от которой до остальных минимальна
Добрый всем день. Помогите мне решить данное задание , я плохо разбираюсь в...


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

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

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