Вставка элемента в массив
Требуется добавить элемент в произвольное место массива.
Алгоритм решения задачи:
- Задаем длину массива на один элемент больше, чем он будет заполнен в начале.
- Выясняем значение и позицию добавляемого элемента
- Все элементы до указанной позиции сдвигаем на один назад.
- Присваиваем по указанному индексу (позиции) значение.
- Остальная (передняя) часть массива не изменяется.
Программа на языке Паскаль:
const n = 6; var arr: array[1..n] of integer; i, j, num, id: integer; begin writeln('Заполните массив: '); for i := 1 to n - 1 do readln(arr[i]); write('Ваш массив: '); for i := 1 to n - 1 do write(arr[i]:5); writeln; write('Укажите еще один элемент: '); readln(num); write('Позиция в массиве: '); readln(id); for i := n - 1 downto id do arr[i+1] := arr[i]; arr[id] := num; write(' Ваш массив: '); for i := 1 to n do write(arr[i]:5); writeln; end.TURBO PASCAL
Вставка элементов в одномерный массив
Вставка одного элемента
Вставлять элемент можно до или после данного элемента, номер этого элемента можно вводить с клавиатуры или искать при определённых условиях. Рассмотрим вставку элемента после элемента с данным номером, номер этого элемента будем вводить с клавиатуры.
Вставка элемента после элемента с заданным номером.
Пример
Вставить число 100 после пятого элемента массива.
Пусть k — это номер элемента, после которого мы должны вставить элемент х (k и х будем вводить с клавиатуры). Тогда вставка осуществляется следующим образом:
| первые k элементов массива остаются без изменений; |
| все элементы, начиная с (k+1)-го, необходимо сдвинуть на один назад; |
| на место (k+1)-го элемента записываем значение х, то есть после k-го элемента массива. |
Рассмотрим на конкретном примере. Пусть дан следующий одномерный массив из N (N = 10) элементов: 3, -12, 5, 14, 27, -6, 1, -34, 10, -15.
Надо вставить 100 после пятого элемента массива. Тогда получим следующий массив:
3, -12, 5, 14, 27, 100, -6, 1, -34, 10, -15.
Таким образом, в массиве стало 11 элементов, то есть массив надо определять на N+1 элемент:
Type myarray = Array[1..n+1] Of Integer.
Кроме того, в программе необходимо выводить массив два раза, сначала первые N элементов массива, а затем все N+1 элементы. Поэтому будем использовать уже известную процедуру Print1.
Составим теперь основную программу с использованием новой процедуры Insert1 (k1, x1, m), которой передаются: k1 — номер элемента, после которого надо вставить, х1 — число, которое вставляем, m — массив, в котором делаем преобразования. Кроме того, сдвиг элементов будем начинать с последнего элемента.
Program Example_42;
Const n = 10; dd = 51;
Type myarray = Array[1.. n+1] Of Integer;
Var A : myarray;
x, k : Integer;
Procedure Init2 (Var m: myarray);
Procedure Print1 (n1: Integer; m: myarray);
Procedure Insert1 (k1,x1: Integer; Var m: myarray);
Var i; Integer;
Begin
For i:=n Downto k1+1 Do
m[i+1]:= m[i]
m[k1+1]:= x1;
End;
Рассмотрим выполнение программы по шагам выполнения. Пусть начальное заполнение массива сделано и имеется массив из десяти целых чисел:
3, -12, 5, 14, 27, -6, 1, 34, 10, -15.
Кроме того, пусть первый вывод массива тоже уже сделан и на экране появились 10 целых чисел. Введём номер элемента, после которого будем вставлять новый элемент и сам этот новый элемент:
k = 5 — будем вставлять после пятого элемента;
x = 100 — вставлять будем число 100.
| Сдвиг элементов | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| i | m[1] | m[2] | m[3] | m[4] | m[5] | m[6] | m[7] | m[8] | m[9] | m[10] | m[11] |
| — | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10 | -15=> | — |
| 10 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10=> | -15 | -15 |
| 9 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34=> | 10 | 10 | -15 |
| 8 | 3 | -12 | 5 | 14 | 27 | -6 | 1=> | 34 | 34 | 10 | -15 |
| 7 | 3 | -12 | 5 | 14 | 27 | -6=> | 1 | 1 | 34 | 10 | -15 |
| 6 | 3 | -12 | 5 | 14 | 27 | -6 | -6 | 1 | 34 | 10 | -15 |
| на (k1+1)-ое место записываем значение x1 — m[k1+1] := 100 | |||||||||||
| — | 3 | -12 | 5 | 14 | 27 | 100 | -6 | 1 | 34 | 10 | -15 |
Итак, получили новый массив, который уже имеет N+1 элемент, его и будем выводить на экран. На экране всё это будет выглядеть следующим образом:
3 -12 5 14 27 -6 1 34 10 -15
Номер элемента, после которого вставлять, и вставляемое число
3 -12 5 14 27 100 -6 1 34 10 -15
Вставка элемента перед данным
Пример
Вставить число 100 перед пятым элементом массива.
Эта вставка немногим отличается от предыдущей: в первой сдвигали назад все элементы, стоящие после k-го, то есть с (k+1)-го, а на его место записывали новый элемент, в этой — сдвигаем все элементы с k-го, а затем на его место записываем новый,
Пусть дан следующий одномерный массив из N (N=10) элементов:
3, -12, 5, 14, 27, -6, 1, 34, 10, -15.
Надо вставить 100 перед пятым элементом массива. Тогда получим следующий массив:
3, -12, 5, 14, 100, 27, -6, 1, 34, 10, -15.
Изменим программу для этой вставки:
Program Example_43;
Const n = 10; dd = 51;
Type myarray = Array[1..n+1] Of Integer;
Var A : myarray;
x, k : Integer;
Procedure Init2(Var m: myarray);
Procedure Print1(n1: Integer; m: myarray );
Procedure Insert2(k1, x1: Integer; Var m: myarray );
Var i : Integer;
Begin
For i:=n Downto k1 Do
m[i+1]:=m[i];
m[k1]:=x1;
End;
Begin
Init2(A);
Print1 (n,A);
Writeln (‘Номер элемента, перед которым вставлять,’);
Writeln (‘ u вставляемое число ‘);
Readln (k,x);
Insert2(k,x,A);
Print1(n+1,A);
Readln;
End.
Рассмотрим на том же примере пошаговое выполнение программы. Пусть начальное заполнение массива сделано и имеется массив из десяти целых чисел:
3, -12, 5, 14, 27, -6, 1, -34, 10, -15.
Кроме того, пусть первый вывод мвссива тоже уже сделан и на экране появились 10 целых чисел. Введём номер элемента, перед которым будем вставлять новый элемент и сам этот новый элемент:
| k = 5 — будем вставлять перед пятым элементом; |
| x = 100 — вставляемое число 100. |
| Сдвиг элементов | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| i | m[1] | m[2] | m[3] | m[4] | m[5] | m[6] | m[7] | m[8] | m[9] | m[10] | m[11] |
| — | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10 | -15=> | — |
| 10 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10=> | -15 | -15 |
| 9 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34=> | 10 | 10 | -15 |
| 8 | 3 | -12 | 5 | 14 | 27 | -6 | 1=> | 34 | 34 | 10 | -15 |
| 7 | 3 | -12 | 5 | 14 | 27 | -6=> | 1 | 1 | 34 | 10 | -15 |
| 6 | 3 | -12 | 5 | 14 | 27=> | -6 | -6 | 1 | 34 | 10 | -15 |
| 5 | 3 | -12 | 5 | 14 | 27 | 27 | -6 | 1 | 34 | 10 | -15 |
| на k1-ое место записываем значение x1 — m[k1] := 100 | |||||||||||
| — | 3 | -12 | 5 | 14 | 100 | 27 | -6 | 1 | 34 | 10 | -15 |
Итак, получили новый массив, который уже имеет N+1 элемент, его и будем выводить на экран. На экране всё это будем выглядеть следующим образом:
3 -12 5 14 27 -6 1 -34 10 -15
Номер элемента, перед которым вставлять, и вставляемое число
3 -12 5 14 100 27 -6 1 -34 10 -15
Вставка нескольких элементов
Предположим, что необходимо вставлять не один элемент в массив, а по одному элементу после всех элементов с заданным свойством. Рассмотрим эту вставку на примере вставки после всех элементов с заданным свойством.
Пример
Вставить число после всех элементов массива, кратных 3.
Первое, на что необходимо обратить внимание — это описание массива: на сколько элементов может увеличиться массив? Максимальное количество элементов, после которых будет вставлен новый элемент, совпадает с количеством элементов массива, так как может случиться, что все элементы массива отвечают заданному свойству. Поэтому массив может увеличиться в два раза (это его самая большая размерность), а значит, соответствующее ему описание будет следующим:
Type myarray = Array[1..2*n] Of Integer;
Второе. Если мы будем просматривать элементы массива с начала и вставлять новый после элемента заданным свойством, то номер последнего элемента каждый раз может меняться, кроме того, будем просматриваться и новый (вставленный) элемент и его необходимо будет пропускать («перепрыгивать»), поэтому решение будет не очень эффективным.
Лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент мешать не будет. Кроме того, номер последнего элемента можно будет знать (если знать, сколько элементов вставлено на данный момент), при этом просмотр будет последовательным от N-го до 1-го.
Program Example-44;
Const n = 10; dd = 51;
Type myarray = Array[1.. 2*n] Of Integer;
Var A : myarray;
x, k, i :Integer;
Procedure Init2(Var m: myarray);
Procedure Print1(n1: Integer; m: myarray);
Begin
Init2 (A) Print1(n,A);
Writeln(‘ Введите вставляемое число’);
Readln(x);
k: = 0;
For i:= n Downto 1 Do
If A[i] Mod 3=0 Then Insert3 (i,x,A);
Print1 (n+k,A);
Readln;
End.
Рассмотрим выполнение программы в пошаговом режиме. Будем вставлять после всех элементов, кратных 3, число 100, то есть х = 100. Пусть дан массив из 10-ти элементов:
3, -12, 5, 14, 27, -6, 1, 34, 10, -15.
Пусть так же первый вывод массива сделан. Трассировка примера приведена в таблице 5.
Таким образом, массив увеличился на k элементов.
На экране всё это будет выглядеть следующим образом:
3 -12 5 14 27 -6 1 -34 10 -15
3 100 -12 100 5 14 27 100 -6 100 1 -34 10 -15 100
| Просмотр элементов массива | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| A[i] mod 3 = 0 | k | i | массив | ||||||
| да | 0 | 10 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15 | ||||||
| вставляем 100 после i-го (десятого) | |||||||||
| 1 | 10 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | |||||||
| нет | 1 | 9 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| нет | 1 | 8 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| нет | 1 | 7 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| да | 1 | 6 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| вставляем 100 после i-го (шестого) | |||||||||
| 2 | 6 | 3, -12, 5, 14, 27, -6, 100, 1, 34, 10, -15, -15, 100 | |||||||
| да | 2 | 5 | 3, -12, 5, 14, 27, -6, 100, 1, 34, 10, 10, -15, 100 | ||||||
| вставляем 100 после i-го (пятого) | |||||||||
| 3 | 5 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | |||||||
| нет | 3 | 4 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| нет | 3 | 3 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| да | 3 | 2 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| вставляем 100 после i-го (второго) | |||||||||
| 4 | 2 | 3, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | |||||||
| да | 4 | 1 | 3, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| вставляем 100 после i-го (первого) элемента | |||||||||
| да | 5 | 1 | 3, 100, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
На главную страницу
(с)Все права защищены
По всем интересующим вопросам прошу писать на электронный адрес
Массивы в PascalABC.NET
В PascalABC.NET рекомендуется использовать динамические массивы. В отличие от статических, они имеют огромное количество методов и операций, просты в создании, заполнении и выводе.
Описание и выделение памяти
Динамический массив описывается так:
begin var a: array of integer; end. Память под динамический массив a выделяется в момент работы программы:
begin var a: array of integer; var n := ReadInteger; a := new integer[n]; end. Здесь — первое преимущество динамических массивов — в переменной a может храниться массив любого размера, память выделяется в процессе работы программы. Кроме того, выделенная память гарантированно автоматически заполняется нулевыми значениями.
Можно совместить описание и выделение памяти — тип динамического массива выводится автоматически:
begin var n := ReadInteger; var a := new integer[n]; end. Обычно в PascalABC.NET совмещают описание динамического массива, выделение памяти и заполнение значениями. Самый простой способ — заполнить n нулями:
begin var n := ReadInteger; var a := |0| * n; end. Индексация в динамических массивах и использование статических массивов
Динамические массивы индексируются с нуля — это эффективно. В качестве индексов в динамических массивах могут выступать только целые.
Статические массивы тем не менее иногда удобно использовать — в задачах, где индексы либо символьные, либо по-существу начинаются не с нуля. Например, для подсчёта количества слов на каждую букву может использоваться стаический массив
var a := array ['a'..'z'] of integer;
Заполнение статических массивов — увы — производится в цикле. Кроме того, они не помнят свою длину и передача таких массивов в качестве параметров подпрограмм связана с техническими сложностями 40-летней давности, не нужными начинающим.
Простейшее заполнение
Важную роль играют функции заполнения динамических массивов. Перед заполнением они выделяют для массива память, поэтому в одной строке можно совмещать описание, выделение памяти и заполнение.
Простейшее заполнение — набором значений:
var a := |1,3,3,7,9|; Заполнение диапазоном целых или символьных значений делается с использованием функции Arr:
var a := Arr(1..9); var b := Arr('a'..'z'); Заполнение определённым значением осуществляется с помощью операции умножения массива на число:
begin var n := ReadInteger; var a := |0| * n; // массив из n нулей end. Для заполнения можно также использовать функцию ArrFill:
begin var n := ReadInteger; var a := ArrFill(n,0); // массив из n нулей end. Для заполнения массива случайными значениями следует использовать
begin var n := ReadInteger; var a := ArrRandomInteger(n); // по умолчанию значения от 0 до 100 var a1 := ArrRandomInteger(n,1,10); // случайные от 1 до 10 var r := ArrRandomReal(n); // по умолчанию значения от 0 до 10 var r1 := ArrRandomReal(n,2,5); // случайные вещественные от 2 до 5 end. Не рекомендуется использовать алгоритм для заполнения массива случайными в каждой задаче:
begin var n := ReadInteger; var a := new integer[n]; for var i:=0 to n-1 do a[i] := Random(0,100); end. Повторять этот текст в каждой задаче — странно. Для этого есть стандартные функции.
Ввод и вывод элементов массива
Для ввода элементов массива базовых типов используются функции
begin var n := ReadInteger; var a := ReadArrInteger(n); var r := ReadArrReal(n); var s := ReadArrString(n); // . end. Стандартная процедура вывода Write или Print выводит значения в массиве в квадратных скобках черезх запятую:
begin var a := Arr(1..9); Print(a); // [1,2,3,4,5,6,7,8,9] end. Однако лучше всего для вывода воспользоваться методом Print, выводящим все значения в массиве через пробел:
begin var a := Arr(1..9); a.Print; // 1 2 3 4 5 6 7 8 9 end. Не рекомендуется вводить и выводить элементы массива в цикле
begin var n := ReadInteger; var a := new integer[n]; for var i:=0 to n-1 do a[i] := ReadInteger; end. Повторять этот текст в каждой задаче — странно. Для этого есть стандартные функции.
Циклы по массиву
Для обработки элементов массива используются следующие циклы:
-
Цикл for по индексам (если требуется менять элементв или нужна информация об индексах)
for var i:=0 to a.Length-1 do a[i] *= 2; var sum := 0; foreach var x in a do sum += x; foreach var i in a.Indices do a[i] += 2; var (K,L) := ReadInteger2; foreach var i in K..L do a[i] := 777; Пример. Найти количество чётных элементов, стоящих на чётных местах
begin var a := ArrRandomInteger(10); a.Println; var count := 0; foreach var i in a.Indices do if i.IsEven and a[i].IsEven then count += 1; Print(count); end. Методы массива
Массивы содержат большое количество стандартных методов:
a.Length - длина массива a.Min - минимальный элемент в массиве a.Max - максимальный элемент в массиве a.IndexMin - индекс первого минимального элемента в массиве a.IndexMax - индекс первого максимального элемента в массиве a.Sum - сумма элементов в числовом массиве a.Product - произведение элементов в числовом массиве a.Average - среднее элементов в числовом массиве a.First - первый элемент в массиве a.Last - последний элемент в массиве a.IndexOf(x) - индекс первого значения x или -1 если не найдено a.Replace(x,y) - заменить в массиве все значения x на y Кроме того, доступны процедуры
Sort(a) - сортировка элементов по возрастанию SortDescending(a) - сортировка элементов по убыванию Reverse(a) - инвертирование элементов массива Методика. Обращаем внимание, что в методических целях естественно рассказывать, как эти алгоритмы устроены “внутри”. Но потом следует пользоваться стандартными алгоритмами, а не заставлять учеников во всех задачах использовать рукописные сортировки или рукописный поиск минимума. Например, рекомендуется показать, как накопить сумму элементов массива:
begin var a := ArrRandomInteger(10); a.Println; var sum := 0; foreach var x in a do sum += x; Print(sum); end. Здесь следует обратить внимание, что этот алгоритм может быть легко модифицирован в алгоритм нахождения суммы элементов по условию: например, всех чётных элементов:
begin var a := ArrRandomInteger(10); a.Println; var sum := 0; foreach var x in a do if x.IsEven then sum += x; Print(sum); end. Отметим, что заполнение случайными и вывод — это технические части программы, которые делаются в PascalABC.NET в одну строку, позволяя концентрироваться на алгоритме.
Если условие надо накладывать на индексы, то в этом случае (и только в этом случае) следует использовать цикл for по индексам:
begin var a := ArrRandomInteger(10); a.Println; var sum := 0; for var i:=0 to a.Length-1 do if i.IsEven then sum += a[i]; Print(sum); end. Для нахождения суммы без условия необходимо использовать стандартный метод a.Sum:
begin var a := ArrRandomInteger(10); a.Println; Print(a.Sum); end. Отметим также, что для поиска суммы по условию также имеется короткая однострочная запись. Она требует использование стандартного метода Where с параметром, являющимся лямбда-выражением. Лямбда-выражения мы будем рассматривать далее:
begin var a := ArrRandomInteger(10); a.Println; Print(a.Where(x -> x.IsEven).Sum); end. Методика. Поскольку данная запись использована здесь впервые, обращаем внимание на её высокую универсальность: алгоритмы фильтрации и поиска суммы не слиты в один алгоритм, а используются порознь один за другим, что позволяет:
- Лучше читать код (потому что он записан компактно и методами с понятными и очевидными названиями)
- Лучше модифицировать код
- Решать более сложные и более прикладные задачи за одно и то же время урока
Далее лямбда-выражения объясняются подробно и тщательно и используются повсеместно.
Операции с массивами
x in a - возвращает true если значение x содержится в a a1 + a2 - возвращает массив, образованный слиянием массивов a1 и a2 a1 * n - возвращает массив, состоящий из n раз повторенных значений массива a Изменение размера динамического массива
Если в процессе работы программы требуется чтобы динамический массив менял свой размер, то следует … пользоваться типом List ! Это — динамический массив с возможностью эффективного измненения размера и рядом дополнительных методов. Основным является методы Add — добавить в конец:
begin var l := new Listinteger>; l.Add(1); l.Add(3); l.Add(5); l.Print end. Для первоначального заполнения списков List используется короткая фунеция Lst:
begin var l := Lst(1,3,5); l.Print end. При необходимости список List можно преобразовать к динамическому массиву, вызвав метод .ToArray:
begin var l := Lst(1,3,5); var a := l.ToArray; end. Большинство методов, которые имеются в массивах, есть и в списках List. Поэтому выбор типа List или array of для контейнера при решении задач определяется тем, будет ли данный контейнер расширяться по ходу работы программы.
©2023 PascalABCNET Team. All rights reserved.
Page last updated: 19.12.2020
Site last generated: Dec 20, 2023
Массивы
Задача. Заменить отрицательные элементы на противоположные по знаку. Для этого опишем процедуру. Ей будем передавать параметры — количество элементов в массиве и массив, который будет также и результатом выполнения процедуры, так как некоторые его элементы могут быть заменены.
| Procedure Zamena (Var m : MyArray; n:integer); Var i : integer; Begin for i := 1 to n do if m[i] < 0 then m[i] := -m[i]; End; |
Нахождение номеров элементов с заданным свойством
Задача. Найти и вывести на экран номера четных элементов. Для решения задачи необходимо просмотреть весь массив, и если просматриваемый элемент является четным, то выводить его номер.
| Procedure PoiskChet(m : MyArray; n:integer); Var i : integer; Begin for i := 1 to n do if m[i] mod 2 =0 then Write(i:5); End; |
Нахождение количества элементов с заданным свойством
Задача. Найти количество положительных и отрицательных элементов в данном массиве. Опишем процедуру, которой будем отправлять параметры — массив, количество элементов в массиве и два счетчика, один для элементов, больших нуля, а второй — для отрицательных элементов.
| Procedure OtrPol(m : MyArray; n:integer; Var k1, k2 : Integer); Var i : integer; Begin k1 :=0; k2 :=0; for i := 1 to n do if m[i] > 0 then Inc(k1) else if m[i] < 0 then Inc(k2); End; |
Есть ли в данном массиве элементы с данным свойством?
Для решения таких задач удобнее использовать циклы с условиями и составлять функции, результат которых имеет логический тип. Задача. Есть ли отрицательный элемент в массиве? Начинаем с первого элемента (i=1). Пока не просмотрен последний элемент (i<=n) и не найден отрицательный (m[i]>=0), будем переходить к следующему (Inc(i)). Таким образом, мы закончим просмотр массива в одном из двух случаев: первый – просмотрели все элементы и не нашли отрицательный, тогда i>n, второй – нашли нужный, при этом i
| Function Control (m : MyArray; n:integer) : Boolean; Var i : integer; Begin i := 1; while (i<=n) and (m[i]>0) do Inc(i); Control := (i<=n); End; |