Как составить алгоритм решения задач с массивами

Используя
команды повторения можно коротким
алгоритмом описать большой объем
действий, необходимых для решения
поставленной задачи. Массивы играют
аналогичную роль по отношению к данным
и позволяют коротким алгоритмом описать
действия с огромным объемом информации.

Применение массивов
при описании алгоритмов решения
практических задач позволяет:

1. записать коротким
   алгоритмом работу с большим объемом
   информации;

2. расширить область
   применимости алгоритма.

Необходимость в
применении массивов для описания
алгоритмов решения задач возникает,
когда при решении задач приходится
иметь дело с большим, конечным количеством
однотипных упорядоченных по индексам
объектов.

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

При работе с
массивами, каждому массиву дается имя.
Работа с массивом – это работа с
элементами массива. Элементу массива
дается имя, соответствующее имени
массива, и указывается в квадратных или
круглых скобках порядковый номер этого
элемента в массиве.

Очевидно, чтобы
задать массив (таблицу), необходимо:

1. указать, что
   однотипные объекты объединены в массив
   (таблицу);

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

3. указать тип
   значений элементов массива (таблицы).

При описании
массива после имени массива будем в
круглых (квадратных) скобках указывать
начальный и конечный номера каждого
индекса элементов массива через
двоеточие. Если массив многомерный, то
описание начального и конечного номеров
каждого индекса элементов массива
разделим запятой. Например, А(1:50) –
массив, элементы которого: А(1), А(2), … ,
А(50); В(1:2,1:3) – массив, элементы которого:

.

Пример 1.
Одномерный массив Осадки (1:365) –
количество осадков в течение года.

Пример 2.
Двумерный массив Расписание (1:4,1:2) –
расписание уроков на 2 дня в 4 классе
общеобразовательной школы.

Массивы
имеют размер и размерность. Размер
массива –
это количество
элементов
в данном массиве, размерность
– количество
индексов,
необходимых для однозначного определения
места фиксированного элемента массива.
Массив примера 1 имеет размерность,
равную 1 (одномерный), размер – 365. Массив
примера 2 имеет размерность равную 2
(двумерный), размер 2∙4=8. Элемент массива
называется переменной с индексом,
переменная без индекса – простой
переменной. Над элементами массива
можно производить те операции, которые
допустимы для базового типа.

В
качестве типов индексов элементов
массива можно использовать целый тип.
Индексы могут задаваться константами,
переменными и выражениями. Значения
переменных и выражений задают номер
элемента массива, поэтому их значения
должны быть определены при обращении
к этому элементу. Элементами массива
могут быть значения любого типа данной
реализации языка.

Пример 3.
Пусть массив A
– одномерный массив, имеющий 4 элемента
целого типа – integer:
-12, 0, 41, -131.

направление изменения
индекса

1
2 3 4

A[1]=-12;
если
i=2,
то
A[i]=0;
если
i=1,
j=3,
то
A[i+j]=-131

Пример 4.
Массив Q
– двумерный массив, имеющий 3 строки и
4 столбца – 12 элементов вещественного
типа – real:

.

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

1 2 3 4

н

аправление

изменения

первого

и
ндекса

Q[3,3]=-28;
если
i=1,
j=2,
s=2,
то
Q[i∙s,j+2]=Q[2,4]=5,121

З
адача
21. Произведение
элементов массива. Составьте блок-схему
алгоритма нахождения произведения
вещественных чисел

П =
a(1)a(2)…a(n).

Решение.
Смотри
блок-схему алгоритма (задача 21),
использована циклическая структура
«while
P
do
S».

Произведение можно
находить так:

П:=а(1); П:=Па(2);
… ; П:=Па(n).

В блок-схеме вместо
этой цепочки операторов запишем оператор
П:=Па(k),
где k
изменяется от 1 до n;
k
– параметр цикла. Чтобы значение первого
произведения было равно a₁,
следует положить начальное значение П
равным 1. Операторы 5-6 составляют тело
цикла.

Задача 22.
Произведение матриц. Составьте блок-схему
нахождения произведения матрицы А
на матрицу В:

,

.

Решение.
Смотри блок-схемы 1-3 алгоритма (задача
22).

Смотри блок-схему
1 (задача 22). Произведение матрицы А
на матрицу
В
есть матрица-столбец; обозначим ее С.

,
где

,
i=1,2,…,m.

Функциональный
блок, вычисляющий величину c(i),
обозначим S₁.
Смотри блок-схему 2 (задача 22).

П


олучать
элементы c(i)
при фиксированном i
можно так: c(i) = c(i)+a(i,j)∙b(j),
где 1jn,
а начальное значение c(i)
равно 0.

Очевидно, что
функциональный блок S₁
будет содержать циклическую структуру,
например, структуру «repeat
S
until
P».

Подставив
детализацию блока S₁
(блок-схема 2 (задача 22)) в блок-схему 1
(задача 22), получим одну циклическую
структуру внутри другой, вложенные
циклы – блок-схема 3(задача 22).

Задача
23.
Положительные числа. Дана числовая
последователь­ность a₁,
a₂,
… , a_n.
Определите, есть ли среди a_i,
1in
положительные числа, если да, то
переменной K
присвойте значение 1, в противном случае
– значение 0. Составьте блок-схему
алгоритма решения поставленной задачи.

Решение.
Смотри блок-схему алгоритма (задача
23).

Б

лок-схема
алгоритма
(задача
23):
Блок-схема
алгоритма (задача
24):

Поскольку
положительный элемент может оказаться
на i-ом
месте, где i<n,
то нужно иметь возможность выйти из
цикла при i<n.
С этой целью перед началом цикла
переменной K
присвоено значение 0, а если a_i>0
– истинно, K
получит значение 1. Проверка окончания
организована так, что выход из цикла
произойдёт или при i>n
(положительного элемента нет), K
= 0, или при
i>n
и K = 1
(этот элемент – последний в массиве),
или при i<n
и K
= 1 (положительный
элемент – a_i,
где 1in–1).

Задача 24.
Поиск
буквы. Пусть w
– слово, состоящее из n
букв русского алфавита: w(1),
w(2),
… , w(n);
v
– буква, относительно которой требуется
установить, входит ли она в слово. Если
входит, то укажите номер позиции первого
вхождения буквы в слово. Составьте
блок-схему алгоритма решения поставленной
задачи.

Решение.
Смотри блок-схему алгоритма (задача
24).

Будем просматривать
последовательно все буквы данного
слова. Для реализации этого используем
цикл с постусловием. Если буква v
не входит в слово, то выход из цикла
осуществляется при i>n,
где i
– номер рассматриваемой буквы. Значение
переменной K
в этом случае равно 0. Если буква v
входит в слово, выход из цикла может
быть осуществлен раньше, чем i
станет больше n,
при K<>
0, где K
– номер позиции первого вхождения
буквы v
в слово w.

Задача 25.
Количество
положительных элементов. Дана
последовательность чисел a₁,
a₂,
… , a_n.
Присвойте переменной m
номер K-го
положительного элемента этой
последовательности. Если в последовательности
положительных элементов меньше K,
то переменной m
присвойте значение 0. Составьте блок-схему
алгоритма решения поставленной задачи.

Решение.
Смотри блок-схему алгоритма (задача
25).

Подсчет
количества положительных элементов
массива организуем с помощью цикла с
постусловием. Если положительных
элементов нет или их меньше, чем K,
выход из
цикла осуществим при i>n,
m
присвоим значение 0. При l
= K,
где l
– число положительных элементов, также
реализуем выход из цикла. При этом i
получит уже следующее значение. Значит,
номер K-го
положительного элемента на единицу
меньше i.

Задача 26.
Сдвиг в
массиве.
Переставьте вещественные элементы
массива A(1:n)
таким образом, чтобы они шли в следующем
порядке: А(n),
А(1), А(2), … , A(n-2),
A(n-1),
т.е. в массиве произведите сдвиг элементов
на одну позицию вправо. Составьте
блок-схему алгоритма решения поставленной
задачи.

Решение.
Смотри блок-схему алгоритма (задача
26).

Б
лок-схема
алгоритма (задача
25):
Блок-схема
алгоритма (задача
26):

Задача 27.
Максимальные
элементы массива. Дана последовательность
чисел a₁,
a₂,
… , a_n.
Найдите количество максимальных
элемен­тов последовательности и их
номера. Составьте блок-схему решения
поставленной задачи.

Решение.
Смотри блок-схемы 1-2 алгоритма (задача
27).

В
блок-схеме1 алгоритма (задача 27) первый
цикл организуем для определения
максимального элемента, значение
которого присваивается переменной b.
Начальное значение b
положим равным a₁.
Второй
цикл считает K
– количество одинаковых максимальных
элементов. Переменная M(K)
принимает значение индекса встретившегося
максимального элемента. M(K)
– числовая последовательность, членами
которой являются эти индексы.

Б

лок-схема1
алгоритма (задача
27):
Блок-схема2
алгоритма (задача
27):

Блок-схема2
алгоритма (задача 27) предполагает в
одном цикле на i-ом
шаге определение максимального элемента
из i
рассмотренных, подсчет количества
таких элементов и фиксирование их
номеров. Если на (i+1)-ом
шаге встречается больший элемент, то
операторы b:=a_i,
K:=1,
m_K:=i
зададут новые начальные значения
переменных b,
K,
m_K,
и все вычисления будут проведены
относительно нового большего элемента.

Задача 28.
Дружественные числа.
Дружественными
числами называются два натуральных
числа, таких, что каждое из них равно
сумме всех натуральных делителей
другого, исключая само это другое число.
Числа 220 и 284 являются дружественными
числами, так как сумма делителей числа
220 – это 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 =
284, а сумма делителей числа 284 – это 1 +
2 + 4 + 71 + 142 = 220. Составьте блок-схему
алгоритма нахождения дружественных
чисел на отрезке [2;n].

Решение.
Смотри блок-схему алгоритма (задача
28).

Блок-схема
алгоритма (задача
28):

С
уммы
делителей чисел от 2 до n
организуем в виде массива Делитель(2:n),
где Делитель(k)
– текущая сумма делителей числа k.
Вычислим суммы делителей всех чисел
от 2 до n,
затем попарно сравним эти суммы, если
суммы делителей чисел k
и s,
принадлежащих [2;n],
равны, то числа k
и s
– дружественные, их необходимо вывести.

Н
екоторые
пары дружественных чисел:
220 и 284,
1184 и 1210, 2620 и 2924, 5020 и 5564, 6232 и 6368 и т.д.

Задача 29.
Группировка.
Дан массив A(1:n),
элементы которого отличны от нуля.
Расположите их в таком порядке, чтобы
первыми были все положительные элементы,
а затем – все отрицательные, причем
порядок следования как положительных,
так и отрицательных элементов должен
сохраняться. При решении задачи нельзя
заводить новую таблицу. Составьте
блок-схему алгоритма решения поставленной
задачи.

Решение.
Смотри блок-схемы 1-2 алгоритма (задача
29).

Для решения
поставленной задачи будем перебирать
элементы массива с первого по n-ый.
Если A(i)>0,
никаких изменений в массиве не производим,
увеличиваем i
на единицу и переходим к исследованию
следующего элемента. Если же A(i)<0,
поставим его на n-ое
место (в конец таблицы), предварительно
освободив это n-ое
место, произведя сдвиг элементов массива
от A(i+1)
до A(n)
на один номер влево. Количество
просмотренных элементов массива будем
запоминать в переменной k.

Д
етализируем
блок «сдвиг влево на одну позицию и
перестановку A(i)
на n-ое
место»: скопируем A(i)
в переменную C,
произведем сдвиг и A(n)
присвоим значение C.
Смотри блок-схему2 алгоритма (задача
29).

Теперь детализированный
блок можно подставить в блок-схему1
алгоритма (задача 29).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Здесь приведены примеры программ и алгоритмов, используемых в курсе Основы программирования для студентов 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:]; 

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

III. Решение типовых задач с использованием массивов
на языке Turbo Pascal.

Решение большинства реальных задач на ЭВМ требует
организации данных в виде массивов.

 Можно выделить некоторые типовые алгоритмы,
являющиеся базовыми для реализации более сложных алгоритмов обработки массивов,
используемые как составная часть алгоритмов обработки данных, организованных в
виде массивов.

Далее рассматриваются часто встречающиеся типовые
алгоритмы обработки массивов:

·     Все алгоритмы описаны в общем виде
применительно к массивам произвольных размеров. Для обозначения границ
изменения индексов используются типизированные константы..

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

·     Все алгоритмы составлены применительно к
одномерным массивам.

РЕКОМЕНДАЦИИ:

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

·     Размеры массивов для конкретной задачи
обозначаются при помощи констант. Эти константы используются далее во всей
программе для обозначения границ изменения индексов. Это делает программу
независимой от данных конкретной задачи и позволяет использовать ее без
изменения для обработки массивов различных размеров.

Этот прием рекомендуется
использовать во всех случаях, даже когда размеры массивов менять не предполагается.

Во-первых, этим облегчается внесение в программу любых
изменений, связанных с границами индексов, если это все же понадобится.

Во-вторых, отладку программы целесообразно проводить на
меньших объемах данных, что легко реализуется, если следовать предлагаемому способу. 

·     Ввод массивов. Ввод нескольких массивов одного размера можно осуществлять
в одном цикле (For I:=1 to N do Readln
(A[I], B[I]). Однако такой способ
ввода часто является причиной ошибок. Более естественно вводить сначала все
элементы одного массива, затем другого. Для этого ввод каждого массива нужно
осуществлять в отдельном цикле.

Если вводимые массивы имеют
разные размеры, то второй способ является практически единственно возможным.

·     Вывод массивов. При выводе массивов необходимо обеспечить наглядность
и удобство восприятия полученных результатов. Вывод одномерного массива, как
правило, целесообразно осуществлять в строку, сопровождая поясняющим текстом:

…

WriteLn (‘ Вывод  массива А ‘);

For I:=1 to N do Write(A[I]:3);

WriteLn;

…

При вводе двух или нескольких
одномерных массивов одного размера часто удобно вывести их как расположенные
параллельно столбцы:

…

WriteLn (‘ Вывод  массивов А и В ‘);

For I:=1 to N do WriteLn(A[I]:5,
B[I]:5);

…

Вывод двух или более массивов
различных размеров, как правило, осуществляется в строку. Вывод нового массива
начинается с новой строки.

Если массив А ( или В ) не
умещается в одной строке, вывод будет автоматически продолжен в следующей.

·     
При использовании
переменных из массивов нередко повторяются их индексы. Например, при каждом
использовании выражения

A[I*K+1]=A[J*K+1]+R;

к переменной A[J*K+1] прибавляется значение R. Однако индекс [J*K+1] вычисляется при этом дважды – в левой и правой частях
равенства. Замена этого выражения фрагментом программы

I=J*K+1; A[I]=A[I]+R;

ведет к экономии памяти
(выражение стало короче) и сокращению времени счета ( индекс I=J*K+1 вычисляется один раз). Эта экономия будет еще существеннее,
если переменные A[J*K+1] используются в
программе более двух раз.

·     
Часто полезно заменять
индексированную переменную простой переменной. Например, вычисление
арифметического выражения

Y= A[J*K+1] * A[J*K+1]+X;  можно
выполнить в виде

Z= A[J*K+1]; Y=Z *Z+X;

Сокращение времени вычислений
в этом случае связано и с тем, что ЭВМ опознает простую переменную быстрее, чем
индексированную.

·     Не следует злоупотреблять обращениями к
подпрограммам, так как на них затрачивается дополнительное время (особенно,
когда обращения идут из циклов).

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

Требуется определить, сколько элементов
заданного массива P, содержащего n элементов, удовлетворяет заданному условию
(для определенности пусть условие имеет вид P_i>T, где T –
заданное число).

Указание к решению задачи. Для решения
задачи следует организовать цикл по i и для каждого значения i
проверять условие P_i>T. Если условие удовлетворяется, то к
счетчику числа элементов прибавляется 1, а если не удовлетворяется (т.е.
P_i£T), осуществляется переход к следующему элементу
массива.

Список используемых переменных.

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

Требуется найти сумму элементов массива Р, содержащего n
элементов, удовлетворяющих заданному условию, (для определенности пусть
условие имеет вид P_i>T, где T – заданное число).

Указание к решению задачи.  Для решения задачи следует организовать цикл по i и для каждого
значения i проверять условие P_i>T. Если условие
удовлетворяется, то к сумме элементов прибавляется элемент P_i, а
если не удовлетворяется (т.е. P_i£T), осуществляется
переход к следующему элементу массива.

Список используемых переменных.

3.3. Удаление элемента из массива.

Требуется
удалить К-й элемент из массива А размером N.

Указание к решению задачи. Удалить элемент, расположенный на К-м месте в массиве, можно, сдвинув
весь “хвост” массива, начиная с (К+1)-го элемента, на одну позицию
влево, т.е. выполняя операции a_i=a_i+1, i = K, K+1,
…, N-1.

Список используемых переменных.

3.4. Включение элемента в заданную позицию массива.

Требуется
включить К-й элемент в массив А размером N.

Указание к решению задачи. Перед включением элемента в К-ую позицию необходимо раздвинуть массив,
т.е. передвинуть “хвост” массива вправо на одну позицию, выполняя операцию
a_i+1= a_i , i
= N, N-1, …, K. Перемещение элементов массива нужно начинать с
конца. В противном случае весь “хвост” будет заполнен элементом a_k. Далее, К-му элементу присваивается заданное значение В. Размер массива
увеличивается на 1.

Замечание Для описания
этого массива нельзя использовать типизированные константы.

Список используемых переменных.

3.5. Включение элемента в  массив, упорядоченный по возрастанию, с
сохранением упорядоченности.

Указание к решению задачи. Сначала необходимо найти элемент, перед которым необходимо включать
заданное значение В. Для этого нужно проверять условие  B<A[I] для I = 1, 2, … . При выполнения условия текущее
значение индекса I определяет позицию нового элемента.
Перед включением элемента в К-ую позицию необходимо раздвинуть массив, т.е. передвинуть
“хвост” массива вправо на одну позицию, выполняя операцию a_i+1= a_i , i = N, N-1, …, K. Перемещение элементов массива нужно начинать с конца. В противном
случае весь “хвост” будет заполнен элементом a_k. Далее, К-му элементу присваивается заданное значение В. Размер массива
увеличивается на 1.

Замечание Для описания
этого массива нельзя использовать типизированные константы.

Список используемых переменных.

3.6. Поиск минимального (максимального ) элемента в массиве.

Требуется найти минимальный элемент в массиве и его
значение поместить в переменную Р, а индекс – в переменную К.

Указание к решению задачи. Считается, что минимальным элементом является первый элемент, т.е. P:=A[1];
K:=1. Далее  начинается цикл от I=2 до N. На каждом шаге цикла сравниваются значения I-го
элемента массива A и текущее значение переменной Р. Если
значение A[I] оказывается меньше текущего значения 
переменной Р, то выполняется присваивание P:=A[I]; K:=I. В
противном случае никаких присваиваний не производится.

Замечание. Если в массиве
несколько элементов имеют минимальное значение, то в К будет запоминаться
индекс первого из них. Если  для поиска максимального элемента будет
проверяться условие P >=A[I], то в К будет запоминаться
индекс последнего элемента.

 Список используемых переменных.

3.7. Объединение двух массивов в один с чередованием элементов исходных
массивов.

Требуется объединить два массива A и B, содержащие по n
элементов, в один массив C=(a₁, b₁, a₂, b₂,
…, a_n, b_n).

Указание к решению задачи. Можно заметить, что индекс элемента массива C
зависит от индекса пересылаемого в него элементов массива A и B,
а именно, c_2i-1=a_i, c_2i=b_i.
Таким образом, организовав цикл по i и  выполняя для каждого i
эти присваивания, мы решим задачу.

Список используемых переменных.

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

Требуется изменить порядок следования элементов массива C,
состоящего из n элементов, на обратный, используя одну вспомогательную
переменную. Результат получить в том же массиве C.

Указание к решению задачи. Сначала поменяем местами 1-й и n-й элементы, используя вспомогательную
переменную P. Для этого перешлем a₁ в P (P=a₁),
затем в a₁  перешлем a_n  (a_n=P).
Так же поступим с элементами a₂ и a_n-1 и
т.д., пока не дойдем до середины массива. Последними элементами, которые нужно
поменять местами, будут a_n-2 и a_n/2+1, если
n -четное, и a_[n/2] и a_[n/2]+2,
если n – нечетное, т.е. цикл по i в общем случае можно
организовать от i=1 до [n/2].

Список используемых переменных.

3.9. Формирование массива из элементов другого массива, удовлетворяющих
заданному условию.

Требуется из данного массива A, состоящего из n элементов,
выбрать элементы, удовлетворяющие заданному условию (например  условию A_i>T),
и сформировать из них массив B.

Указание к  решению задачи. Особенностью
решения этой задачи является то, что индексы элементов массивов A и B
не совпадают, так как не все элементы массива  A включаются в массив B.
Следовательно, для обозначения индекса элементов массива B предусмотреть
другую переменную , например j, значение которой будем изменять на 1
перед занесением в массив B нового значения. До входа в цикл нужно
положить j=0.

Список используемых переменных.

3.10. Поиск заданного элемента в массиве.

Требуется определить, есть ли в заданном массиве P, состоящем из n элементов, элемент, равный L (массив
может быть как числовым, так и символьным). Результат присвоить символьной
переменной.

Указание к решению задачи. Если элемент, равный L, найден, то, чтобы завершить цикл, I присваивается
значение, большее или равное размеру
массива ( I=N). Этот формальный прием позволяет
использовать только типовые структуры алгоритмов, имеющие один вход и один
выход.

Список используемых переменных.

3.11a.  Циклический сдвиг элементов массива.

Требуется переместить элементы массива А, состоящего из n элементов,
вправо (влево) на m позиций, при этом m элементов из конца массива перемещается в начало. Например,
результатом циклической перестановки  исходного массива А=(а₁, а₂,
а₃, а₄, а₅) вправо на две позиции будет А=(а₄,
а₅, а₁, а₂, а₃ ).

Указание к решению задачи. Рассмотрим
первый вариант алгоритма решения задачи: с использованием вспомогательного
массива.

В первом варианте
«хвост» массива (элементы а_n-m+1, …, a_n) пересылается во вспомогательный массив, все остальные элементы
перемещаются вправо на m позиций (a_i+m=a_i
, i=n-m, n-m-1, …, 1). Следует обратить внимание на
обратный порядок перемещения элементов (с конца). Прямой порядок (с начала)
привел бы к искажениям исходного массива.

Далее, в первые
элементы массива A (a₁, …, a_m) пересылаются
элементы вспомогательного массива, в котором временно хранится
“хвост” исходного массива.

Список используемых переменных.

3.11b. Циклический сдвиг элементов массива.

Требуется переместить элементы массива А, состоящего из n элементов,
вправо (влево) на m позиций, при этом m элементов из конца массива перемещается в начало. Например,
результатом циклической перестановки  исходного массива А=(а₁, а₂,
а₃, а₄, а₅) вправо на две позиции будет А=(а₄,
а₅, а₁, а₂, а₃ ).

Указание к решению задачи. Рассмотрим
второй вариант алгоритма решения задачи: с использованием одной
вспомогательной переменной. Во втором варианте во вспомогательную
переменную каждый раз пересылается последний элемент массива А, затем все элементы
сдвигаются вправо на одну позицию ( в обратном порядке) и на место первого
элемента помещается содержимое вспомогательной переменной. Эта процедура повторяется
m раз.

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

Список используемых переменных. 

3.12. Упорядочение массива.

Требуется расположить элементы массива в порядке возрастания
(убывания).

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

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

Список используемых переменных.

3.13. Проверка массива на упорядоченность.

Для заданного массива А размером n требуется 
определить, является ли массив упорядоченным. Результат присвоить символьной
переменной.

Указание к решению задачи. Для
определенности предположим, что проверяется упорядоченность массива по
возрастанию. Если массив упорядочен, то для каждой пары соседних элементов
должно выполняться условие a_i<a_i+1, i=1, …,
n-1. Если ни для какого i условие не было
нарушено, то массив упорядочен. Если для какого-либо i условие
нарушается, массив не является упорядоченным.

Список используемых переменных.

3.14. Поиск заданного элемента в упорядоченном массиве.

Требуется  в массиве М определить индекс С элемента,
равного заданному значению К. Массив М упорядочен по возрастанию.

Указание к решению задачи. Если в заданном
массиве поиск осуществляется многократно, то целесообразно сначала массив
упорядочить, чтобы затем быстро производить поиск. Предположим, что массив
упорядочен по возрастанию. Рассмотрим алгоритм так называемого бинарного
поиска. Идея алгоритма заключается в следующем. Заданное число К сравнивается
со средним элементом массива М ( имеющим, например, индекс где  А – нижняя граница, В – верхняя
граница индексов ( в начале А=1, B=N, где N – размерность массива). Если М(С)¹К, то далее, поиск продолжается в одной из
половин массива (исключая элемент М(С)) в зависимости от результата сравнения.
Для этого изменяется значение или А(А=С+1) или В (В=С-1). Заданное число К
сравнивается  со средним элементом в выбранной половине и т.д.

Пояснение к
программе. Часть массива, в которой ищется значение К, постоянно сужается. Поиск
заканчивается, когда в ней не остается ни одного элемента (выполняется условие
В<А). Если значение К найдено, то для обеспечения выхода
из цикла полагается  В=А-1.

Список используемых переменных.

3.15. Объединение
двух упорядоченных массивов одного размера в один, так же упорядоченный.

Требуется объединить два упорядоченных по возрастанию
(убыванию) массива А и В размером N
в один массив 2N также упорядоченный по возрастанию (убыванию).

Указание к решению задачи. Индексы массивов А и В будем менять независимо. 
Если выполняется условие a_i<b_j, то
в массив С начинаем пересылать элементы массива В (индекс j при этом не меняются) до тех пор, пока это условие не нарушается. Тогда
в массив С начинаем пересылать элементы массива В (индекс i при этом не меняется ) и т.д.. пока не закончится пересылка элементов
обоих массивов (будет выполняться условие i>n и j>n ). Если одно из этих условий выполнено, т.е. один из массивов
полностью исчерпан, то “хвост” другого массива пересылается элемент
за элементом без каких либо проверок.

Список используемых переменных.

3.16. Сравнение двух упорядоченных по возрастанию массивов.

Требуется определить количество совпадающих элементов двух
упорядоченных массивов А и В. Размеры массивов не обязательно одинаковы.

Указание к решению задачи. Сравнение
начинаем с первых элементов ( k=1, l=1 ), и если они
совпадают, то увеличиваем результат (число совпадающих элементов) на 1 и
переходим к следующим элементам (k=k+1, l=l+1). В
противном случае происходит движение ( изменение индекса) по тому массиву,
значение элементов которого меньше, индекс второго массива не меняется.
Алгоритм должен закончить работу, если исчерпан хотя бы один массив.

Пояснение к программе. Так как внешний цикл организован по L , то, чтобы
обеспечить формально выход из этого цикла при окончании просмотра элементов массива
А (при К>N) , полагается L=М.

Список используемых переменных.