Как найти количество элементов массива pascal - Avtoru.top

На занятии объясняется, как работать с одномерными массивами в Паскале, как использовать генератор случайных чисел — функцию random в Паскале. Рассматривается пример того, как вывести числа Фибоначчи

Материалы сайта labs-org.ru направлены на практическое освоение языка программирования Pascal. Краткие теоретические сведения не претендуют на полное освещение материала по теме; необходимую информацию можно найти в сети Интернет в большом количестве. В наши же задачи входит предоставление возможности получения практических навыков программирования на Паскале. Решенные наглядные примеры и задания изложены по мере увеличения их сложности, что позволит с легкостью изучить материал с нуля.

Содержание:

Одномерные массивы в Паскале
- Объявление массива
- Инициализация массива
- Вывод элементов массива
- Динамические массивы (pascalAbc.Net)
- Функция Random в Pascal
- Числа Фибоначчи в Паскале
- Максимальный (минимальный) элемент массива
- Поиск в массиве
- Циклический сдвиг
- Перестановка элементов в массиве
- Выбор элементов и сохранение в другой массив
- Сортировка элементов массива

Одномерные массивы в Паскале

Объявление массива

Массивы в Паскале используются двух типов: одномерные и двумерные.
Определение одномерного массива в Паскале звучит так: одномерный массив — это определенное количество элементов, относящихся к одному и тому же типу данных, которые имеют одно имя, и каждый элемент имеет свой индекс — порядковый номер.
Описание массива в Паскале (объявление) и обращение к его элементам происходит следующим образом:

Объявление массива

var dlina: array [1..3] of integer;
begin
dlina[1]:=500; 
dlina[2]:=400; 
dlina[3]:=150;
...

dlina — идентификатор (имя) массива;

для объявления используется служебное слово Array (в переводе с англ. «массив» или «набор»);

[1..3] — в квадратных скобках ставится номер (индекс) первого элемента, затем две точки и индекс последнего элемента массива, т.е. по сути, указывается количество элементов; количество элементов массива называется размерностью массива

of integer (с англ. «из целых чисел») — указывает, к какому типу относится массив, of здесь — служебное слово.

Объявить размер можно через константу:

Инициализация массива

Кроме того, массив может быть сам константным, т.е. все его элементы в программе заранее определены. Описание такого массива выглядит следующим образом:

const a:array[1..4] of integer = (1, 3, 2, 5);

Заполнение последовательными числами:

Результат:
A[1] = 8, A[2] = 9, A[3] = 10, ..., A[N] = A[N-1] + 1

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

Пример: Рассмотрим, как происходит ввод массива в Паскале:

writeln ('введите кол-во элементов: ');
readln(n); {если кол-во заранее не известно, - запрашиваем его}
for i := 1 to n do begin
   write('a[', i, ']=');
   read(a[i]);
   ...
end;
...

✍ Пример результата:

введите кол-во элементов: 
3
a[1]=5
a[2]=7
a[3]=4

Вывод элементов массива

Пример: Рассмотрим, как вывести массив в Паскале:

var
  a: array[1..5] of integer; {массив из пяти элементов}
  i: integer;
begin
a[1]:=2;
a[2]:=4;
a[3]:=8;
a[4]:=6;
a[5]:=3;
writeln('Массив A:');
for i := 1 to 5 do
    write(a[i]:2); {вывод элементов массива}
end.

✍ Пример результата:

Для работы с массивами чаще всего используется в Паскале цикл for с параметром, так как обычно известно, сколько элементов в массиве, и можно использовать счетчик цикла в качестве индексов элементов.

Задача Array 0. Необходимо задать вещественный массив размерностью 6 (т.е. из шести элементов); заполнить массив вводимыми значениями и вывести элементы на экран. Использовать два цикла: первый — для ввода элементов, второй — для вывода.

Пример результата:

введите элемент массива: 3.0
введите элемент массива: 0.8
введите элемент массива: 0.56
введите элемент массива: 4.3
введите элемент массива: 23.8
введите элемент массива: 0.7
Массив =  3, 0.8, 0.56, 4.3, 23.8, 0.7

[Название файла: taskArray0.pas]

В данном примере работы с одномерным массивом есть явное неудобство: присваивание значений элементам.

Обработка массивов в Паскале, так же как и заполнение массива, происходит обычно с использованием цикла for.

Динамические массивы (pascalAbc.Net)

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

Основной особенностью динамических массивов является возможность выделения для них памяти на любом этапе выполнения программы.

Имеется возможность корректировки размера динамического массива как в сторону его уменьшения, так и в сторону увеличения.

Объявление:

var a: array of integer;
var n:=readInteger;
a:=new integer[n]; // инициализация, выделение памяти для элементов массива

или:

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

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

procedure p(a: array of integer);

Созданные элементы сразу получают начальное значение, равное нулевому значению соответствующего типа: для чисел это целый или вещественный нуль, для символов — символ с кодом 0, для строк и других ссылочных типов данных — нулевая ссылка nil

Объявление и инициализация массива:

Пример:

begin
  var a: array of integer;
  a := new integer[3];
  a[0] := 5;
  a[1] := 2;
  a[2] := 3;
end.

или в одну строку:

begin
  var a: array of integer;
  a := new integer[3](5,2,3);
  print(a)
end.

или короткая запись:

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

Элементы динамического массива всегда индексируются от 0.

Ввод элементов:

Пример:

var a:=ReadArrInteger(5); // ввод пяти целых
var a:=ReadArrReal(5); // ввод пяти вещественных

Функции генерации массивов:

1. ArrFill :

var a := ArrFill(10, 1); // массив из 10 целых чисел, равных 1

2. ArrGen :

var a := ArrGen(ReadInteger, 1, e -> e + 2); // массив, состоящий из n первых положительных нечетных чисел
a.Print;

Проход по элементам массива:

Пример:

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

или:

for var i := 0 to a.High do
  a[i] += 1;

Проход по элементам (только для чтения):
Пример:

foreach var x in a do
  Print(x)

Размер динамического массива (т. е. количество его элементов) можно определить с помощью его свойства Length

Для динамического массива определены еще два свойства: Low и High, определяющие соответственно нижнюю и верхнюю границу диапазона изменения индекса. Свойство a.Low всегда возвращает 0, а свойство a.High определяется как a.High = a.Length – 1

Простой вывод элементов:

Writeln(a); // пример вывода: [1,5,3,13,20]

или метод массива Print:

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

Функция Random в Pascal

Для того чтобы постоянно не запрашивать значения элементов массива используется генератор случайных чисел в Паскаль, который реализуется функцией Random. На самом деле генерируются псевдослучайные числа, но суть не в этом.

Для генерации чисел от 0 до n (не включая само значение n, целые числа в интервале [0,N)) используется запись random (n).
Перед использованием функции необходимо инициализировать датчик случайных чисел с помощью процедуры randomize.

Диапазон в Паскале тех самых случайных чисел от a до b задается формулой:

Пример: Заполнение массива случайными числами в Pascal:

var f: array[1..10] of integer;
    i:integer;
begin
randomize;
for i:=1 to 10 do
  begin
   f[i]:=random(10); { интервал [0,9] }   
   write(f[i],' ');
  end;
end.

✍ Пример результата:

Для вещественных чисел в интервале [0,1):

var x: real;
...
x := random(0.0,1.0);;         { интервал [0,1), т.е. единица не включена }

PascalABC.NET:

Сгенерированный случайным образом кортеж из двух (Random2), либо из трех (Random3) элементов:

var (a, b, c) := Random3(10.0, 20.0); // диапазон [10, 20)
write(a:0:2,' ',b:0:2,' ', c:0:2) // 14.73 18.63 19.72

Массив из 10 сгенерированных случайным образом целых чисел в диапазоне [0;99]:

Пример:

var a:=arrRandomInteger(10);

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

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

Задача Array 1. Необходимо задать массив размерностью 5, заполнить массив случайными числами в интервале [-1,1] и вывести элементы на экран: определить три позиции для вывода каждого элемента, с двумя знаками после запятой.

Пример результата:

Массив =  0.22 0.00 -0.69 -0.35 -0.11

[Название файла: taskArray1.pas]

Числа Фибоначчи в Паскале

Наиболее распространенным примером работы с массивом является вывод ряда чисел Фибоначчи в Паскаль. Рассмотрим его.

Пример: Ряд чисел Фибоначчи: 1 1 2 3 5 8 13…

f[0]:=1;   
f[1]:=1; 
f[2]:=2;  
…
или
f[2]:=f[0]+f[1];
f[3]:=f[1]+f[2];
или

Получили формулу элементов ряда.

Пример: Вычислить и распечатать первые 20 чисел Фибоначчи.

var i:integer;
f:array[0..19]of integer;
begin
f[0]:=1;
f[1]:=1;
for i:=2 to 19 do
begin
  f[i]:=f[i-1]+f[i-2];
  writeln(f[i])
end;
end.

На данном примере, становится понятен принцип работы с числовыми рядами. Обычно, для вывода числового ряда находится формула определения каждого элемента данного ряда. Так, в случае с числами Фибоначчи, эта формула-правило выглядит как f[i]:=f[i-1]+f[i-2]. Поэтому ее необходимо использовать в цикле for при формировании элементов массива.

Задача Array 2. Дан ряд из 10 произвольных чисел: a[1], a[2], ... , a[10] (использовать функцию random()). Подсчитать и напечатать суммы троек стоящих рядом чисел: a[1]+a[2]+a[3], a[2]+a[3]+a[4], a[3]+a[4]+a[5], …… , a[8]+a[9]+a[10]

Пример результата:

Массив =  2 0 4 29 3 11 26 11 9 4 
mas[1] + mas[2] + mas[3] = 6
mas[2] + mas[3] + mas[4] = 33
mas[3] + mas[4] + mas[5] = 36
mas[4] + mas[5] + mas[6] = 43
mas[5] + mas[6] + mas[7] = 40
mas[6] + mas[7] + mas[8] = 48
mas[7] + mas[8] + mas[9] = 46
mas[8] + mas[9] + mas[10] = 24

[Название файла: taskArray2.pas]

Задача Array 3. Написать программу решения задачи о печати ряда чисел 2 4 8 16 32 ... 512; для заполнения массива использовать цикл Repeat
[Название файла: taskArray3.pas]

Максимальный (минимальный) элемент массива

Псевдокод:

Поиск максимального элемента по его индексу:

PascalABC.NET:

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

Решение 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.

Задача Array_min: Найдите минимальный элемент массива. Выведите элемент и его индекс.

Пример результата:

9 5 4 22 23 7 3 16 16 8 
Минимальный элемент массива A[7]=3

[Название файла: taskArray_min.pas]

Задача Array 4. Дан массив из 10 целочисленных элементов. Найти количество отрицательных и вывести количество на экран.

Пример результата:

3 4 6 -1 6 -2 1 5 0 1 
Количество отрицательных элементов: 2

[Название файла: taskArray4.pas]

Задача Array 5. Найти минимальное и максимальное из n введенных чисел (массива). Определить расстояние между этими элементами.

3  2  6  1  3  4  7  2  >>>  min=1, max=7, distance=3

[Название файла: taskArray5.pas]

Задача Array 6. Дан целочисленный массив размера N. Вывести все содержащиеся в данном массиве четные числа в порядке убывания их индексов, а также их количество K.

N=4
mas: 8 9 2 5
>>> 2 8 количество= 2

[Название файла: taskArray6.pas]

Задача Array 7. Ввести с клавиатуры массив из 5 элементов, найти в нем два максимальных элемента и их номера.

Пример:

Исходный массив:
4   -5   10  -10  5
максимальные A[3]=10, A[5]=5

[Название файла: taskArray7.pas]

Поиск в массиве

Рассмотрим сложный пример работы с одномерными массивами:

Пример: Дан массив из 10 чисел. Определить, есть ли в массиве число, введенное пользователем. Если есть – выводить «найдено», если нет – «не найдено».
Сложность задания заключается в том, что выводить слова «найдено» или «не найдено» необходимо один раз.

Для решения поставленной задачи понадобится оператор break — выход из цикла.
Решение Вариант 1. Цикл for:

PascalABC.NET:

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.

Рассмотрим эффективное решение:

Задача: найти в массиве элемент, равный X, или установить, что его нет.

Алгоритм:

начать с 1-го элемента (i:=1);
если очередной элемент (A[i]) равен X, то закончить поиск иначе перейти к следующему элементу.

решение на Паскале Вариант 2. Цикл While:

Поиск элемента в массиве

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

Задача Array 8. Заполнить массив из 10 элементов случайными числами в интервале [0..4] и вывести номера всех элементов, равных X.

Пример:

	 Исходный массив:
	 4  0  1  2  0  1  3  4  1  0
	 Что ищем? 0
	 A[2], A[5], A[10]

[Название файла: taskArray8.pas]

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

Пример: сдвинуть элементы массива влево на 1 позицию, первый элемент становится на место последнего.

Решение:

Алгоритм:
A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N];

Программа:

PascalABC.NET:

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

  // …
  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;

Задача Array 9. Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить циклический сдвиг влево без первого элемента.
Пример:

Исходный массив:
  4  -5   3  10  -4  -6   8 -10  1  0
Результат:
  4   3  10  -4  -6   8 -10   1  0 -5

[Название файла: taskArray9.pas]

Перестановка элементов в массиве

Рассмотрим, как происходит перестановка или реверс массива.

Пример: переставить элементы массива в обратном порядке

Решение:

Алгоритм:

Псевдокод:

Программа:

PascalABC.NET:

Перестановка (ревёрс):

Решение 1:

begin
var a: array of integer := (1,3,5,7); 
var n := a.Length;
for var i:=0 to n div 2 - 1 do
    Swap(a[i],a[n-i-1]);
End.

Решение 2 (стандартная процедура Reverse()):

begin
var a:=new integer[10];
a:=arrRandomInteger(10);
print(a);// [41,81,84,63,12,26,88,25,36,72] 
Reverse(a);
print(a) //[72,36,25,88,26,12,63,84,81,41] 
end.

Задача Array 10. Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и сделать реверс всех элементов, кроме последнего.
Пример:

 Исходный массив:
-5  3   10  -4  -6   8 -10  1   0  4
 Результат:
0  1  -10   8  -6  -4  10  3  -5  4

[Название файла: taskArray10.pas]

Выбор элементов и сохранение в другой массив

Пример: найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив

Решение:

Решение: подсчитывать количество найденных элементов с помощью счетчика count, очередной элемент устанавливать на место B[count]. Переменой count необходимо присвоить 1.

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

writeln('Выбранные элементы');
for i:=1 to count-1 do
   write(B[i], ' ')

PascalABC.NET:

Процедура SetLength():

// ...
for var i := 0 to a.length - 1 do 
    if a[i] < 0 then
    begin
      b[j] := a[i];
      j += 1;
    end;
  SetLength(b, j);

Задача Array 11. Заполнить массив случайными числами в интервале [20,100] и записать в другой массив все числа, которые оканчиваются на 0.
Пример:

	 Исходный массив:
	 40   57   30  71  84
	 Заканчиваются на 0:
	 40 30

[Название файла: taskArray11.pas]

Сортировка элементов массива

Сортировка методом «Пузырька»

В таком типе сортировок массив представляется в виде воды, маленькие элементы — пузырьки в воде, которые всплывают наверх (самые легкие).
При первой итерации цикла элементы массива попарно сравниваются между собой:предпоследний с последним, пред предпоследний с предпоследним и т.д. Если предшествующий элемент оказывается больше последующего, то производится их обмен.
При второй итерации цикла нет надобности сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте, он самый большой. Значит, число сравнений будет на одно меньше. То же самое касается каждой последующей итерации.

Pascal

PascalABC.NET

for i:=1 to N-1 do begin
   for j:=N-1 downto i do
     if A[j] > A[j+1] then begin
       с := A[j];
       A[j] := A[j+1];
       A[j+1] := с;
     end;
 end;

for var i := 0 to arr.High - 1 do
    for var j := arr.High - 1 downto i do
      if arr[j] > arr[j + 1] then 
        Swap(arr[j], arr[j + 1]);

Задача Array 12. Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину массива по возрастанию, а вторую – по убыванию (методом ‘Пузырька’).

Пример:
Исходный массив:
14  25  13  30  76  58  32  11  41  97
Результат:
13  14  25  30  76  97  58  41  32  11

[Название файла: taskArray12.pas]

Сортировка методом выбора

в массиве ищется минимальный элемент и ставится на первое место (меняется местами с A[1]);
среди оставшихся элементов также производится поиск минимального, который ставится на второе место (меняется местами с A[2]) и т.д.

Pascal

PascalABC.NET

for i := 1 to N-1 do begin
  min:= i ;
  for j:= i+1 to N do
    if A[j] < A[min] then min:=j; 
  if min <> i then begin
    c:=A[i]; 
    A[i]:=A[min]; 
    A[min]:=c;
  end;
end;

for var i := 0 to a.High-1 do
  begin
    var (min,imin) := (a[i],i);
    for var j := i + 1 to a.High do
      if a[j] < min then
        (min,imin) := (a[j],j);
    Swap(a[imin],a[i]);
  end;

Задача Array 13: Заполнить массив из 10 элементов случайными числами в интервале [0..50] и отсортировать его по возрастанию суммы цифр

Пример:
Исходный массив:
14  25  13  12  76  58  21  87  10  98
Результат:
10  21  12  13  14  25  76  58  87  98

[Название файла: taskArray13.pas]

PascalABC.NET:

Стандартная процедура sort():

Sort(a);
SortByDescending(a);

Быстрая сортировка или quick sort

Алгоритм:

Выбирается и запоминается средний элемент массива (присвоим X):

Инициализируем две переменные (будущие индексы массива): L:=1, R:=N (N — количество элементов).
Увеличиваем L и ищем первый элемент A[L], который больше либо равен X (в итоге он должен находиться справа).
Уменьшаем R и ищем элемент A[R], который меньше либо равен X (в итоге он должен находиться слева).
Смотрим, если L<=R, то меняем местами A[L] и A[R], возвращаемся к пункту 3.

Выполнение на Паскале:

procedure QSort ( first, last: integer);
var L, R, c, X: integer;
begin
  if first < last then begin
    X:= A[(first + last) div 2];
    L:= first; R:= last;
 while L <= R do begin
   while A[L] < X do L:= L + 1;
   while A[R] > X do R:= R - 1;
   if L <= R then begin
     c:= A[L]; A[L]:= A[R]; A[R]:= c;
     L:= L + 1; R:= R - 1;
   end;
 end;
  QSort(first, R);   QSort(L, last);
  end;
end.

Задача Array 14:
Заполнить массив из 10 элементов случайными числами в интервале [-50..50] и отсортировать его с помощью алгоритма быстрой сортировки.

[Название файла: taskArray14.pas]

Источник

Ввод и вывод

const Sz = 100; // Размер массива

var 
  a: array [1..Sz] of integer;
  N: integer; // Количество элементов в массиве
  i: integer;
  
begin
  write('Введите количество элементов в массиве: ');
  readln(N);
  write('Введите элементы массива: ');
  for i:=1 to N do
    read(a[i]);
  write('Вывод элементов массива: ');
  for i:=1 to N do
    write(a[i],' ');
end.

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

const Sz = 100; // Размер массива

var 
  a: array [1..Sz] of integer;
  N: integer; // Количество элементов в массиве
  i: integer;
  
begin
  N := 20;
  for i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива: ');
  for i:=1 to N do
    write(a[i],' ');
end.

Заполнение арифметической прогрессией

const 
  Sz = 100;
  a0 = 5; // Первый элемент арифметической прогрессии
  d = 3;  // Разность арифметической прогрессии

var 
  a: array [1..Sz] of integer;
  N: integer; // Количество элементов в массиве
  
begin
  N := 20;
  a[1] := a0;
  for var i:=2 to N do
    a[i] := a[i-1] + d;
  writeln('Арифметическая прогрессия: ');
  for var i:=1 to N do
    write(a[i],' ');
end.

Заполнение степенями двойки

const 
  Sz = 100;
var 
  a: array [1..Sz] of integer;
  N: integer;   
begin
  N := 20;
  a[1] := 2;
  for var i:=2 to N do
    a[i] := a[i-1] * 2;
  writeln('Степени двойки: ');
  for var i:=1 to N do
    writeln(i:3,a[i]:9);
end.

Заполнение числами Фибоначчи

const 
  Sz = 100;
var 
  a: array [1..Sz] of integer;
  N: integer;   
begin
  N := 20;
  a[1] := 1; 
  a[2] := 1;
  for var i:=3 to N do
    a[i] := a[i-2] + a[i-1];
  writeln('Числа Фибоначчи: ');
  for var i:=1 to N do
    write(a[i],' ');
end.

Инвертирование массива

const 
  Sz = 100;
var 
  a: array [1..Sz] of integer;
  N: integer;   
begin
  N := 20;
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  
    
  for var i:=1 to N div 2 do
    Swap(a[i],a[N-i+1]);
    
  writeln('После инвертирования: ');
  for var i:=1 to N do
    write(a[i],' ');
end.

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

const 
  Sz = 100;
var 
  a: array [1..Sz] of real;
  N: integer;   
  min: real;
  minind: integer;
begin
  N := 20;
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  
  
  min := a[1];
  minind := 1;
  for var i:=2 to N do
    if a[i]<min then 
    begin
      min := a[i];
      minind := i;
    end;
    
  writeln('Минимальный элемент: ',min);
  writeln('Индекс минимального элемента: ',minind);
end.

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

const 
  Sz = 100;
var 
  a: array [1..Sz] of integer;
  N: integer;   
  min: integer;
  minind: integer;
begin
  N := 20;
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  
  
  min := integer.MaxValue;
  for var i:=1 to N do
    if (a[i]<min) and (a[i] mod 2 = 0) then 
    begin
      min := a[i];
      minind := i;
    end;
    
  if min = integer.MaxValue then
    writeln('Четных элементов нет')
  else  
  begin
    writeln('Минимальный четный элемент: ',min);
    writeln('Индекс минимального четного элемента: ',minind);
  end;
end.

Запись четных элементов массива в новый массив

const 
  Sz = 100;
var 
  a,b: array [1..Sz] of integer;
  aN: integer; // Количество элементов в массиве a  
  bN: integer; // Количество элементов в массиве b  
begin
  aN := 20;
  for var i:=1 to aN do
    a[i] := Random(100);
  writeln('Элементы массива: ');
  for var i:=1 to aN do
    write(a[i],' ');
  writeln;  
  
  bN := 0;
  for var i:=1 to aN do
    if a[i] mod 2 = 0 then 
    begin
      bN += 1;
      b[bN] := a[i];
    end;
    
  writeln('Четные элементы массива: ');
  for var i:=1 to bN do
    write(b[i],' ');
end.

Слияние отсортированных массивов в отсортированный

Способ 1.

const 
  aN = 10;      // Количество элементов в массиве a 
  bN = 6;       // Количество элементов в массиве b 
  cN = aN + bN; // Количество элементов в массиве c 

var 
  a: array [1..aN] of integer := (1,5,12,15,47,89,98,112,171,180);
  b: array [1..bN] of integer := (13,44,58,71,73,111);
  c: array [1..сN] of integer;
  ai,bi,ci: integer;
begin
  writeln('Элементы массива a: ');
  for var i:=1 to aN do
    write(a[i],' ');
  writeln;  
  writeln('Элементы массива b: ');
  for var i:=1 to bN do
    write(b[i],' ');
  writeln;  
  
  ci := 1;
  ai := 1;
  bi := 1;
  
  while (ai<=aN) and (bi<=bN) do
  begin
    if a[ai]<b[bi] then
    begin
      c[ci] := a[ai];
      ai += 1;
    end
    else 
    begin
      c[ci] := b[bi];
      bi += 1;
    end;
    ci += 1;
  end;
  while ai<=aN do
  begin
    c[ci] := a[ai];
    ai += 1;
    ci += 1;
  end;
  while bi<=bN do
  begin
    c[ci] := b[bi];
    bi += 1;
    ci += 1;
  end;
    
  writeln('Результат слияния: ');
  for var i:=1 to cN do
    write(c[i],' ');
end.

Способ 2. С барьерным элементом

const 
  aN = 10;      // Количество элементов в массиве a 
  bN = 6;       // Количество элементов в массиве b 
  cN = aN + bN; // Количество элементов в массиве c 

var 
  a: array [1..aN+1] of integer := (1,5,12,15,47,89,98,112,171,180,0); // последний элемент - барьерный
  b: array [1..bN+1] of integer := (13,44,58,71,73,111,0);
  c: array [1..cN] of integer;
  ai,bi,ci: integer;
begin
  writeln('Элементы массива a: ');
  for var i:=1 to aN do
    write(a[i],' ');
  writeln;  
  writeln('Элементы массива b: ');
  for var i:=1 to bN do
    write(b[i],' ');
  writeln;  

  a[aN+1] := integer.MaxValue; // барьерный элемент - самый большой
  b[bN+1] := integer.MaxValue;
  
  ci := 1;
  ai := 1;
  bi := 1;
  
  for ci:=1 to cN do
    if a[ai]<b[bi] then
    begin
      c[ci] := a[ai];
      ai += 1;
    end
    else 
    begin
      c[ci] := b[bi];
      bi += 1;
    end;
    
  writeln('Результат слияния: ');
  for var i:=1 to cN do
    write(c[i],' ');
end.

Сдвиг элементов влево

const N = 10;

var a: array [1..N] of integer;

begin
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  for var i:=1 to N-1 do
    a[i] := a[i+1];
  a[N] := 0;
  
  writeln('После сдвига влево: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  
end.

Сдвиг элементов вправо

const N = 10;

var a: array [1..N] of integer;

begin
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  for var i:=N downto 2 do
    a[i] := a[i-1];
  a[1] := 0;
  
  writeln('После сдвига влево: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  
end.

Удаление элемента

const N = 10;

var 
  a: array [1..N] of integer;
  K: integer;

begin
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  K := Random(1,N);

  for var i:=K to N-1 do
    a[i] := a[i+1];
  
  writeln('После удаления элемента с индексом ',K,':');
  for var i:=1 to N-1 do
    write(a[i],' ');
  writeln;  
end.

Вставка элемента

const 
  N = 10;
  Elem = 666;

var 
  a: array [1..N+1] of integer;
  K: integer;

begin
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  K := Random(1,N);

  for var i:=N downto K do
    a[i+1] := a[i];
  a[K] := 666;  
  
  writeln('После вставки элемента ',Elem,' в позицию ',K,':');
  for var i:=1 to N+1 do
    write(a[i],' ');
  writeln;  
end.

Подсчет количества элементов, удовлетворяющих условию

const N = 20;

var 
  a: array [1..N] of integer;
  K,Count: integer;

begin
  for var i:=1 to N do
    a[i] := Random(10);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  K := Random(10);

  Count := 0;
  for var i:=1 to N do
    if a[i] = K then 
      Count += 1;
  
  writeln('Количество элементов, равных ',K,': ',Count);  
end.

Есть ли элемент, удовлетворяющий условию

const N = 10;

var 
  a: array [1..N] of integer;
  K: integer;
  IsFound: boolean;

begin
  for var i:=1 to N do
    a[i] := Random(15);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  K := Random(15);

  IsFound := False;
  for var i:=1 to N do
    if a[i] = K then 
    begin
      IsFound := True;
      break
    end;
  
  if IsFound then
    writeln('Элемент ',K,' найден')
  else writeln('Элемент ',K,' не найден')  
end.

Сортировка пузырьком

const N = 10;

var 
  a: array [1..N] of integer;

begin
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  for var i:=n downto 2 do
  for var j:=1 to i-1 do
    if a[j+1]<a[j] then
      Swap(a[j+1],a[j]);
  
  writeln('После сортировки пузырьком: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  
end.

Сортировка выбором

const N = 10;

var 
  a: array [1..N] of integer;
  K: integer;
  IsFound: boolean;

begin
  for var i:=1 to N do
    a[i] := Random(100);
  writeln('Элементы массива a: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  

  for var i:=1 to N-1 do
  begin
    var min := a[i]; 
    var ind := i;
    for var j:=i+1 to N do
      if a[j]<min then
      begin
        min := a[j];
        ind := j;
      end;
    a[ind] := a[i];
    a[i] := min;
  end;

  writeln('После сортировки выбором: ');
  for var i:=1 to N do
    write(a[i],' ');
  writeln;  
end.

Ссылки

Программы для начинающих
Сайт PascalABC.NET: Программы и алгоритмы для начинающих

Источник

1 / 1 / 0

Регистрация: 19.11.2010

Сообщений: 23

Определить количество элементов массива

16.12.2010, 11:59. Показов 27758. Ответов 2

Дан числовой массив А, состоящий из n-натуральных чисел. Определить количество элементов массива, являющихся кратными 7. Очень надо, напишите пож прогу)

Shelovek

66 / 66 / 33

Регистрация: 25.05.2010

Сообщений: 176

16.12.2010, 12:03

Сообщение было отмечено sizoichel как решение

Решение

Pascal

uses
    crt;
var
   a:array[1..1000] of integer;
   i,k,n:integer;
begin
     writeln('wvedite razmernost matrici');
     readln(n);
     writeln('wvedite massiv razmerom ',n,' x ',n);
     for i:= 1 to n do
         read(a[i]);
     k:=0;
     for i:= 1 to n do
         begin
              if a[i] mod 7 = 0 then
                 k:=k+1;
         end;
writeln('kol-vo takih shisel ravno ',k);
readkey
end.

1 / 1 / 0

Регистрация: 19.11.2010

Сообщений: 23

16.12.2010, 13:06

[ТС]

Респект те)

Добавлено через 59 минут
не работает… help me!!!

Источник

Сегодня мы с вами наконец-то начинаем новую тему — одномерные массивы.

Одномерные массивы. Определение.

Одномерный массив — это фиксированное количество элементов одного и того же типа, объединенных одним именем, где каждый элемент имеет свой номер. Обращение к элементам массива осуществляется с помощью указания имени массива и номеров элементов.

var 
   a : array [1..N] of integer;

//или
type 
  arr = array[1..N] of integer;

var
  a: arr;

Между именем типа и именем переменной ставится знак «двоеточие». Array — служебное слово (в переводе с английского означает «массив», «набор»); [1..N] — в квадратных скобках указывается номер первого элемента, затем, после двух точек, номер последнего элемента массива; of — служебное слово (в переводе с английского «из»); integer — тип элементов массива.

Индексом могут быть не только натуральные числа: мы можем написать так: [0..10], [-29..45], [‘a’..’z’], [false..true] — то есть нам подходят любые символы и числа — главное соблюсти следующее условие: левая часть меньше правой. Для того чтобы определить, что меньше — восклицательный знак(‘!’) или точка(‘.’) используем таблицу ASCII и функции Ord() и Chr().

Как же производится ввод одномерного массива?

Для того чтобы ввести или вывести значения элементов такого массива, используем цикл с параметром(или с постусловием, или с предусловием — в общем, любой цикл. ).

for i := 1 to N do
   read(a[i]); //где a[i] -- элемент одномерного массива a с индексом (порядковым номером) i.

Как видите, ничего страшного в массивах нет. Массивы применяют в тех случаях, когда нельзя обойтись одной-двумя переменными (примеры таких задач мы рассматривали в решении задач из блока Series). В случаях, когда после ввода последовательности целиком пользователю необходимо обратиться к переменным в середине последовательности, в начале, поменять их значения местами, отсортировать.

Раз уж мы затронули тему задач из блока Series, давайте решим пару задачек оттуда с помощью массивов, а не тем увечным способом, которым нам приходилось пользоваться.

Одномерные массивы. Решение задач.

Series8. Дано целое число N и набор из N целых чисел. Вывести в том же порядке все четные числа из данного набора и количество K таких чисел.

Исходное решение: Series8.

Модифицированное решение:

var
  a: array[1..1000] of integer; {мы не знаем заранее N, поэтому берем с запасом.}
  k, N, i: integer;

begin
  write('N = '); 
  readln(N);  
  write('Введите ', N, ' целых чисел: '); 
  for i := 1 to N do read(a[i]); {заполняем масссив}
  
  {Начинаем выбирать чётные числа}
  write('Чётные числа: ');
  for i := 1 to N do
  begin
    if a[i] mod 2 = 0 then 
    begin
      Inc(k);
      write(a[i], ' ');
    end;
  end;  
  writeln();
  writeln('Количество четных чисел - ', k); 
end.

Series28. Дано целое число N и набор из N вещественных чисел: A₁, A₂, …, A_N. Вывести следующие числа:

(A₁)^N, (A₂)^N−1, …, (A_N−1)², A_N.

Исходное решение: Series28.

Более подробно про возведение числа в степень мы говорили в решении задачи for36.

Модифицированное решение:

var
  a: array[1..1000] of integer; 
  N, i, j, n_pow: integer;
  d, r: real;

begin
  write('N = ');
  readln(N);
  write('Введите ', N, ' целых чисел: '); 
  for i := 1 to N do read(a[i]);
  
  {Возводим элементы массива в степень}
  for i := 1 to N do
  begin
    n_pow := N + 1 - i;
    d := a[i];
    if n_pow mod 2 <> 0 then r := d else r := 1; //в r будет записываться результат
    while n_pow > 1 do
    begin
      n_pow := n_pow div 2;
      d := d * d;
      if n_pow mod 2 <> 0 then r := r * d;
    end;
    writeln(a[i], ' в степени ', N + 1 - i, ' равно ', r);
  end;
end.

Ну и напоследок давайте разберём веселенькую задачу на длинную арифметику.

Задача. Найти факториал числа.

Мы уже решали эту задачу здесь(for19).

Научимся вычислять факториал натурального числа N. Факториал числа — это произведение чисел 1*2*3*…*(N-1 )*N (обозначается как N!). Сложность задачи в том, что уже 8!=40320, а 13!=6227020800. Типы данных Integer, Longlnt применимы весьма в ограниченном диапазоне натуральных чисел. Для представления факториала договоримся использовать массив. Пример:

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]
8	0	0	8	6	1	9	9	3

В массиве записано значение 11!=39916800. Каким образом? В А[0] фиксируется число занятых элементов массива, в А[1] — цифра единиц результата, в А[2] — цифра десятков результата, в А[3] — цифра сотен результата и т. д. Почему так, а не наоборот? Такая запись позволяет исключить сдвиг элементов массива при переносе значений в старший разряд. А сейчас наберите, как обычно, текст программы, выполните компиляцию и, выполните ее в пошаговом режиме, отслеживая изменение значений переменных при не очень большом значении N. Добейтесь полного понимания логики работы программы.

Для того чтобы выполнить программу в пошаговом режиме, нажмите «шаг без входа в подпрограмму» и перейдите в «локальные переменные».

const 
  MaxN = 300;

var
  A: array [0..MaxN] of integer;
  i, j, r, w, N: integer;

begin
  Write('Введите число, факториал которого необходимо подсчитать: ');
  Read(N);
  A[0] := 1;
  A[1] := 1; 
  j := 2; {Начальные присвоения, начинаем вычислять 2! }
  while (j <= N) and (A[0] < MaxN) Do {Второе условие 
  позволяет избежать выхода из границ диапазона, если 
  количество цифр в факториале превзойдет 300.}
  begin
    r := 0;
    i := 1;
    {r - перенос из разряда в разряд при
    выполнении умножения числа j на очередную цифру
    A[i] предыдущего результата.}
    while (i <= A[0]) or (r <> 0) Do 
    begin
      {Пока не
      «прошли» все цифры предыдущего результата или
      есть перенос цифры в старший разряд}
      w := A[i] * j + r;{Умножаем очередную цифру и
      прибавляем цифру переноса из предыдущего
      разряда}
      A[i] := w mod 10; {Оставляем остаток от деления на 10}
      r := w div 10;{Вычисляем значение переноса}
      if A[A[0] + 1] <> 0 then Inc(A[0]);{Изменяем 
      количество элементов, если их количество увеличилось.}
      Inc(i);
    end;
    Inc(j);
  end;
  write('Факториал: ');
  for i := A[0] downto 1 Do Write(A[i]);{Вывод результата}
end.

Подведем итоги:

Одномерный массив — это конечное упорядоченное множество элементов. За первым элементом идет второй, за вторым — третий и т. д. Индекс может быть чем угодно — и целым числом, и символом. Но чаще мы всё-таки будем пользоваться следующим диапазоном: [1.. N].

На сегодня все! Если у вас еще остались вопросы о том, как работает программа выше, оставляйте их в комментариях. И очень скоро мы начнем решать задачи на массивы из задачника М. Э. Абрамяна.

Источник

title	keywords	last_updated	summary	sidebar	permalink	folder
Программы и алгоритмы с использованием массивов	arrays, examples, programs, algorithms	31.12.19	Здесь приведены примеры программ и алгоритмов, используемых в курсе Основы программирования для студентов 1 курса ФИИТ мехмата ЮФУ	mydoc_sidebar	progr_arrays.html	mydoc

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

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

  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. С помощью срезов

Решение 3. С помощью стандартной процедуры

Поиск

Задача. Есть ли в массиве a элемент x

Решение. С помощью операции in или метода Contains:

Задача. Найти индекс первого вхождения элемента 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. С помощью стандартного метода

Количество по условию

Задача. Количество элементов, удовлетворяющих заданному условию

Решение 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. С помощью стандартного метода

Минимумы-максимумы

Задача. Найти минимальный элемент и его индекс

Решение 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. С помощью стандартной функции

Задача. Найти минимальный элемент, удовлетворяющий условию, и его индекс

Решение. Алгоритм

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. С помощью срезов

Задача. Сдвиг вправо

Решение 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. С помощью срезов

Решение 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 -> 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. С помощью стандартного метода

Алгоритмы сортировки

Сортировка выбором

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

Стандартная сортировка

Асимптотическая сложность $$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:];

Решение. В списке — с помощью стандартного метода:

Задача. Дан массив (список) $$N$$ вещественных. Требуется удалить элемент с индексом $$k$$, $$k

Решение. В массиве — с помощью срезов:

var N := ReadInteger;
var a := ReadArrInteger(N);
var l := Lst(a);
var k := ReadInteger;
a := a[:k] + a?[k+1:];

Решение. В списке — с помощью стандартного метода:

{% include links.html %}

Источник

Одномерные массивы в Паскале

Объявление массива

Инициализация массива

Вывод элементов массива

Динамические массивы (pascalAbc.Net)

Функция Random в Pascal

Числа Фибоначчи в Паскале

Максимальный (минимальный) элемент массива

Поиск в массиве

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

Перестановка элементов в массиве

Выбор элементов и сохранение в другой массив

Сортировка элементов массива

Ввод и вывод

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

Заполнение арифметической прогрессией

Заполнение степенями двойки

Заполнение числами Фибоначчи

Инвертирование массива

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

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

Запись четных элементов массива в новый массив

Слияние отсортированных массивов в отсортированный

Способ 1.

Способ 2. С барьерным элементом

Сдвиг элементов влево

Сдвиг элементов вправо

Удаление элемента

Вставка элемента

Подсчет количества элементов, удовлетворяющих условию

Есть ли элемент, удовлетворяющий условию

Сортировка пузырьком

Сортировка выбором

Ссылки

Определить количество элементов массива

Решение

Одномерные массивы. Определение.

Одномерные массивы. Решение задач.

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

Циклы по массиву

Инвертирование

Поиск

Поиск по условию

Количество по условию

Минимумы-максимумы

Сдвиги

Преобразование элементов

Слияние

Бинарный поиск

Алгоритмы сортировки

Сортировка выбором

Пузырьковая сортировка

Сортировка вставками

Стандартная сортировка

Методы и операции для работы cо списками List

Реализация функции Distinct

Вставка и удаление элементов в массиве и списке

Не пропустите также: