Подсчитать сумму всех элементов, имеющих положительные значения O(n)

@Кристина 1998 · Регистрация: 13.09.2016

Студворк — интернет-сервис помощи студентам

Используя память, пропорциональную n, хранить массив целых чисел
A, содержащий n элементов.
Элементы массива A могут принимать случайные значения от
-((n div 2) - 1) до (n div 2). То есть, если в массиве хранится 10 элементов, то
эти элементы должны быть в диапазоне от -4 до 5.
Разработать алгоритм, который осуществляет заполнение массива A
случайными значениями, и по выбору пользователя выполняет одну из двух
функций.
Подсчитать сумму всех элементов, имеющих положительные значения O(n)

@Кристина 1998 · 14.09.2017, 15:00 **[ТС]**

bormant, объясните , пожалуйста, чем отличается код если сложности разные?
Например, написать программу со сложность O(n),а потом меняем на O(n^2)?

Добавлено через 15 секунд
bormant, объясните , пожалуйста, чем отличается код если сложности разные?
Например, написать программу со сложность O(n),а потом меняем на O(n^2)?

Добавлено через 28 минут

Сообщение от CoderHuligan

#define MIN_RAND (-((N/2)-1))
#define MAX_RAND (N/2)
#define bounded_rand(minVal, maxVal) \
*( rand() % ((maxVal) - (minVal) + 1) + (minVal) )//aka easybudda

можете объяснить вот эти строчки?

Добавлено через 9 минут

Сообщение от CoderHuligan

2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
#define MIN_RAND (-((N/2)-1))
#define MAX_RAND (N/2)
#define bounded_rand(minVal, maxVal) \
*( rand() % ((maxVal) - (minVal) + 1) + (minVal) )//aka easybudda
//функция для вычисления суммы элементов
int sum_elem(int* a, int len)
{
* * int i, sum=0;
* * for(i=0; i<len; ++i)
* * * * if(a[i]>0)sum+=a[i];
* * return sum;
}
//конец функции
int main(void)
{
* * srand(time(NULL));
* * int A[N], i;
for(i=0; i<N; ++i)
* * * * A[i]=bounded_rand(MIN_RAND, MAX_RAND);//заполняем массив случайными числами
for(i=0; i<N; ++i)//выводим массив на экран
* * * * printf("%d ", A[i]);
printf("\nSumma pol. elementov = %d\n", sum_elem(A, N));//вызываем функцию подсчёта и выводим результат
return 0;
}

Рассчитываю сложность кода подсчитываем теоретические сложность алгоритма. Разработанный
алгоритм использует следующие данные: один массив размерность N , три переменных целого типа.
v = N*C(int) + 3*C(int) C(int) – константа, характеризующая объем памяти, отводимый под
переменную целого типа.
Теоретическая пространственная сложность алгоритма составляет:
V(n) = O(v) = O(max( O(N*C(int)), O(3*C(int))) =
O(max( O(n), O(1))) = O(n) Правильно ли это и не подскажете , как теоретическую сложность считать ?

@CoderHuligan · 14.09.2017, 16:11

Сообщение от Кристина 1998

можете объяснить вот эти строчки?

Это определения макросов препроцессора Си.
Макрос открывается строчкой #define, затем через пробел следует так называемое макроопределение, желательно заглавными буквами, чтобы было понятно, что это макроопределение. Через пробел далее следует строка, которая будет подставлена в листинге программы вместо макроопределения.

Сообщение от Кристина 1998

Теоретическая пространственная сложность алгоритма составляет

Честно говоря, я этим не занимался.

@Кристина 1998 · 15.09.2017, 23:27 **[ТС]**

CoderHuligan, не могу понять почему мы макроопределяем эти строки именно так

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
MIN_RAND (-((N/2)-1))(-((N/2)-1)) и MAX_RAND (N/2)? и почему там черта  \
 ( rand() % ((maxVal) - (minVal) + 1) + (minVal) )?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
#define MIN_RAND (-((N/2)-1))
#define MAX_RAND (N/2)
#define bounded_rand(minVal, maxVal) \
 ( rand() % ((maxVal) - (minVal) + 1) + (minVal) )//aka easybudda
int sum_elem(int* a, int len)
{
    int i, c=0;
    for(i=0; i<len; ++i)
        if(a[i]>0)c+=1;
    return c;
}
int main(void)
{
    srand(time(NULL));
    int A[N], i;
 
    for(i=0; i<N; ++i)
        A[i]=bounded_rand(MIN_RAND, MAX_RAND);
 
    for(i=0; i<N; ++i)
        printf("%d ", A[i]);
 
    printf("\nSumma pol. elementov = %d\n", sum_elem(A, N));
 
    return 0;
}

Добавлено через 8 минут
CoderHuligan, и можете, пожалуйста, в этот код добавить функцию подсчёта количество элементов с отрицательными значениями вот я написала, если я не ошибаюсь в написании(если мы считаем вывод рандомных чисел в main его надо в функции прописывать?):

C
1
2
3
4
5
6
7
8
9
int pos=0;
int neg=0;
for(i=0;i<N;i++)
{
printf("%d", A[i]);
if (A[i] > 0) pos += 1;
else if (A[i] < 0) neg += 1;
}
    printf("Отрицательных: %d\n", neg);

@LazySlacker · 16.09.2017, 00:39

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 20
 
int main(void)
{
    srand(time(NULL));
    int arr[N];
    for (int i = 0; i < N; ++i)
    {
        printf("%d ", arr[i] = rand() % N - N / 2 + 1);
    }
    int neg = 0;
    int pos = 0;
    for (int i = 0; i < N; ++i)
    {
        switch ((arr[i] > 0) - (arr[i] < 0))
        {
            case -1: ++neg; break;
            case 1: ++pos; break;
        }
    }
    printf("\nnegatives = %d, positives = %d\n", neg, pos);
    return 0;
}

@Кристина 1998 · 16.09.2017, 10:09 **[ТС]**

LazySlacker, спасибо, но мне эти программы в двух функциях надо сделать, где первая- Подсчитать сумму всех элементов, имеющих положительные значения O(n).вторая- подсчёта количество элементов с отрицательными значениями О(1)

@CoderHuligan · 16.09.2017, 11:29

Сообщение от Кристина 1998

CoderHuligan, не могу понять почему мы макроопределяем эти строки именно так

Потому что так в вашем задании:

Сообщение от Кристина 1998

Элементы массива A могут принимать случайные значения от
-((n div 2) - 1) до (n div 2).

Можно обойтись и без макросов, однако так красивее и понятнее.

Сообщение от Кристина 1998

и почему там черта *\

Черта - это слэш. Он означает переход на новую строку. Это удобно для того, чтобы всё макроопределение уместилось на одном экране.

Сообщение от Кристина 1998

CoderHuligan, и можете, пожалуйста, в этот код добавить функцию подсчёта количество элементов с отрицательными значениями вот я написала, если я не ошибаюсь в написании(если мы считаем вывод рандомных чисел в main его надо в функции прописывать?):

В функции ничего не надо прописывать за исключением того, что она должна делать. Вот вариант с дополнительной функцией и без макросов, чтобы не пугать препода:

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
int sum_pol_elem(int* a, int len)
{
    int i, c=0;
    for(i=0; i<len; ++i)
        if(a[i]>0)c+=1;
    return c;
}
 
int sum_otr_elem(int* a, int len)
{
    int i, c=0;
    for(i=0; i<len; ++i)
        if(a[i]<0)c+=1;
    return c;
}
 
 
int main(void)
{
    srand(time(NULL));
    int A[N], i;
 
    for(i=0; i<N; ++i)
        A[i]=rand() % ((N/2) - (-((N/2)-1)) + 1) + (-((N/2)-1));
 
    for(i=0; i<N; ++i)
        printf("%d ", A[i]);
 
    printf("\nSumma pol. elementov = %d\nSumma otr. elementov = %d\n", sum_pol_elem(A, N), sum_otr_elem(A, N));
 
    return 0;
}

@LazySlacker · 16.09.2017, 11:51

Сообщение от Кристина 1998

LazySlacker, спасибо, но мне эти программы в двух функциях надо сделать, где первая- Подсчитать сумму всех элементов, имеющих положительные значения O(n).вторая- подсчёта количество элементов с отрицательными значениями О(1)

Если под положительными понимаются неотрицательные, то можно и за O(1):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 20
 
int main(void)
{
    srand(time(NULL));
    int a[N];
    for (int i = 0; i < N; ++i)
    {
        printf("%d ", a[i] = rand() % N - N / 2 + 1);
    }
    int neg = 0;
    for (int i = 0; i < N; ++i)
    {
        if (a[i] < 0) ++neg;
    }
    printf("\nneg = %d, pos = %d\n", neg, N - neg);
    return 0;
}

@Кристина 1998 · 17.09.2017, 15:33 **[ТС]**

Сообщение от CoderHuligan

t sum_otr_elem(int* a, int len)
{
* * int i, c=0;
* * for(i=0; i<len; ++i)
* * * * if(a[i]<0)c+=1;
* * return c;

А тут получается сложность О(1)?
А если мы размер массива вводим с клавиатуры и потом элементы массива сгенерировать по вот этой формуле: -((n div 2) - 1) до (n div 2), как сделать чтобы так было?

Добавлено через 16 секунд

Сообщение от CoderHuligan

t sum_otr_elem(int* a, int len)
{
* * int i, c=0;
* * for(i=0; i<len; ++i)
* * * * if(a[i]<0)c+=1;
* * return c;

А тут получается сложность О(1)?
А если мы размер массива вводим с клавиатуры и потом элементы массива сгенерировать по вот этой формуле: -((n div 2) - 1) до (n div 2), как сделать чтобы так было?

@CoderHuligan · 17.09.2017, 16:08

Сообщение от Кристина 1998

А тут получается сложность О(1)?

Она получается такой же, как и у другой функции. Честно говоря не знаю зачем нужно извращаться и пытаться увелиичивать сложность алгоритма, и не понимаю по каким критериям её оценивать.

Сообщение от Кристина 1998

А если мы размер массива вводим с клавиатуры и потом элементы массива сгенерировать по вот этой формуле: -((n div 2) - 1) до (n div 2), как сделать чтобы так было?

Вот так:

C
1
2
3
4
5
6
int A[N], i, n;
    for(i=0; i<N; ++i)
    {
        scanf("%d", &n);
        A[i]=n % ((N/2) - (-((N/2)-1)) + 1) + (-((N/2)-1));
    }

@LazySlacker · 17.09.2017, 16:21

Прочтите уже Википедию, наконец. И какой-нибудь учебник по C. Кстати, моя программа имеет сложность подсчета отрицательных чисел O(n), положительных - O(1). Что в ней не устроило?

@Кристина 1998 · 17.09.2017, 16:23 **[ТС]**

LazySlacker, в ваше программе же массива не вводится с клавиатуры и потом элементы массива не генерируются по вот этой формуле: -((n div 2) - 1) до (n div 2)

@LazySlacker · 17.09.2017, 16:53

Сообщение от Кристина 1998

LazySlacker, в ваше программе же массива не вводится с клавиатуры

Кокой ужос! Так трудно переделать пару строк?

Сообщение от Кристина 1998

и потом элементы массива не генерируются по вот этой формуле: -((n div 2) - 1) до (n div 2)

Вы уверены? У Вас не только с программированием проблемы, но и с элементарной математикой. Вы смысл этой формулы понимаете?

@Кристина 1998 · 17.09.2017, 18:14 **[ТС]**

Вот так тогда будет?

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int sum_pol_elem(int* a, int len)
{
    int i, c=0;
    for(i=0; i<len; i++)
        if(a[i]>0)c+=1;
    return c;
}
 
int sum_otr_elem(int* a, int len)
{
    int i, c=0;
    for(i=0; i<len; i++)
        if(a[i]<0)c+=1;
    return c;
}
 
 
int main(void)
{
    srand(time(NULL));
    int A[N], i;
scanf("%d",&N);
printf("Vvedite chisla:",N);
 
    for(i=0; i<N; ++i)
        A[i]=rand() % ((N/2) - (-((N/2)-1)) + 1) + (-((N/2)-1));
 
    for(i=0; i<N; ++i)
        printf("%d ", A[i]);
 
    printf("\nSumma pol. elementov = %d\nSumma otr. elementov = %d\n", sum_pol_elem(A, N), sum_otr_elem(A, N));
 
    return 0;
}

Добавлено через 13 минут
LazySlacker, не очень хорошо понимаю программирование. И должно же быть две функции

Добавлено через 32 минуты
LazySlacker, и в вашем коде сложность положительных- О(1), а отрицательных О(n)

@LazySlacker · 17.09.2017, 19:29

Сообщение от Кристина 1998

LazySlacker, и в вашем коде сложность положительных- О(1), а отрицательных О(n)

А Вам как надо? Только не говорите, что сложность подсчета отрицательных тоже должна быть O(1).

@bormant · 18.09.2017, 11:53

Сообщение от LazySlacker

Кстати, моя программа имеет сложность подсчета отрицательных чисел O(n), положительных - O(1). Что в ней не устроило?

Наверное, несоответствие заданию? Нужно было подсчитать сумму положительных, количество отрицательных.
Даже если было бы нужно считать количества, O(1) -- иллюзия, ибо по условию выполняется только один вариант, а разность нельзя взять, не посчитав вычитаемое. Иначе можно было бы константой обозвать и это:

C
1
2
3
4
5
6
7
  int sum=0, cnt=0;
  for (int i=0; i<n; ++i) {
    sscanf(" %d", a[i]);
    if (a[i]<0) ++cnt;
    else sum += a[i];  // прибавление 0 не повлияет на результат
  }
  printf("Сумма положительных: %d, количество отрицательных: %d\n", sum, cnt);

Сообщение от Кристина 1998

если мы размер массива вводим с клавиатуры

C
1
2
  int n;
  scanf(" %d", n);

C
1
  int a[n];  // начиная с C99

или, если локальные массивы переменной длины не поддерживаются:

C
1
2
3
  int *a=malloc(n*sizeof(*a));
...
  free(a);

Сообщение от Кристина 1998

элементы массива сгенерировать

C
1
2
3
  int ra=-(n/2-1), ri=n/2-ra+1;
  srand(time(NULL));
  for (int i=0; i<n; ++i) a[i]=ra+rand()%ri;

@easybudda · 18.09.2017, 12:01

Сообщение от bormant

scanf(" %d", n);

C
1
2
if ( scanf("%d", &n) != 1 )
  // WRONG INPUT!

@bormant · 18.09.2017, 12:06

easybudda,
да-да, "любимая" очепятка :-) с пропуском взятия адреса. Хочу ссылок в Си, аж кушать не могу...

@LazySlacker · 18.09.2017, 18:32

Сообщение от bormant

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

Mea culpa.

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int count_neg(int* arr, int n)
{
    int count = 0;
    while (n-- > 0)
    {
        if (*arr++ < 0) ++count;
    }
    return count;
}
 
int sum_pos(int* arr, int n)
{
    int sum = 0;
    while (n-- > 0)
    {
        if (*arr > 0) sum += *arr;
        ++arr;
    }
    return sum;
}
 
int main(void)
{
    srand(time(NULL));
    int n;
    scanf("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", arr[i] = rand() % n - n / 2 + 1);
    }
    printf("\nsum_pos = %d, count_neg = %d\n", sum_pos(arr, n), count_neg(arr, n));
    free(arr);
    return 0;
}

@bormant · 18.09.2017, 18:53

LazySlacker,
или так:

C
1
2
3
4
5
6
7
int sum_pos(int* arr, int n)
{
    int sum = 0;
    for (; n --> 0; ++arr)
        if (*arr > 0) sum += *arr;
    return sum;
}

Новые блоги и статьи Все статьи Все блоги /
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .

@Кристина 1998 0 / 0 / 1 Регистрация: 13.09.2016 Сообщений: 154

	Подсчитать сумму всех элементов, имеющих положительные значения O(n) 08.09.2017, 19:03. Показов 7093. Ответов 38 Метки нет (Все метки) Используя память, пропорциональную n, хранить массив целых чисел A, содержащий n элементов. Элементы массива A могут принимать случайные значения от -((n div 2) - 1) до (n div 2). То есть, если в массиве хранится 10 элементов, то эти элементы должны быть в диапазоне от -4 до 5. Разработать алгоритм, который осуществляет заполнение массива A случайными значениями, и по выбору пользователя выполняет одну из двух функций. Подсчитать сумму всех элементов, имеющих положительные значения O(n) 0

@Кристина 1998 0 / 0 / 1 Регистрация: 13.09.2016 Сообщений: 154
	16.09.2017, 10:09 [ТС]
	LazySlacker, спасибо, но мне эти программы в двух функциях надо сделать, где первая- Подсчитать сумму всех элементов, имеющих положительные значения O(n).вторая- подсчёта количество элементов с отрицательными значениями О(1) 0

@LazySlacker 93 / 77 / 31 Регистрация: 29.08.2017 Сообщений: 188
	17.09.2017, 16:21
	Прочтите уже Википедию, наконец. И какой-нибудь учебник по C. Кстати, моя программа имеет сложность подсчета отрицательных чисел O(n), положительных - O(1). Что в ней не устроило? 0

@Кристина 1998 0 / 0 / 1 Регистрация: 13.09.2016 Сообщений: 154
	17.09.2017, 16:23 [ТС]
	LazySlacker, в ваше программе же массива не вводится с клавиатуры и потом элементы массива не генерируются по вот этой формуле: -((n div 2) - 1) до (n div 2) 0

@bormant Модератор 7818 / 4637 / 2837 Регистрация: 22.11.2013 Сообщений: 13,159 Записей в блоге: 1
	18.09.2017, 12:06
	easybudda, да-да, "любимая" очепятка :-) с пропуском взятия адреса. Хочу ссылок в Си, аж кушать не могу... 0

Подсчитать сумму всех элементов, имеющих положительные значения O(n)

Решение