Как найти элемент массива по индексу паскаль

Здесь приведены примеры программ и алгоритмов, используемых в курсе Основы программирования для студентов 1 курса ФИИТ мехмата ЮФУ

Редактировать

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

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

  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<N$$.

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

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

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

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

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

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

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 применимы весьма в ограниченном диапазоне натуральных чисел. Для представления факториала договоримся использовать массив. Пример:

В массиве записано значение 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].

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