Занятие 5. Pascal abc.net: Динамические массивы

Авторadmin / Опубликовано

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

Назад
К оглавлению
Далее

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

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

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

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

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

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

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

begin
...
var a: array of integer;

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

var a:= Arr(1,3,2,7);

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

  1. var a: array of integer;
var n:=readInteger;
a:=new integer[n];
  2. var a: array of integer;
a:=new integer[readInteger];
  3. var a: array of integer;
var n:=readInteger;
SetLength(a,n); // устанавливаем размер массива а

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

    var a := new integer[5];
Организация памяти для массива a
Организация памяти для массива a

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

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

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);

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

print(a);

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

print(a, '; ');

Или:

printArr(a);

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

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];

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

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

a:=nil;

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

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

  1. Цикл for
    2. for var i:=0 to High(a) do
   print(a[i]);;
  2. Цикл foreach
    3. 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.
    При вызове обобщенной функции компиляция будет в два этапа:

    1. Автовыведение типа Т, сравнение с реальными цифрами, и т.к. числа целые, то Т определится как integer.
    2. Берется тело функции и заменяется Т на integer (инстанцирование функции с конкретным типом)

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

  • Reverse(a)
    • var a:=Arr(1,2,3,4,5);
reverse(a); // [5,4,3,2,1]
  • Sort(a)
    • var a:=Arr(2,3,1,4,5); //[1,2,3,4,5] 
sort(a);
  • SortByDescending(a); — по убыванию
    • Следующие методы не меняют сам массив:

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

  • Cтандартные методы a.IndexOf(x) и a.LastIndexOf(x):
    • 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.
      Пример «Универсальный тип»:
      Написать процедуру для печати значений массива любого типа.
      В определении универсального типа функции или процедуры параметр типа является заполнителем для определенного типа, который клиент указывает при создании экземпляра универсального типа.

      ✍ Решение:

        procedure printArray<T>(a: array of T);
begin
  for var i:=0 to a.Length-1 do
  begin
    print(a[i]);
  end;
  println
end;
      Задание 1: Исправить процедуру PrintArr предыдущего задания 0 так, чтобы за последним элементом символ-разделитель не ставился. Реализовать данную процедуру как процедуру универсального типа.
      Задание 2: Заполнить массив (b) первыми N (N ≥ 0) положительными нечётными числами массива a. Необходимо реализовать два различных решения задачи:

      1. Функция MakeOddArrFunc с одним параметром N, возвращающая массив.
      2. Процедура MakeOddArrProc с двумя параметрами: входным — массив a и выходным параметром — массивом положительный нечетных чисел

      1

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

      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 количество таких элементов
      1

      Пример: Описать функцию 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.
      Задание 6: Дан целочисленный массив, содержащий не менее трёх элементов. Найти значение первого локального минимума. Выполнить задание с помощью пользовательской функции FirstLocMin.

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

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

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

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

      Пример: Дан массив A размера N и целое число K (1<=K<=N). Вывести его элементы с порядковыми номерами, кратными K: 

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

      Условный оператор не использовать.

      Выполнение:

      1
2
3
4

      var n:=ReadInteger;
var a:=ReadArrReal(n);
var k:=ReadInteger;
a[k-1 : : k].Print;
      Задание srez2: Дан массив A размера N (N - четное число). Вывести его элементы с четными номерами в порядке возрастания номеров: 

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

      Условный оператор не использовать.

      Задание srez3: Дан массив A размера N (N - нечетное число). Вывести его элементы с нечетными номерами в порядке убывания номеров: 

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

      Условный оператор не использовать.

      Пример: Дан массив A размера N. Вывести сначала его элементы с четными номерами (в порядке возрастания номеров), а затем - элементы с нечетными номерами (также в порядке возрастания номеров):

      а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);
      Задание srez4: Дан массив A размера N. Вывести сначала его элементы с нечетными номерами (в порядке возрастания номеров), а затем - элементы с четными номерами (в порядке убывания номеров): 

      а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);
      Задание srez6: Дан массив. Поменять в нем первую половину со второй (считать, что длина массива - четное число). Порядок элементов в половинах не менять.
      Например: 

      [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.

      Назад
      К оглавлению
      Далее