Методы и операции для работы с массивами
Объявление и выделение памяти
var n := ReadInteger;
var a: array of integer;
a := new integer[n];
или
var n := ReadInteger;
var a := new integer[n];
Ввод-вывод
var a := ReadArrInteger(n);
var r := ReadArrReal(n);
Print(a);
a.Println;
a.Println(', ');
Заполнение
a := |1,3,7|;
a := Arr(1..10);
a := ArrFill(10,666);
a := ArrGen(n,i->elem(i)[,from:=0])
a := ArrGen(n,first,x->next(x))
a := ArrGen(n,first,second,(x,y)->next(x,y))
Примеры:
a := ArrGen(10,1,x -> x + 2); // 1 3 5 7 9 11 13 15 17 19
a := ArrGen(10,1,x -> x * 2); // 1 2 4 8 16 32 64 128 256 512
a := ArrGen(10,1,1,(x,y) -> x + y); // 1 1 2 3 5 8 13 21 34 55
Заполнение случайными числами
a := ArrRandomInteger(n[,from,to]);
r := ArrRandomReal(n[,from,to]);
Срезы
var a := Arr(0..9);
a[2:5] // 2 3 4
a[:2] // 0 1
a[5:] // 5 6 7 8 9
a[:] // копия массива a
a[::2] // 0 2 4 6 8
a[1::2] // 1 3 5 7 9
a[5:2:-1] // 5 4 3
a[::-1] // 9 8 7 6 5 4 3 2 1 0
Операции + и *
var a := |1,2,3|;
var b := |4,5,6|;
a + b // 1 2 3 4 5 6
a * 2 // 1 2 3 1 2 3
|0|*3 + |1|*3 // 0 0 0 1 1 1
(|0| + |1|)*3 // 0 1 0 1 0 1
Циклы по массиву
For
for var i:=0 to a.Length-1 do
a[i] += 1;
Foreach
foreach var x in a do
Print(x);
Foreach по индексам
foreach var i in a.Indices do
a[i] *= 2;
Foreach по определённым индексам
foreach var i in a.Indices(x -> x in 10..20) do
a[i] += 1;
foreach var i in a.Indices((x,i) -> i.IsEven and (x > 0)) do
a[i] += 1;
Инвертирование
Задача. Инвертировать массив
Решение 1. Алгоритм
procedure Reverse<T>(a: array of T);
begin
var n := a.Length;
for var i:=0 to n div 2 - 1 do
Swap(a[i],a[n-i-1]);
end;
Решение 2. С помощью срезов
a := a[::-1]
Решение 3. С помощью стандартной процедуры
Reverse(a)
Поиск
Задача. Есть ли в массиве a элемент x
Решение. С помощью операции in или метода Contains:
x in a
a.Contains(x)
Задача. Найти индекс первого вхождения элемента x
Решение 1. С использованием break
function IndexOf<T>(a: array of T; x: T): integer;
begin
Result := -1;
for var i := 0 to a.High do // a.High = a.Length - 1
if a[i] = x then
begin
Result := i;
break;
end;
end;
Решение 2. Без использования break
function IndexOfW<T>(a: array of T; x: T): integer;
begin
var n := a.Length;
var i := 0;
while (i<n) and (a[i]<>x) do
i += 1;
Result := i=n ? -1 : i;
end;
Решение 3. Поиск с барьером
Добавим в конец массива барьер, равный x. В массиве должно быть место под этот элемент
function IndexOfWithBarrier<T>
(a: array of T; n: integer; x: T): integer;
begin
Assert((0 < n) and (n < a.Length));
a[n] := x; // барьер
var i := 0;
while a[i]<>x do
i += 1;
Result := i=n ? -1 : i;
end;
За счет использования барьера экономится одна операция сравнения
Решение 4. Стандартные методы
a.IndexOf(x)
a.LastIndexOf(x)
Поиск по условию
Задача. Поиск по условию
Решение 1. Алгоритм
function FindIndex<T>(a: array of T; cond: T->boolean): integer;
begin
Result := -1;
for var i := 0 to a.High do
if cond(a[i]) then
begin
Result := i;
break;
end;
end;
Решение 2. С помощью стандартного метода
a.FindIndex(cond)
Количество по условию
Задача. Количество элементов, удовлетворяющих заданному условию
Решение 1. Алгоритм
function Count<T>(a: array of T; cond: T->boolean): integer;
begin
Result := 0;
foreach var x in a do
if cond(x) then
Result += 1;
end;
Решение 2. С помощью стандартного метода
a.Count(условие)
Минимумы-максимумы
Задача. Найти минимальный элемент и его индекс
Решение 1. Алгоритм
function MinElemAndIndex(a: array of real): (real,integer);
begin
var (min, minind) := (real.MaxValue, -1);
for var i:=0 to a.Length-1 do
if a[i]<min then
(min, minind) := (a[i], i);
Result := (min, minind)
end;
Решение 2. С помощью стандартной функции
a.Min
a.IndexMin
Задача. Найти минимальный элемент, удовлетворяющий условию, и его индекс
Решение. Алгоритм
function MinElemAndIndexCond(a: array of real: cond: real -> boolean):
(real,integer);
begin
var (min, minind) := (real.MaxValue, -1);
for var i:=0 to a.Length-1 do
if (a[i]<min) and cond(a[i]) then
(min, minind) := (a[i], i);
Result := (min, minind)
end;
Сдвиги
Задача. Сдвиг влево на 1
Решение 1. Алгоритм
procedure ShiftLeft<T>(a: array of T);
begin
for var i:=0 to a.Length-2 do
a[i] := a[i+1];
a[a.Length-1] := default(T);
end;
Решение 2. С помощью срезов
a := a[1:] + |0|;
Задача. Сдвиг вправо
Решение 1. Алгоритм
procedure ShiftRight<T>(a: array of T);
begin
for var i:=a.Length-1 downto 1 do
a[i] := a[i-1];
a[0] := default(T);
end;
Решение 2. С помощью срезов
a := |0| + a[:a.Length-1];
Задача. Циклический сдвиг вправо
Решение 1. Алгоритм
procedure CycleShiftRight<T>(a: array of T);
begin
var v := a.Last;
for var i:=a.Length-1 downto 1 do
a[i] := a[i-1];
a[0] := v;
end;
Решение 2. С помощью срезов
var m := a.Length-1;
a := a[m:] + a[:m];
Задача. Циклический сдвиг влево на k
Решение 1. С помощью срезов
a := a[k:] + a[:k];
Решение 2. С помощью частичного Reverse
Reverse(a,0,k);
Reverse(a,k,a.Length-k);
Reverse(a);
Преобразование элементов
Задача. Требуется преобразовать элементы массива по правилу $$x -> f(x)$$
Решение 1. Алгоритм
procedure Transform<T>(a: array of T; f: T -> T);
begin
for var i:=0 to a.Length-1 do
a[i] := f(a[i]);
end;
Решение 2. С помощью стандартного метода
a.Transform(x -> x*x)
Для преобразования части элементов:
a.Transform(x -> if x mod 2 = 0 then x*x else x)
Слияние
Задача. Слияние двух упорядоченных массивов в один упорядоченный
В массивах должно быть место под один барьерный элмент
function Merge(a,b: array of real; n,m: integer):
array of real;
begin
Assert((0 < n) and (n < a.Length));
Assert((0 < m) and (m < b.Length));
a[n] := real.MaxValue; // барьер
b[m] := real.MaxValue; // барьер
SetLength(Result,m+n);
var (ia,ib) := (0,0);
for var ir:=0 to n+m-1 do
if a[ia]<b[ib] then
begin
Result[ir] := a[ia];
ia += 1;
end
else
begin
Result[ir] := b[ib];
ib += 1;
end;
end;
Бинарный поиск
Задача. Поиск в упорядоченном массиве
Решение 1. Алгоритм
function BinarySearch(a: array of integer; x: integer): integer;
begin
var k: integer;
var (l,r) := (0, a.Length-1);
repeat
k := (l+r) div 2;
if x>a[k] then
l := k+1
else r := k-1;
until (a[k]=x) or (l>r);
Result := a[k]=x ? k : -1;
end;
Асимптотическая сложность $$\Theta(\log n)$$
Решение 2. С помощью стандартного метода
a.BinarySearch(x)
Алгоритмы сортировки
Сортировка выбором
procedure SortByChoice(a: array of integer);
begin
for var i := 0 to a.High-1 do
begin
var min := a[i];
var imin := i;
for var j := i + 1 to a.High do
if a[j] < min then
begin
min := a[j];
imin := j;
end;
Swap(a[imin],a[i]);
end;
end;
С использованием срезов:
procedure SortByChoice(a: array of integer);
begin
for var i := 0 to a.High-1 do
Swap(a[a[i:].IndexMin + i],a[i]);
end;
Асимптотическая сложность $$\Theta(n^2)$$
Пузырьковая сортировка
procedure BubbleSort(a: array of integer);
begin
for var i := 0 to a.High-1 do
for var j := a.High downto i+1 do
if a[j] < a[j-1] then
Swap(a[j], a[j-1]);
end;
Асимптотическая сложность $$\Theta(n^2)$$
С флагом (эффективнее в ситуациях, когда массив частично отсортирован):
procedure BubbleSort2(a: array of integer);
begin
var i := a.High;
var q: boolean;
repeat
q := true;
for var j := 0 to i - 1 do
if a[j+1] < a[j] then
begin
Swap(a[j+1], a[j]);
q := false;
end;
i -= 1;
until q;
end;
Асимптотическая сложность $$\Theta(n^2)$$ в среднем и $$\Theta(n)$$) в лучшем случае (когда массив отсортирован).
Сортировка вставками
procedure SortByInsert(a: array of integer);
begin
for var i:=1 to a.High do
begin
var x := a[i];
var j := i - 1;
while (j >= 0) and (x < a[j]) do
begin
a[j+1] := a[j];
j -= 1;
end;
a[j+1] := x;
end;
end;
Асимптотическая сложность $$\Theta(n^2)$$
Стандартная сортировка
Sort(a);
Асимптотическая сложность $$\Theta(n \cdot \log n)$$
Методы и операции для работы cо списками List
Список List<T> – это динамический массив с возможностью динамического изменения размеров по ходу работы программы.
Объявление списка:
var l := new List<integer>;
Добавление элементов в конец списка:
l.Add(5); // список расширяется, выделяя память под новые элементы
l.Add(3);
l.Add(4);
l += 8; // синоним l.Add(8)
Цикл по списку:
for var i:=0 to l.Count-1 do
Print(l[i]);
foreach var x in l do
Print(x);
Заполнение списка:
var l := Lst(5,2,3);
var l1 := Lst(1..10);
Операции со списками:
var l := Lst(5,2,3);
Print(2 in l); // True
Print(2 * l); // [5,2,3,5,2,3]
l.Print; // 5 2 3
Print(l + Lst(7,6,8)); // 5 2 3 7 6 8
Методы списков:
l.Insert(ind,x); // вставка x по индексу ind
l.RemoveAt(ind); // удаление элемента по индексу ind
l.RemoveRange(ind,count) // удаление диапазона элементов
l.RemoveAll(x -> x.IsOdd); // возвращает число удалённых элементов
l.IndexOf(3); // индекс первого вхождения или -1
l.FindIndex(x -> x > 4); // индекс первого вхождения или -1
l.Clear; // очищает список
l.Reverse; // инвертирует список
l.Sort; // сортирует список
Реализация функции Distinct
Задача. Реализовать функцию Distinct, по заданному массиву возвращающая список только различных элементов массива
Решение. Алгоритм
function Distinct(a: array of T): List<T>;
begin
Result := new List<T>;
foreach var x in a do
if not (x in Result) then
Result += x;
end;
Вставка и удаление элементов в массиве и списке
Задача. Дан массив (список) $$N$$ вещественных. Требуется вставить элемент $$x$$ на $$k$$-тое место (начиная с 0), $$k \leq N$$.
Решение. В массиве - с помощью срезов:
var N := ReadInteger;
var a := ReadArrInteger(N);
var l := Lst(a);
var k := ReadInteger;
a := a[:k] + |x| + a?[k:];
Решение. В списке - с помощью стандартного метода:
l.Insert(k,x);
Задача. Дан массив (список) $$N$$ вещественных. Требуется удалить элемент с индексом $$k$$, $$k<N$$.
Решение. В массиве - с помощью срезов:
var N := ReadInteger;
var a := ReadArrInteger(N);
var l := Lst(a);
var k := ReadInteger;
a := a[:k] + a?[k+1:];
Решение. В списке - с помощью стандартного метода:
l.RemoveAt(k);