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

Работа с динамическими массивами в Паскаль 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);
Вывод массива:
print(a);

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

print(a, '; ');

Или:

printArr(a);

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

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]);;
  3. Цикл foreach
  4. 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);

Следующие методы не меняют сам массив:
a.Min
a.Max
a.Sum
a.Average — среднее арифметическое

Сдвиги

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

Стандартное выполнение:

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)

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

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

Срезы

  • Срезы доступны только на чтение, присваивать им значения нельзя.
  • Тип среза такой же, как у массива.
  • Срезы работают с массивами, строками и со списками.
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.

Пример: Дан массив, вывести его содержимое на экран, разделяя элементы точкой с запятой (процедура 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 так, чтобы за последним элементом символ-разделитель не ставился

Задание 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.

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

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

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

Задание 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.

Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить