Найти непрерывную часть массива, чтобы сумма элементов была максимальной - C (СИ)

Узнай цену своей работы

Формулировка задачи:

массив из случайных целых чисел от -1000 до 1000. задача найти непрерывную часть этого массива чтобы сумма элементов была максимальной

Решение задачи: «Найти непрерывную часть массива, чтобы сумма элементов была максимальной»

textual
Листинг программы
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. int *build_arr(unsigned lenght, int max, int min);
  6. void print_arr(int *ptr, unsigned lenght);
  7. void print_sequence(int *ptr, unsigned lenght);
  8.  
  9. int main(void)
  10. {
  11.    srand(time(NULL));
  12.    unsigned arrlen = 15;
  13.    int *arr = build_arr(arrlen, 1000, -1000);
  14.    print_arr(arr, arrlen);
  15.    print_sequence(arr,arrlen);
  16.  
  17.    free (arr);
  18.    return 0;
  19. }
  20.  
  21. int *build_arr(unsigned lenght, int max, int min) {
  22.    int *ptr = malloc(sizeof(int)*lenght);
  23.    if (ptr == NULL) {
  24.       puts ("out of memory!");
  25.       exit (1);
  26.    }
  27.    int *pos = ptr;
  28.    while ((pos-ptr) < lenght) {
  29.       *pos = rand() % (max * 2) + 1 + min;
  30.       pos++;
  31.    }
  32.    return ptr;
  33. }
  34.  
  35. void print_arr(int *ptr, unsigned lenght) {
  36.    while (lenght--)
  37.       printf("%i ", *ptr++);
  38.    putchar('\n');
  39. }
  40.  
  41. void print_sequence(int *ptr, unsigned lenght) {
  42.    long max[2][lenght];
  43.    int *pos;
  44.    int i;
  45.  
  46.    for (i=0; i<lenght; i++) {
  47.       pos = &ptr[i];
  48.       long temp_max = 0;
  49.       long counter = 0;
  50.       while (pos < (&ptr[0] + lenght)) {
  51.          counter += (*pos);
  52.          if (counter > temp_max)
  53.             temp_max = counter;
  54.          ++pos;
  55.       }
  56.       max[0][i] = temp_max;
  57.       pos = &ptr[i-1];
  58.       temp_max? (counter = temp_max): (counter = *(pos+1));
  59.       while (pos >= &ptr[0]) {
  60.          counter += (*pos);
  61.          if (counter > temp_max)
  62.             temp_max = counter;
  63.          --pos;
  64.       }
  65.       max[1][i] = temp_max;
  66.    }
  67.  
  68.    int number = 0;
  69.    pos = (int*)&max[1][0];
  70.    for (i=0; i<lenght; i++)
  71.       if (*pos < max[1][i]) {
  72.          pos = (int*)&max[1][i];
  73.          number = i;
  74.       }
  75.  
  76.    while (1) {
  77.       printf ("%i ", ptr[number]);
  78.       if (max[1][number] == max[1][number+1])
  79.          number++ ;
  80.       else
  81.          break;
  82.    }
  83.    putchar('\n');
  84. }

Объяснение кода листинга программы

  1. Название: main Описание: Главная функция программы, инициализирует генератор случайных чисел, создает массив заданной длины с случайными числами, выводит этот массив на экран, а затем выводит непрерывную последовательность элементов с максимальной суммой.
  2. Название: build_arr Описание: Функция для создания массива заданной длины с случайными числами в указанном диапазоне.
  3. Название: print_arr Описание: Функция для вывода на экран элементов массива через пробел.
  4. Название: print_sequence Описание: Функция для поиска непрерывной последовательности элементов массива с максимальной суммой. Использует два подмассива для отслеживания максимальной суммы, обновляя их при переходе к следующему элементу. При достижении конца массива, начинает проверку предыдущих элементов, пока не найдет непрерывную последовательность с максимальной суммой.
  5. Название: number Описание: Локальная переменная в функции print_sequence, используется для отслеживания индекса текущего элемента непрерывной последовательности.
  6. Название: max_counter Описание: Локальная переменная в функции print_sequence, используется для отслеживания текущей максимальной суммы.
  7. Название: temp_max Описание: Локальная переменная в функции print_sequence, используется для временного хранения текущей максимальной суммы.
  8. Название: counter Описание: Локальная переменная в функции print_sequence, используется для отслеживания суммы текущих элементов.
  9. Название: pos Описание: Локальная переменная в функции print_sequence, используется для перемещения по массиву при поиске непрерывной последовательности.
  10. Название: ptr Описание: Локальная переменная в функции print_sequence, используется для обращения к элементам массива.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 3.538 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы