Перейти к содержанию
Найти массив с максимальной суммой элементов
Просмотров 673 Обновлено 15 октября 2021
Сгенерировать десять массивов из случайных чисел. Вывести их и сумму их элементов на экран. Найти среди них один с максимальной суммой элементов. Указать какой он по счету, повторно вывести этот массив и сумму его элементов.
Заполнение массива и подсчет суммы его элементов оформить в виде отдельной функции.
Если сохранять все массивы нет необходимости, то тогда задача решается проще.
В основной ветке программы создается два массива. Один для хранения массива с максимальной суммой элементов, а второй — для хранения текущего массива.
В функцию передается ссылка на текущий массив. Там он заполняется, выводится на экран и вычисляется сумма его элементов, которую функция возвращает в основную ветку программы.
Если сумма элементов текущего массива оказывается больше, чем значение переменной, предназначенной для хранения максимальной суммы, то текущий массив присваивается переменной, предназначенной для хранения массива с максимальной суммой элементов. Кроме того в отдельной переменной запоминается номер этого массива. В конце программы массив, его номер по счету и сумма элементов выводятся на экран.
Pascal
const N = 15;
type arr = array[1..N] of integer;
var
arr_max, arr_new: arr;
sum_max, sum_new, i, id: integer;function new_array(var a: arr): integer;
var k: byte;
begin
new_array := 0;
for k:=1 to N do begin
a[k] := random(50);
write(a[k]:4);
new_array := new_array + a[k];
end;
writeln(' - ', new_array);
end;begin
randomize;
sum_max := 0;
id := 1;
for i:=1 to 10 do begin
sum_new := new_array(arr_new);
if sum_new > sum_max then begin
arr_max := arr_new;
sum_max := sum_new;
id := i;
end;
end;
writeln;
writeln(id, '-й массив с максимальной суммой элементов:');
for i:=1 to N do
write(arr_max[i]:4);
writeln(' - ', sum_max);
end.
3 29 24 7 30 28 37 30 7 4 23 18 26 18 10 - 294
2 39 2 35 15 33 35 37 16 8 35 37 8 22 47 - 371
1 36 47 21 49 35 44 40 27 16 36 15 43 12 19 - 441
13 2 9 21 9 13 13 26 32 15 12 32 14 19 7 - 237
0 11 7 11 27 13 23 9 33 19 21 9 31 9 7 - 230
10 9 33 22 5 25 1 40 36 25 15 41 39 8 38 - 347
17 13 44 18 32 18 22 11 19 40 26 29 15 2 0 - 306
20 33 35 21 1 4 3 33 7 10 8 33 12 10 5 - 235
36 33 31 26 44 33 18 17 27 42 15 12 19 8 34 - 395
21 29 48 41 31 42 34 0 17 37 36 33 11 12 42 - 4343-й массив с максимальной суммой элементов:
1 36 47 21 49 35 44 40 27 16 36 15 43 12 19 - 44
Язык Си
#include < stdio.h>
#define N 15
int array(int a[]);main() {
int arr_new[N], arr_max[N], i, j, id, sum_max, sum_new;
srand(time(NULL));
id = 0;
sum_max = 0;
for (i=1; i<=10; i++) {
sum_new = array(arr_new);
if (sum_new > sum_max) {
sum_max = sum_new;
for (j=0; j< N; j++) arr_max[j] = arr_new[j];
id = i;
}
}
printf("n%d-й массив с максимальной суммой элементов:n", id);
for (i=0; i< N; i++) printf("%4d", arr_max[i]);
printf(" - %dn", sum_max);
}int array(int a[]) {
int k, sum;
sum = 0;
for (k=0; k< N; k++) {
a[k] = rand()%50;
sum += a[k];
printf("%4d", a[k]);
}
printf(" - %dn", sum);
return sum;
}
Нельзя напрямую присвоить один массив другому.
Python
from random import randomdef array(a):
s = 0
for i in range(15):
a[i] = int(random()*50)
print("%4d" % a[i], end='')
s += a[i]
print(" - %d" % s)
return sarr_new = [0]*15
sum_max = 0
index = -1
arr_max = -1
for i in range(10):
sum_new = array(arr_new)
if sum_new > sum_max:
sum_max = sum_new
index = i+1
arr_max = arr_new[:]print("%d-й массив имеет максимальную сумму элементов:" % index)
print(arr_max, ' - ', sum_max)
Выражение arr_max = arr_new[:] присваивает копию массива. Иначе — создавалась бы еще одна ссылка на текущий массив arr_new, и в конце выводился бы последний массив, а не с наибольшей суммой (сама сумма выводилась бы правильно).
КуМир
цел Н = 15
цел таб а[1:Н]
алг
нач
цел сч, сч2, индекс, сумма, сумма_текущая
цел таб б[1:Н]
сумма := 0
индекс := 1
нц для сч от 1 до 10
сумма_текущая := массив
если сумма < сумма_текущая то
сумма := сумма_текущая
индекс := сч
нц для сч2 от 1 до Н
б[сч2] := а[сч2]
кц
все
кц
вывод индекс, "-й массив имеет максимальную сумму элементов:", нс
нц для сч от 1 до Н
вывод б[сч], " "
кц
вывод " - ", сумма
коналг цел массив
нач
цел сч
знач := 0
нц для сч от 1 до Н
а[сч] := int(rand(0,50))
вывод а[сч], " "
знач := знач + а[сч]
кц
вывод " - ", знач, нс
кон
Переменные-массивы нельзя присваивать друг другу.
uses crt;
const nmax=15;
var a:array[1..nmax,1..nmax] of integer;
m,n,i,j,imx:byte;
sm,mx:integer;
begin
randomize;
repeat
write('Количество строк до ',nmax,' m=');
read(m);
until m in [1..nmax];
repeat
write('Количество столбцов до ',nmax,' n=');
read(n);
until n in [1..nmax];
writeln('Исходная матрица:');
writeln(' №','Сумма:':n*4+8);
mx:=-maxint-1;
imx:=0;
for i:=1 to m do
begin
write(i:2);
sm:=0;
for j:=1 to n do
begin
a[i,j]:=random(20);
write(a[i,j]:4);
sm:=sm+a[i,j];
end;
writeln(sm:6);
if sm>mx then
begin
mx:=sm;
imx:=i;
end;
end;
writeln;
write('Максимальная сумма=',mx,' в строке ',imx);
end.
Динамика по паре (позиция в массиве, количество оставшихся действий).
Пусть f(i, k) — максимальная сумма которую можно набрать за k действий стартуя с позиции i. Для неё верны следующие соотношения:
f(0, k) # искомая величина f(i >= len(a), *) = 0 # вышли за пределы массива a f(*, k <= 0) = 0 # кончились действия f(i, k) <= f(i + 1, k - 1) # двигаемся, a[i] не взяли f(i, k) <= a[i] + f(i + 1, k - 2) # взяли a[i] и сдвинулись на шаг
Программа:
import functools
def max_sum(a, k):
@functools.cache
def f(i, k):
if k <= 0:
return 0
if i >= len(a):
return 0
return max(
a[i] + f(i + 1, k - 2),
f(i + 1, k - 1)
)
return f(0, k)
print(max_sum([5, 7, 11], 3))
print(max_sum([15, 17, 13, 20], 2))
print(max_sum([15, 17, 13, 20], 100))
$ python max-sum.py 12 17 65
К обработке элементов одномерного массива можно отнести такие типы задач:
1. найти сумму элементов;
2. найти количество элементов;
3. заменить элементы по условию;
4. поиск максимального и минимального значений.
Рассмотрим эти задачи на двух языках программирования
Найти сумму элементов массива (сложить все элементы массива).
|
|
|
| Рис. (1). Программа на Pascal | Рис. (2). Программа на Python |
Найти сумму по условию, например сумму чётных элементов (сложить все чётные элементы массива).
|
|
|
| Рис. (3). Программа на Pascal | Рис. (4). Программа на Python |
Найти количество элементов по сложному условию, например кратных (7) и не кратных (5) и (3).
|
|
|
| Рис. (5). Программа на Pascal | Рис. (6). Программа на Python |
Заменить все отрицательные элементы на модуль элемента.
|
|
|
| Рис. (7). Программа на Pascal | Рис. (8). Программа на Python |
Способов поиска максимального и минимального значений элементов массива существует множество. Остановимся на таком способе:
1. допустим, что максимальное значение равно меньшему из диапазона;
2. сравним его со всеми элементами массива поочерёдно;
3. всегда найдётся значение большее, чем начальное, поэтому запомним его в переменную, которую ввели для поиска максимального значения.
Задача на поиск максимального элемента
Заполнить массив элементами в диапазоне от (-10) до (20). Найти максимальный элемент массива.
Рис. (9). Алгоритм поиска максимального элемента массива
|
|
|
|
Рис. (10). Поиск максимального элемента на Pascal |
Рис. (11). Поиск максимального элемента на Python |
Аналогично происходит поиск минимального элемента.
Источники:
Рис. 1. Программа на Pascal. © ЯКласс.
Рис. 2. Программа на Python. © ЯКласс.
Рис. 3. Программа на Pascal. © ЯКласс.
Рис. 4. Программа на Python. © ЯКласс.
Рис. 5. Программа на Pascal. © ЯКласс.
Рис. 6. Программа на Python. © ЯКласс.
Рис. 7. Программа на Pascal. © ЯКласс.
Рис. 8. Программа на Python. © ЯКласс.
Рис. 9. Алгоритм поиска максимального элемента массива. © ЯКласс.
Рис. 10. Поиск максимального элемента на Pascal. © ЯКласс.
Рис. 11. Поиск максимального элемента на Python. © ЯКласс.
Задание:
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать произвольные целые значения. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит сумму наибольшей по длине возрастающей последовательности подряд идущих элементов. Если таких последовательностей несколько, можно вывести любую из них. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
|
Паскаль |
|
|
Си |
|
|
Естественный язык |
|
Объявляем массив A из 30 элементов. Объявляем целочисленные переменные i, l, lmax, s, smax. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й. … |
Решение:
Обратим внимание, что нужно найти не длину, а сумму наибольшей (то есть, самой длинной!) возрастающей последовательности (то есть, такой, в которой каждый следующий элемент строго больше предыдущего). В переменных l и s будем хранить длину и сумму текущей (рассматриваемой сейчас) последовательности, а в переменных lmax и smax – значения для наибольшей последовательности.
Решение на естественном языке. Записываем в переменную lmax начальное значение 0, в переменную l – значение 1, а в переменную smax – значение первого элемента массива. В цикле рассматриваем все элементы массива, начиная со 2-ого до 30-ого. Если очередной элемент больше предыдущего, увеличиваем переменную l на 1, а к переменной s добавляем значение этого элемента; иначе записываем 1 в переменную l и значение этого элемента в s. После этого (в теле цикла) сравниваем l и lmax; если l > lmax (нашли новую самую длинную возрастающую цепочку), записываем значение s в smax.
Решение на Паскале.
const N=30;
var a: array [1..N] of integer;
i, l, lmax, s, smax: integer;
begin
for i:=1 to N do readln(a[i]);
lmax:=0; l:=1; s:=a[1];
for i:=2 to N do begin
if a[i] > a[i-1] then begin
l:=l+1; s:=s+a[i]
end
else begin
l:=1; s:=a[i]
end;
if l > lmax then begin
lmax:=l;
smax:=s
end
end;
writeln(smax)
end.