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

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

Восстановить пароль Регистрация
 
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
08.06.2010, 23:25     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #1
В произвольном массиве нужно найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна.
Размер массива: 200, диапазон : от -100 до 100.

помогите! завтра зачет! ....погибаю...
)

спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2010, 23:25     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна
Посмотрите здесь:

C++ Поиск поселдовательности в массиве, сумма элементов которой максимальна
C++ Найти непрерывную последовательность положительных чисел, сумма элементов которой максимальна
C++ Найти строку, в которой сумма модулей элементов максимальна и назвать её номер
C++ Массив: Найти такую неразрывную последовательность положительных чисел, сумма элементов у которой максимальная.
В заданном 2-м массиве найти индекс строки,сумма элементов которой максимальна C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
НеПродюссер
 Аватар для НеПродюссер
32 / 20 / 3
Регистрация: 05.03.2010
Сообщений: 51
08.06.2010, 23:29     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #2
что такое позитивные числа??=)
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
08.06.2010, 23:31  [ТС]     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #3
Цитата Сообщение от НеПродюссер Посмотреть сообщение
что такое позитивные числа??=)
позитивные - имеется в виду, что положительные )
НеПродюссер
 Аватар для НеПродюссер
32 / 20 / 3
Регистрация: 05.03.2010
Сообщений: 51
08.06.2010, 23:35     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include "stdafx.h"
#include <iostream>
using namespace std;
 
void main() {
  int size = 200;
  int a[size];
  for (int i = 0; i < size; scanf("%d", a[i++]));
  
  for (int i = 0; i < size; printf("%d", a[i++]));
  system("PAUSE");
}
это введения и выведения массива=)

Добавлено через 17 секунд
сейчас допишу=)
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
08.06.2010, 23:42     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #5
НеПродюссер, во-первых размер статического массива должен быть константой, а во-вторых 200 элементов вводить - это если только сильно заняться нечем...
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
08.06.2010, 23:47  [ТС]     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #6
Цитата Сообщение от НеПродюссер Посмотреть сообщение
сейчас допишу=)
да-да, спасибо большое!. только, если не ошибаюсь, при выводе массива нужно использовать "рандомайз" с ограничением от -100 до 100. но это мелочи, в этой части я еще более менее.

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


спасибо за ваше внимание !)

Добавлено через 1 минуту
Цитата Сообщение от easybudda Посмотреть сообщение
НеПродюссер, во-первых размер статического массива должен быть константой, а во-вторых 200 элементов вводить - это если только сильно заняться нечем...
да, я про это же.
но это я и сама смогу задать..

тяжело дается именно вторая часть задания
(повторно только что описаная выше)...

помогите, если разбираетесь. пожалуйста...
НеПродюссер
 Аватар для НеПродюссер
32 / 20 / 3
Регистрация: 05.03.2010
Сообщений: 51
08.06.2010, 23:53     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #7
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
#include "stdafx.h"
#include <iostream>
using namespace std;
 
void getMax(int *a, int size, int &sum, int index) {
  int locSum = 0;  
  for (int j = i; j < size, a[j] > 0; j++) {
    locSum = locSum + a[j];
  if (locSum > sum) {
    sum := locSum;
  }
   return;
}
         
int getValue() {
  int value;
  do {
       scanf("%d", value);
  } while ((value < -100) || (value > 100));
  return value;
}
 
void main() {
  int size = 200;
  int a[size];
  for (int i = 0; i < size; a[i++] = getValue());
  int sum = 0;
  for (int i = 0; i < size; i++) {
    if ((a[i] > 0) && (a[i - 1] <= 0)) {
      getMax(a,  size, sum, i);
  printf("%d ", sum);
  for (int i = 0; i < size; printf("%d", a[i++]));
  system("PAUSE");
}
Добавлено через 1 минуту
Цитата Сообщение от easybudda Посмотреть сообщение
во-первых размер статического массива должен быть константой, а во-вторых 200 элементов вводить - это если только сильно заняться нечем...
полностью с Вами согласен, но сам учусь в университете и много раз писал другим людям лабы, которые у них принимали именно, чем проще код и чем он очевиднее=) понимаете о чем я??=)

Добавлено через 1 минуту
если не то, обязательно напишите - перепишу=)
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
09.06.2010, 00:18  [ТС]     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #8
Цитата Сообщение от НеПродюссер Посмотреть сообщение
если не то, обязательно напишите - перепишу=)
такой вопрос. я пишу в borland 3.1
он ругается на первые три строчки
#include "stdafx.h"
#include <iostream>
using namespace std;
говорит, что не знает таких директив.

принтскрин во вложениях.

подскажите, как можно это изменить?
Миниатюры
Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна  
НеПродюссер
 Аватар для НеПродюссер
32 / 20 / 3
Регистрация: 05.03.2010
Сообщений: 51
09.06.2010, 00:30     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #9
блин, я писал на C++, в спецификациях чистого С к сожалению не разбираюсь...извините=)

Добавлено через 1 минуту
возможно, попробуйте так=)

C
1
#include <iostream.h>
остальные строки не пишите вообще=)

Добавлено через 1 минуту
оу, Borland 3.1 - это С++, попробуйте, как я написал=)
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
09.06.2010, 00:44  [ТС]     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #10
Цитата Сообщение от НеПродюссер Посмотреть сообщение

возможно, попробуйте так=)

C
1
#include <iostream.h>
улыбнуло )
на самом деле, пыталась.
теперь уже придирается к синтаксису.
сейчас вникаю в суть вами написанного и пробую на основе сотворить что-нибудь свое.
вся ночь, как говорится, впереди)

спасибо за ваше время.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
09.06.2010, 00:53     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Есть нюанс: 0 считается чётным беззнаковым числом. Он должен последовательность прерывать? Если нет, то вот:
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <cstdlib>  
#include <ctime>
 
// В произвольном массиве нужно найти такую непрерывную последовательность положительных чисел, 
// сумма элементов в которой максимальна.
// Размер массива: 200, диапазон : от -100 до 100.
 
int rand_num(){
    return rand() % 201 - 100;
}
 
int main(){
    const int SIZE = 200;
    int arr[SIZE];
    
    srand(time(NULL));
    std::generate(arr, arr + SIZE, rand_num);
    
    std::vector<int> pos, max_pos;
    int sum, max_sum = 0;
    for ( int i = 0; i < SIZE; ++i ){
        if ( arr[i] < 0 ){
            if ( ! pos.empty() ){
                if ( ( sum = std::accumulate(pos.begin(), pos.end(), 0) ) > max_sum ){
                    max_sum = sum;
                    max_pos = pos;
                }
                pos.clear();
            }
        }
        else
            pos.push_back(arr[i]);
    }
    std::cout << "Max sum of positive elements continuous sequence is:" << std::endl;
    std::copy(max_pos.begin(), max_pos.end(), std::ostream_iterator<int>(std::cout, " + "));
    std::cout << "\b\b\b = " << max_sum << std::endl;
    
    std::cout << "Print all array? (y/n): ";
    char c;
    std::cin >> c;
    if ( c == 'y' || c == 'Y' )
        std::copy(arr, arr + SIZE, std::ostream_iterator<int>(std::cout, "\t"));
    
    return 0;
}
если 0 прерывать последовательность должен, то нужно
C++
1
if ( arr[i] < 0 )
заменить на
C++
1
if ( arr[i] < 1 )
Добавлено через 57 секунд
а в прочем дремучим борландовским компилятором скорее всего ни так, ни эдак не скомпилится...
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
09.06.2010, 01:04  [ТС]     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #12
так и есть.
ругается на синтаксис.
в особенности на std::, pos.begin(), pos.end(), std::copy(arr, arr + SIZE, std::ostream_iterator<int>(std::cout, " ")) и т. д.

что ж, увы ..
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
09.06.2010, 01:17     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #13
люSька, а тут ему замену подыскать - не? Тогда разве-что картинку показать могу...
Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
09.06.2010, 01:30  [ТС]     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #14
дада. это именно оно !!

если вам не сложно - не могли бы вы словесно объяснить сам принцип вывода суммы этой последовательности?
все остальное , думаю, смогу реализовать сама

а замену искать не могу. к сожалению,
от меня требуется код, адаптированный именно под этот замечательный борланд.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
09.06.2010, 01:40     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #15
люSька, пока числа в массиве положительные, они копируются в контейнер pos. При встрече отрицательного числа, если контейнер pos содержит элементы, вычисляется сумма элементов контейнера, если она больше max_sum, весь контейнер оптом копируется в контейнер max_pos, а сам контейнер pos очищается. А потом просто выводится контейнер max_pos через разделители " + ", последний + затирается "\b\b\b = " и выводится максимальная сумма элементов
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
09.06.2010, 03:17     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #16
Сообщение было отмечено автором темы, экспертом или модератором как ответ
люSька, вот Вам примерно то же самое на С - должно бы скомпилироваться. Длинно, сложно и запутанно, за то с красивостями
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef struct NODE {
    int val;
    struct NODE * next;
} node_t;
 
node_t * new_node(int val, node_t * last){
    node_t * node;
    
    if ( ( node = (node_t*)malloc(sizeof(node_t)) ) == NULL )
        return NULL;
    node->val = val;
    node->next = NULL;
 
    if ( last )
        last->next = node;
 
    return node;
}
 
void print_nodes_sum(const node_t * node){
    int sum = 0;
    while ( node ){
        printf("%d%s", node->val, ( node->next ) ? " + " : " = ");
        sum += node->val;
        node = node->next;
    }
    printf("%d\n", sum);
}
 
void delete_nodes(node_t * node){
    node_t * tmp;
    while ( node ){
        tmp = node->next;
        free(node);
        node = tmp;
    }
}
 
int rand_num(){
    return rand() % 201 - 100;
}
 
void print_array(const int * arr, int size){
    int i;
    
    printf("Print all array? (y/n): ");
    if ( ( i = getchar() ) != 'y' && i != 'Y' )
        return;
    
    for ( i = 0; i < size; ++i )
        printf("%4d%s", arr[i], ( ( i + 1 ) % 16 ) ? " " : "\n");
    printf("\n");
}
 
#define ARR_SIZE 200
 
int main(void){
    int arr[ARR_SIZE], i, cur_sum, max_sum;
    node_t * cur_first, * cur_last, * max_first;
    
    cur_first = cur_last = max_first = NULL;
    cur_sum = max_sum = 0;
    srand(time(NULL));
    for ( i = 0; i < ARR_SIZE; ++i )
        arr[i] = rand_num();
    
    for ( i = 0; i < ARR_SIZE; ++i ){
        if ( arr[i] < 0 ){
            if ( cur_sum ){
                if ( cur_sum > max_sum ){
                    if ( max_first )
                        delete_nodes(max_first);
                    max_first = cur_first;
                    max_sum = cur_sum;
                }
                else
                    delete_nodes(cur_first);
                cur_first = cur_last = NULL;
                cur_sum = 0;
            }
        }
        else {
            if ( ( cur_last = new_node(arr[i], cur_last) ) == NULL ){
                fprintf(stderr, "Can't create a new node!\n");
                exit(EXIT_FAILURE);
            }
            if ( ! cur_first )
                cur_first = cur_last;
            cur_sum += arr[i];
        }
    }
    if ( cur_sum > max_sum ){
        if ( max_first )
            delete_nodes(max_first);
        max_first = cur_first;
    }
    
    if ( ! max_first ){
        if ( cur_first ){
            printf("No negative elements in array!\n");
            printf("Sum of all elements: %d\n", cur_sum);
            delete_nodes(cur_first);
        }
        else
            printf("Can't find any positive sentence!\n");
    
        print_array(arr, ARR_SIZE);
        exit(EXIT_SUCCESS);
    }
    
    printf("Max sum of positive elements continuous sequence is:\n");
    print_nodes_sum(max_first);
    
    print_array(arr, ARR_SIZE);
    
    if ( cur_first != NULL && cur_first != max_first )
        delete_nodes(cur_first);
    delete_nodes(max_first);
    
    exit(EXIT_SUCCESS);
}
Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна
НеПродюссер
 Аватар для НеПродюссер
32 / 20 / 3
Регистрация: 05.03.2010
Сообщений: 51
09.06.2010, 12:12     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #17
всегда пожалуйста=) девушки-программисты - это святое, так что надо помогать=)
люSька
0 / 0 / 0
Регистрация: 08.06.2010
Сообщений: 11
09.06.2010, 21:08  [ТС]     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #18
улыбнуло : ) спасибо, коллеги)

показываю, до чего дошла сама.
единственный момент - с выводом на экран проблема. знаю, смешно)
возможно, просто уже туплю или невнимательничаю.
так вот, мне нужно вывести макс. послед. положительных чисел, а выводит оно последний положительный элемент. в чем причина?

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
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <graphics.h>
#include <iostream.h>
 int M[200];
 
int main(void) {
 int i, j;
 int sum;
 int max;
 int start_index=0, amount_max=1;
 
clrscr();
  randomize();
  for (i=0; i<200; M[i++]=random(201)-100 );
 
  printf("Array:\n");
  for (i=0; i<200; printf("%3d  ",M[i++]));
 
  putchar('\n');
  putchar('\n');
 
 
for (i=0; i<200;i++) {
if (M[i]<0) continue;
 
int max_sum=M[0];
int curr_amount=1;
int curr_sum=M[i];
int curr_index=i;
 
 
for (int j=i+1; j<200 && M[j-1] < M[j] && M[j] >0; j++)
{curr_sum+=M[j];
curr_amount++;
 
}
if (curr_sum>max_sum)
{
max_sum=curr_sum;
start_index=curr_index;
amount_max=curr_amount;
}
if (curr_amount>2)
i=i+(curr_amount-2);
}
//vyvod na druk
for (int k=start_index; k<(start_index+amount_max); k++) {
cout<<M[k]<<endl;
}
 
 
getche();
return 0;
            }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2010, 01:07     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна
Еще ссылки по теме:

C++ Определить номер столбца квадратной матрицы, сумма элементов которой максимальна
C++ Номер строки, сумма элементов которой максимальна
C++ Номер строки квадратной матрицы, сумма элементов которой максимальна

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

Или воспользуйтесь поиском по форуму:
НеПродюссер
 Аватар для НеПродюссер
32 / 20 / 3
Регистрация: 05.03.2010
Сообщений: 51
10.06.2010, 01:07     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна #19
возможно, все из-за того, что в for стоит меньше=) хотя было бы правильно в данной ситуации меньше или равно, ибо у Вас не размер, а конкретный индекс и до него надо дойти=)

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

вообщем, так

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
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
#include <graphics.h>
#include <iostream.h>
 int M[200];
 
int main(void) {
 int i, j;
 int sum;
 int max;
 int start_index=0;
 amount_max=1;
 
clrscr();
  randomize();
  for (i=0; i<200; M[i++]=random(201)-100 );
 
  printf("Array:\n");
  for (i=0; i<200; printf("%3d  ",M[i++]));
 
  putchar('\n');
  putchar('\n');
 
 
for (i=0; i<200;i++) {
if (M[i]<0) continue;
 
int max_sum=M[0];
int curr_amount=1;
int curr_sum=M[i];
int curr_index=i;
 
 
for (int j=i+1; j<200 && M[j-1] < M[j] && M[j] >0; j++)
{curr_sum+=M[j];
curr_amount++;
 
}
if (curr_sum>max_sum)
{
max_sum=curr_sum;
start_index=curr_index;
amount_max=curr_amount;
}
if (curr_amount>2)
i=i+(curr_amount-2);
}
//vyvod na druk
for (int k=start_index; k<=(start_index+amount_max); printf("%d ", M[k++], "\n"));
_getch();
return 0;
}
вот примерно так=)
Yandex
Объявления
10.06.2010, 01:07     Найти такую непрерывную последовательность положительных чисел, сумма элементов в которой максимальна
Ответ Создать тему
Опции темы

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