Найти столбец матрицы с максимальной суммой элементов

Задача

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

Пояснение к задаче и алгоритм решения

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

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

Если сумма следующего столбца окажется больше, то снова перезапишем указанные переменные. Если же меньше или равна, то перезаписывать не будем.

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

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

Исходный код на языке программирования Pascal

const
    N = 5; M = 10;
var
    a: array[1..N,1..M] of integer;
    i, j, col_max: byte;
    sum, sum_max: integer;
begin
    randomize;
    for i:=1 to N do begin
        for j:=1 to M do begin
            a[i,j] := random(10);
            write(a[i,j]:3);
        end;
        writeln;
    end;
   
    sum_max := -1;
    col_max := 0;
    for j:=1 to M do begin
        sum := 0;
        for i:=1 to N do
            sum := sum + a[i,j];
        if sum > sum_max then begin
            sum_max := sum;
            col_max := j;
        end;        
    end;
   
    writeln('Столбец ',col_max,', сумма ',sum_max);
end.

Пример(ы) выполнения программы на языке Pascal

  0  8  9  8  2  2  2  8  6  8
  7  1  1  7  3  1  6  3  8  8
  8  7  0  8  5  7  9  0  8  9
  2  6  1  6  2  6  4  6  5  8
  4  3  6  8  7  9  1  2  1  7
Столбец 10, сумма 40

Исходный код на языке программирования C

#include <stdio.h>
#define M 10
#define N 5
main() {
    int a[N][M];
    int i, j, s, sum, col;
    srand(time(NULL));
    for (i=0; i<N; i++) {
        for (j=0; j<M; j++) {
            a[i][j] = rand() % 10;
            printf("%5d", a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
   
    sum = 0;
    col = 0;
    for (j=0; j<M; j++) {
        s = 0;
        for (i=0; i<N; i++) s+=a[i][j];
        printf("%5d", s);
        if (s > sum) {
            sum = s;
            col = j;
        }
    }
    printf("\n %d \n", col+1);
}

Пример(ы) выполнения программы на языке C

    8    8    5    3    2    8    2    8    2    2
    1    7    1    8    7    6    5    4    9    5
    1    0    8    5    3    6    6    2    8    2
    6    6    2    1    1    5    1    4    3    3
    6    7    0    7    7    9    6    3    3    5

   22   28   16   24   20   34   20   21   25   17
 6

Исходный код на языке программирования Python

from random import random
M = 10
N = 5
a = []
for i in range(N):
    b = []
    for j in range(M):
        b.append(int(random()*11))
        print("%3d" % b[j], end='')
    a.append(b)
    print()
 
for i in range(M):
    print(" --", end='')
print()

max_sum = 0
col = 0
for i in range(M):
    s = 0
    for j in range(N):
        s += a[j][i]
    print("%3d" % s, end='')
    if s > max_sum:
        max_sum = s
        col = i
print()
print(col+1)

Пример(ы) выполнения программы на языке Python

  5  3  4  6  0  6  6 10  1  8
  6  5 10  5  3  5  7  7 10  2
  5 10  2  4  7  5  3  4  2  2
  1  3  0  9  0  8  4  5  5  9
  9  8  5  3  7  8  4  1  5  4
 -- -- -- -- -- -- -- -- -- --
 26 29 21 27 17 32 24 27 23 25
6

Исходный код на языке программирования КуМир

алг суммы строк столбцов
нач
    цел M = 10, N = 5
    цел таб a[1:N,1:M]
    цел i, j, s, smax, col

    нц для i от 1 до N
        нц для j от 1 до M
            a[i,j] := int(rand(0,10))
            вывод a[i,j]:3
        кц
        вывод нс
    кц

    нц для i от 1 до M
        вывод "---"
    кц
    вывод нс

    smax := 0
    col := 0
    нц для j от 1 до M
        s := 0
        нц для i от 1 до N
            s := s + a[i,j]
        кц
        вывод s:3
        если s > smax то
            smax := s
            col := j
        все
    кц
    вывод нс, col
кон

Пример(ы) выполнения программы на языке КуМир

  5  7  0  1  1  0  8  4  4  3
  9  6  2  6  2  3  5  8  8  3
  1  3  3  3  5  0  2  3  2  5
  2  8  6  5  8  5  7  9  5  8
  2  6  0  9  8  4  2  8  2  4
------------------------------
 19 30 11 24 24 12 24 32 21 23
8

Исходный код на языке программирования Basic

M = 10
N = 5
dim a(N,M)
for i = 0 to N-1
        for j=0 to M-1
                a[i,j] = int(rand*10)
                print a[i,j] + "     ";
        next j
        print
next i
 
for i=0 to M+2
        print "--   ";
next i
print

max=0
col = 0
for i=0 to M-1
        s = 0
        for j=0 to N-1
                s = s + a[j,i]
        next j
        print s + "   ";
        if s > max then
                max = s
                col = i
        endif
next i
print
print col+1

Пример(ы) выполнения программы на языке Basic

9     2     6     0     6     0     4     5     8     3    
1     0     0     0     4     7     6     2     0     2    
7     3     9     5     0     5     4     7     9     0    
3     7     8     3     3     5     7     2     8     5    
6     0     7     6     6     0     5     9     8     3    
--   --   --   --   --   --   --   --   --   --   --   --   --  
26   12   30   14   19   17   26   25   33   13  
9

Тема

Матрицы

Уровень сложности

Средний

Дата публикации