Как найти сумму элементов динамического массива

Работа с динамическими массивами в Паскаль abc.net

Динамические массивы

Объявление, выделение памяти

Обычно в языке Паскаль используются статические массивы вида:

var mas: array [1..10] of integer;

Границы статического массива изменить в ходе программы нельзя, так как они задаются в разделе объявлений «раз и навсегда».
Основным недостатком такого массива является то, что в случае, когда заранее не известно количество элементов массива, то приходится выделять память максимального размера, что называется «на всякий случай».

Рассмотрим работу с динамическим массивом.

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

begin
...
var a: array of integer;

Или объявление с инициализацией:

А выделение памяти и размер такого массива задается уже по ходу программы:

var a: array of integer;
var n:=readInteger;
a:=new integer[n];

var a: array of integer;
a:=new integer[readInteger];

var a: array of integer;
var n:=readInteger;
SetLength(a,n); // устанавливаем размер массива а

Ссылочная объектная модель: память выделяется служебным словом NEW

Инициализация, присваивание и вывод

Возможна инициализация динамического массива при описании:

var a: array of integer := (1,2,3);

Новые способы заполнения массива (заполнители):

var a:=Arr(1,2,3);// по правой части - integer

var a:=ArrFill(5,2); // 2 2 2 2 2

Ввод с клавиатуры:

var a:=ReadArrInteger(5); 
var a:=ReadArrReal(5);

Заполнение случайными числами:

var a:=new integer[10];
a:=arrRandomInteger(10);

или с дополнительными параметрами (диапазон [5;15]):

var a:=arrRandomInteger(10,5,15);

Вывод массива

Или с разделителем между элементами:

Или:

Или с использованием метода:

a.Print; // пример вывода: 1 5 3 13 20
a.PrintLines; // каждый элемент с новой строки

Переприсваивание:

var a: array of integer := (1,2,3);
var b:=a; // [1,2,3]

Но!
Если теперь переприсвоить значение элементов массива b, то изменится и массив a:

var a: array of integer := (1,2,3);
var b:=a;
b[2]:=1;
print(a); //[1,2,1]

Для того, чтобы избежать данной ситуации, необходимо создать массив b, как копию массива a:

var a: array of integer := (1,2,3);
var b:=Copy(a);
b[2]:=1;
print(a); //[1,2,3]

Очистка динамического массива

Если в программе случайно создается повторно один и тот же массив:

var a: array of integer;
a:=new integer[4];
...
a:=new integer[5];

В результате возникают так называемые участки «утекшей» памяти (неиспользуемой).
Постепенно произойдет переполнение памяти. В платформе .net используется автоматический сборщик мусора.

Но можно очистить память и принудительно:

В процессе очистки выполнение программы и всех процессов приостанавливается. По этой причине сборщик мусора в системах реального времени не используется.

Работа с элементами массива

1. Цикл for

for var i:=0 to High(a) do
   print(a[i]);;

2. Цикл foreach

foreach var x in a do
    print(x);

High(массив) — возвращает верхнюю границу динамического массива

Пример: поиск элемента в массиве (выдавать индекс искомого)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function IndexOf(a:array of integer;x:integer):integer;
begin
  result:=-1;
  for var i:=0 to High(a) do
    if a[i]=x then
    begin
      result:=i;
      break
     end
end;
begin
var a:=Arr(1,2,3,4,5);
print(IndexOf(a,5))
end.

1
2
3
4
5
6
7
8

function IndexOf<T>(a:array of T;x:T):integer;
begin
 ...
end;
begin
var a:=Arr(1,2,3,4,5);
print(IndexOf(a,5))
end.

Методы для работы с массивами

var a:=Arr(1,2,3,4,5);
reverse(a); // [5,4,3,2,1]

var a:=Arr(2,3,1,4,5); //[1,2,3,4,5] 
sort(a);

Следующие методы не меняют сам массив:

a.Min
a.Max
a.Sum
a.Average — среднее арифметическое

begin
  var a := new integer[10];
  a := arrRandomInteger(5,0,5); //[1,3,5,4,5] 
  print(a.IndexOf(3)) // 1
end.

или метод a.Contains(x) наравне с x in a:

begin
  var a := new integer[10];
  a := arrRandomInteger(5,0,5); //[1,3,5,4,5] 
  print(a.Contains(3)); // True
  print(3 in a)// True
end.

Некоторые алгоритмы работы с массивами

Сдвиги

Пример: дан массив, надо сдвинуть его элементы:

var a:=Arr(1,2,3,4,5,6);
var x:=a[0];
for var i:=0 to 4 do
   a[i]:=a[i+1];
a[5]:=x;
print(a)

Если сдвиг вправо:

 // …
  var v := a[0];
  for var i:=0 to a.Length-2 do
    a[i] := a[i+1];
  a[a.Length-1] := v;

1. либо задействовать еще один массив (𝜭 (n-k) — по времени)
2. либо много раз запускать один и тот же алгоритм (𝜭 (1) — по памяти)

Минимальный элемент и его индекс:

Решение 1:

  // …
  var (min, minind) := (a[0], 0);  
  for var i:=1 to a.Length-1 do
    if a[i]<min then
      (min, minind) := (a[i], i);  Result := (min, minind);

Решение 2:

  // …
  var (min, minind) := (real.MaxValue, 0);  
  for var i:=0 to a.Length-1 do
    if a[i]<min then
      (min, minind) := (a[i], i);  Result := (min, minind);

Решение 3:

begin
  var a := new integer[5];
  a := arrRandomInteger(5); // [86,37,41,45,76] 
  print(a.Min,a.IndexMin); // 37  1
end.

Циклический сдвиг влево:

  // …
  var v := a[0];
  for var i:=0 to a.Length-2 do
    a[i] := a[i+1];
  a[a.Length-1] := v;

Циклический сдвиг вправо:

  // …
  var v := a[a.Length-1];
  for var i:=a.Length-1 downto 1 do
    a[i] := a[i-1];
  a[0] := v;

Срезы

Срез массива — это подмножество исходного массива.

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

var a:=Arr(1,2,3,4,5,6);
print(a[1:5]) // [2,3,4,5]

a[1:5] — 1-й элемент включая, 5-й не включая

println(a[:5]); // [1,2,3,4,5] - с начала до 5-го не включая
println(a[1:]); // [2,3,4,5,6] - до конца
println(a[::2]); // [1,3,5] - третий параметр - это шаг

a[::-1] — получим 6 5 4 3 2 1

Т.о. выполнение при помощи срезов выглядит так:
Перестановка:

var a:=Arr(1,2,3,4,5,6);
var k:=a.Length-1; // 6 - 1
a:=a[k:]+a[:k];
print(a) // [6,1,2,3,4,5]

Т.е. создан еще массив уже со сдвигом.

Время работы алгоритма n+n, 𝜭 (n)

Подробнее со срезами можно ознакомиться здесь

Удаление и вставка элементов массива. Списки

Для расширения массива путем вставки какого-либо элемента, необходимо предусмотреть место в памяти. По этой причине для данных случаев проще использовать списки:
Списки — List — это тоже динамический массив, который может «расширяться» и «сужаться» по ходу программы (вставка и удаление элементов).

  
Подробнее со списками можно ознакомиться здесь

Решение задач

Простые задачи

Пример: Напишите функцию SumArray, возвращающую сумму элементов заданного динамического массива. Выведите длину и сумму элементов массива

Выполнение:

1
2
3
4
5
6
7
8

function SumArray(var a: array of integer): integer:=a.Sum;
begin
  var a:=new integer[10];
  a:=arrRandomInteger(10);
  foreach var x in a do
    print(x);
  println('длина массива = ',a.Length,' сумма = ',ArraySum(a))
end.

Задание 0: Дан массив, вывести его содержимое на экран, разделяя элементы точкой с запятой (процедура PrintArr). Используйте для разделителя delim значение по умолчанию равное ‘; ‘

Выполнение:
Дополните код:

1
2
3
4
5
6
7
8
9
10

procedure PrintArr( a: array of integer; delim:string:='; ');
begin
  foreach var ... in ... do
    print(x,delim);
end;
begin
  var a:=new integer[10];
  a:=arrRandomInteger(10);
  ...
end.

Пример «Универсальный тип»:
Написать процедуру для печати значений массива любого типа.

В определении универсального типа функции или процедуры параметр типа является заполнителем для определенного типа, который клиент указывает при создании экземпляра универсального типа.

✍ Решение:

Задание 1: Исправить процедуру PrintArr предыдущего задания 0 так, чтобы за последним элементом символ-разделитель не ставился. Реализовать данную процедуру как процедуру универсального типа.

Фрагмент программы:

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

function MakeOddArrFunc (a: array of integer; n:integer):array of integer;
begin
  var b:= new integer[n];
  var j:=0;
  for var i:=0 to ... do 
    if ... then
      begin ...;...;end;
  SetLength(...,...);
  result:=b;
end;
procedure MakeOddArrProc (a: array of integer;var b: array of integer; n:integer);
begin
 b:= new integer[n];
 var j:=0;
 for var i:=0 to ... do 
    if ... then
      begin ...;...;end;
 SetLength(...,...);
end;
begin
  var a:=arrRandomInteger(20);
  var b: array of integer;
  var n:=readInteger('введите N');
  println('исходный массив ',a);
  println('результат работы с функцией ',MakeOddArrFunc(a,n));
  MakeOddArrProc(a,b,n);
 print('результат работы с процедурой ',b) 
end.

Задание 3: Заполнить целочисленный массив первыми N (N ≥ 0) числами Фибоначчи. Достаточно одной из реализаций: функции или процедуры

Фрагмент программы:

1
2
3
4
5
6
7
8
9
10
11
12

function MakeFibArr (n : integer):array of integer;
begin
 var c:= new integer[n];
 c[0]:=...;c[1]:=...;
 for var i:=2 to n-1 do 
    ...;
 result:=c;
end;
begin
  var n:= readinteger;
  ...;
end.

Задание 4: Дан целочисленный массив. Написать процедуру EvenMult с двумя параметрами: входным (параметр по значению) — целочисленным массивом и выходным (параметр по ссылке) — evensCnt — значением целого типа, которая увеличивает все элементы массива с чётными значениями в два раза и записывает в evensCnt количество таких элементов

Пример: Описать функцию MakeRandomRealArr с тремя параметрами: целым числом N (N ≥ 0), вещественными параметрами a и b (a < b).
Функция должна возвращать массив (тип которого либо RealArr либо array of real) из N случайных вещественных элементов в диапазоне a..b.
Продемонстрируйте заполнение и вывод на экран массива

Выполнение:

1
2
3
4
5
6
7
8
9
10
11

function MakeRandomRealArr (n : integer;a,b:real):array of real;
begin
   var c:= ArrRandomReal(n,a,b);
   result:=c;
end;
begin
  var n:= readinteger;
  var a:=readReal;
  var b:=readReal;
  println('результат работы с функцией ',MakeRandomRealArr(n,a,b));
end.

Задание 5: Дан непустой массив вещественных чисел. Найти его наименьший элемент. Выполнить задание с помощью пользовательской функции FindMin.

Пример: Дан целочисленный массив. Обнулить все его элементы
с нечётными индексами (процедура SetToZeroOddIndexes).
Условный оператор не использовать

Выполнение:

1
2
3
4
5
6
7
8
9
10
11
12
13

procedure SetToZeroOddIndexes(a: array of integer);
begin
var j:=0;
 while j<=a.Length-1 do  begin
    a[j]:=0;j+=2;
 end;
 println('результирующий массив: ',a);
end;
begin
  var a:=arrRandomInteger(10);
  println('исходный массив: ',a);
  SetToZeroOddIndexes(a);
end.

Задание 7: Дан массив целых чисел, содержащий не менее трёх элементов. Найти значение и номер последнего локального максимума. Для этого написать процедуру с двумя выходными параметрами (параметры по ссылке)

Задачи на срезы

Задание srez1: Дан массив размера N. Вывести его элементы в обратном порядке

Ak, A2*k, A3*k... 

Выполнение:

1
2
3
4

var n:=ReadInteger;
var a:=ReadArrReal(n);
var k:=ReadInteger;
a[k-1 : : k].Print;

а2, а4, а6, ... аn

аn, аn-2, аn-4, ... а1 

а2, а4, а6,...а1, а3, а5...

Выполнение:

1
2
3
4

var n:=ReadInteger;
var a:=ReadArrReal(n);
var srez:=a[1::2]+a[::2];
Print(srez);

а1, а3, а5, ..., а6, а4, а2...

Пример: Дан массив размера N и целые числа K и L (1<=K<=L<=N). Найти среднее арифметическое элементов массива с номерами от K до L включительно

Выполнение:

1
2
3
4
5
6

var n:=ReadInteger;
 var a:=ReadArrReal(n);
 var k:=ReadInteger;
 var l:=ReadInteger;
 var srez:=a[k-1:l].Average;
 print(srez);

Задание srez5: Дан массив размера N и целые числа K и L (1<=K<=L<=N). Найти сумму элементов массива кроме элементов с номерами от K до L включительно

Пример: Дан массив А размера N. Найти минимальный элемент из его элементов с четными номерами: а2, а4, а6,… .

Выполнение:

1
2
3

var n:=ReadInteger;
var a:=ReadArrReal(n);
print(a[1::2].min);

[1,2,3,4,5,6,7,8] -> [5,6,7,8,1,2,3,4]

Использование методов

Пример: Дан случайный массив. Найти сумму элементов между первым минимальным и последним максимальным. Сделайте 2 версии – с использованием методов и без их использования. Выдайте время работы каждой версии (для достаточно больших массивов) – можно использовать System.DateTime.Now

Выполнение:

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

function MyMin(a: array of real): integer;
  begin
  var minInd:=0;
     for var i:=1 to a.Length-1 do begin
      if a[minInd]>a[i] then minInd:=i;
     end;
   result:=minInd;
  end;
  function MyMax(a: array of real): integer;
  begin
  var maxInd:=0;
    for var i:=1 to a.Length-1 do begin
       if a[maxInd]<=a[i] then maxInd:=i;
    end;
   result:=maxInd;
  end;
begin
//использование методов
var n:=readinteger;
var a:=readArrreal(n);
var t:=System.DateTime.Now;
var minInd:=a.IndexMin;
var maxInd:=a.LastIndexMax;
var srez1:=a[minind+1:maxind].sum;
println('Результат 1: ',srez1);
var t1:=System.DateTime.Now;
println('Время выполнения: ',t1-t);
// без использования методов
t:=System.DateTime.Now;
 minind:= MyMin(a);
 maxind:= MyMax(a);
srez1:=a[minind+1:maxind].sum;
println('Результат 2: ',srez1); 
t1:=System.DateTime.Now;
println('Время выполнения: ',t1-t);
end.

Задание: Даны 2 упорядоченных массива. Создайте третий – их объединение с сохранением упорядоченности (сортировка – метод sort). Как и для предыдущей задачи, сделайте хотя бы 2 варианта работы и сравните их.

Фрагмент кода:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

procedure MySort(c: array of integer);
  begin
// сортировка методом Пузырька
    for ...
        for ...
           ...
  end;
begin
var a:=arr(1,3,5,6,12);
var b:=arr(2,6,8,12,16);
var c:=a+b;
//использование методов
var t:=System.DateTime.Now;
...
...
var t1:=System.DateTime.Now;
println('Время выполнения с методом: ',t1-t);
t:=System.DateTime.Now;
//без использования методов
...
...
...
end.