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

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), осуществляется переход к следующему элементу массива.

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

Исходные данные:	N - размер массива;
	P -  массив размером N;
	T - заданное значение, с которым сравниваются элементы массива;
Результат:	K - число элементов массива P, удовлетворяющих заданному условию;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_1; uses Crt; const      N=10;      P : array [1..N] of  integer = (21,33,25,68,72,39,5,12,34,56); Var i, k : integer;          T : integer; begin ClrScr;       Write ('Введите число :');ReadLn(T);       k:=0;       for i:=1 to N do            if P[i]<=T then k:=k+1;       WriteLn('Количество элементов массива,',               ' удовлетворяющих заданному               условию равно ', k); end.

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

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

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

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

Исходные данные:	N - размер массива;
	P -  массив размером N;
	T - заданное значение, с которым сравниваются элементы массива;
Результат:	S- число элементов массива P, удовлетворяющих заданному условию;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.
На языке TURBO PASCAL		Блок - схема.
Program Mas_1_2; uses Crt; const      N=10;      P : array [1..N] of  integer = (21,33,25,68,72,39,5,12,34,56); Var I : integer;       T, S : integer; begin ClrScr;       Write ('Введите число :');ReadLn(T);       S:=0;       for I:=1 to N do            if  P[i]<=T then S:=S+P[i];       WriteLn ('Сумма элементов массива,', 'удовлетворяющих заданному условию равна ',S); end.

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

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

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

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

Исходные данные:	N - размер массива;
	A -  массив размером N;
	K - индекс элемента, который нужно удалить;
Результат:	А - массив размером N-1;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.

На языке TURBO PASCAL	Блок - схема.
PROGRAM Mas_1_3; USES Crt; CONST    N=10; VAR    A : array[1..N] of integer;    I, K, R : integer; BEGIN ClrScr; Write(' Введите элементы массива чеpез пpобел: '); For I:=1 to N do Read (A[I]); Write(' Введите К:');ReadLn(K); R:=N-1; For I:=K to R do A[I]:=A[I+1]; For i:=1 to R do Write(A[I]:4) END.

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

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

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

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

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

Исходные данные:	N - размер массива;
	A -  массив размером N;
	K - индекс элемента, который нужно вставить; В - значение вставляемого элемента;
Результат:	А - массив размером N+1;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.

На языке TURBO PASCAL	Блок - схема.
PROGRAM Mas_1_4; USES Crt; CONST    N=10; VAR    A : array[1..N+1] of integer;    I, K, R, B : integer; BEGIN ClrScr; Write('Введите элементы массива чеpез пpобел: '); For I:=1 to N do Read(A[I]); Write('Введите К:');ReadLn(K); Write('Введите значение элемента:');ReadLn(B); For i:=N downto K do A[I+1]:=A[I]; A[K]:=B; R:=N+1; For i:=1 to R do Write(A[I]:4) END.

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

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

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

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

Исходные данные:	N - размер массива;
	A -  упорядоченный массив размером N;
	В - значение вставляемого элемента;
Результат:	А - упорядоченный массив размером N+1;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.

На языке TURBO PASCAL	Блок - схема.
PROGRAM Mas_1_5; USES Crt; CONST    N=10; VAR    A : array [1..N+1] of integer;    I, K, R, B : integer; BEGIN ClrScr; Write('Введите элементы массива чеpез пpобел: '); For I:=1 to N do Read(A[I]); Write('Введите значение элемента:'); ReadLn(B); For I:=1 to N do IF B<=A[I] then begin K:=I; I:=N end; For I:=N downto K do A[I+1]:=A[I]; A[K]:=B; R:=N+1; For i:=1 to R do Write(A[I]:4) END.

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

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

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

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

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

Исходные данные:	N - размер массива;
	A - массив размером N;
Результат:	Р - переменная для хранения  значения минимального элемента ; K - индекс минимального элемента
Вспомогательные переменные:	I - индекс-управляющая переменная  цикла .

На языке TURBO PASCAL	Блок - схема.
Program Mas_1_6; uses Crt; const N=10; A : array [1..N] of integer = (21,33,25,68,72,39,5,12,34,56); Var i,  K, P : integer; begin ClrScr; for i:=1 to N do Write(A[I]:4); WriteLn; P:=A[1]; K:=1; for I:=1 to N do if A[I]<P then begin P:=A[I]; K:=I; end; WriteLn('Минимальный элемент  :',P); WriteLn('Индекс минимального элемента :', K) end.

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 эти присваивания, мы решим задачу.

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

Исходные данные:	N - размер массива;
	A, B -  массивы размером N;
Результат:	С - массив размером 2N ;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_7; uses Crt; const      N=10;      A : array [1..N] of integer = (21,33,25,68,72,39,5,12,34,56);      B : array [1..N] of integer = (45,67,23,32,15,89,12,75,567,345); Var     C : array [1..2*N] of integer;      I, T, S : integer; begin ClrScr;       for i:=1 to N do         begin              C[2*I-1]:=A[i]; C[2*I]:=B[I]         end;       for i:=1 to 2*N do WriteLn('C[',I,']=',C[I]) end.

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].

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

Исходные данные:	N - размер массива;
	C -  массив размером N;
Результат:	C - инвертированный исходный массив;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла; M=[N/2] -  вычисляется до входа в цикл для уменьшения объема вычислений.

На языке TURBO PASCAL	Блок - схема.
Program Mas_1_8; uses Crt; const      N=10;      C: array [1..N] of integer = (21,33,25,68,72,39,5,12,34,56); Var     I, M, P : integer; begin ClrScr;       M:=Trunc(N/2);       for i:=1 to M do       begin           P:=C[i]; C[i]:=C[N-I+1]; C[N-I+1]:=P       end;       for i:=1 to N do           WriteLn('C[',i,']=',C[i]); end.

 

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

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

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

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

Исходные данные:	N - размер массива;
	A -  массив размером N;
	T - заданное значение для проверки условия включения элемента массива A в массив B;
Результат:	B - массив размером не больше N; J - число элементов массива B;
Вспомогательные переменные:	I - индекс элементов массива; A - управляющая переменная цикла.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_9; uses Crt; const      N=10;      A : array [1..N] of integer = (21,33,25,68,72,39,5,12,34,56); Var     B : array [1..N] of integer;     i, j, T : integer; begin ClrScr;       Write ('Введите число :');ReadLn(T);       j:=0;       for i:=1 to N do            if A[i]>=T then                       begin                            j:=j+1; B[j]:=A[i]                       end;       for i:=1 to J do WriteLn ('B[',i,']=',B[i]); end.

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

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

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

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

Исходные данные:	N - размер массива;
	P -  массив размером N;
	L - значение, которое ищется в массиве;
Результат:	R - символьная переменная;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_10; uses Crt; const      N=10;      P : array[1..N] of integer = (21,33,25,68,72,39,5,12,34,56); Var    i, L : integer;    R : String [50]; begin ClrScr;       Write ('Введите число :');ReadLn(L);       R:='Элемента, равного L нет';       for i:=1 to N do         if P[i]=L then                      begin                      R:='Элемент, равный L есть';                      i:=N;                      end;       WriteLn(R) end.

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) пересылаются элементы вспомогательного массива, в котором временно хранится "хвост" исходного массива.

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

Исходные данные:	N - размер массива;
	A - массив размером N;
	M - число позиций сдвига;
Результат:	A - массив, циклически сдвинутый на М позиций вправо;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла; P - вспомогательный массив размером N.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_11a; uses Crt; const N=10; A : array[1..N] of integer = (21,33,25,68,72,39,5,12,34,56); Var P : array[1..N] of integer; i, M : integer; begin ClrScr; Write ('Введите число позиций сдвига:'); ReadLn(M); for i:=1 to N do begin GotoXY(1,I); WriteLn('A[',I,']=',A[I]) end; for i:=1 to M do P[i]:=A[N-M+I]; for i:=N-M downto 1 do A[I+M]:=A[I]; for i:=1 to M do A[I]:=P[I]; for i:=1 to N do begin GotoXY(20,I); WriteLn('A[',I,']=',A[I]) end end.

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

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

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

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

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

Исходные данные:	N - размер массива;
	A - массив размером N;
	M - число позиций сдвига;
Результат:	A - массив, циклически сдвинутый на М позиций вправо;
Вспомогательные переменные:	I - индекс - управляющая переменная цикла; P - переменная, для временного хранения элемента массива А; J - управляющая переменная внутреннего цикла.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_11b; uses Crt; const N=10; A : array [1..N] of integer = (21,33,25,68,72,39,5,12,34,56); Var  i, j, M, P: integer; begin ClrScr; Write ('Введите число позиций сдвига:'); ReadLn(M); for i:=1 to N do begin GotoXY(1,I+2); WriteLn('A[',I,']=',A[I]) end; for i:=1 to M do begin P:=A[N]; for J:=N downto 1 do A[J]:=A[J-1]; A[1]:=P end; for i:=1 to N do begin GotoXY(20,I+2); WriteLn('A[',I,']=',A[I]); end end.

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

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

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

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

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

Исходные данные:	N - размер массива;
	A - массив размером N;
Результат:	A - массив размером N, упорядоченный по возрастанию;
Вспомогательные переменные:	I - индекс элемента упорядоченного массива - управляющая переменная внешнего цикла ; J - индекс элемента части массива, в которой ищется минимальный элемент - управляющая переменная внутреннего цикла; P - переменная для хранения промежуточного значения минимального элемента, K - индекс минимального элемента.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_12; uses Crt; const      N=10;      A : array[1..N] of integer = (21,33,25,68,72,39,5,12,34,56); Var    i, j, K, P : integer; begin ClrScr;       for I:=1 to N-1 do       begin           P:=A[I]; K:=I;           for J:=I+1 to N do               if A[J]<P then                            begin                                 P:=A[J]; K:=J;                            end;           A[K]:=A[I]; A[I]:=P       end;       for I:=1 to N do                      begin                       GotoXY(20,I+2); WriteLn('A[',I,']=',A[I])                      end end.

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

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

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

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

Исходные данные:	N - размер массива;
	A -  массив размером N;
Результат:	T - имеет значение "Массив упорядочен" или "Массив не упорядочен";
Вспомогательные переменные:	I - индекс - управляющая переменная цикла.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_13; uses Crt; const      N=10; Var    A : array[1..N] of integer;    I, L : integer;    T : String[50]; begin ClrScr;       for I:=1 to N do       begin            Write('Введите A[',I,']=');ReadLn(A[I])       end;       T:='Массив упорядочен по убыванию ';       for i:=1 to N-1 do            if A[I]>A[I+1] then                            begin   T:='Массив не упорядочен по убыванию ';                                 I:=N-1                            end;       WriteLn(T) end.

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

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

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

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

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

Исходные данные:	N - размер массива;
	M -  упорядоченный по возрастанию  массив размером N;
	К - заданное число;
Результат:	L - если элемент со значением К не найден, то L=0, если элемент найден, то L=1;
Вспомогательные переменные:	С - индекс - управляющая переменная цикла.

На языке TURBO PASCAL

Блок - схема.

Program Mas_1_14; uses Crt; const N=10; Var   M : array[1..N] of integer; I, K, L, A, B, C : integer; begin ClrScr; WriteLn(' Введите элементы массива :'); for I:=1 to N do ReadLn(M[i]); Write('Введите заданный элемент :');  ReadLn(K); A:=1; B:=N; L:=0; While B>=A do begin C:=Trunc((A+B)/2); if M[C]=K then begin L:=1; B:=A-1  end else if M[C]>K then B:=C-1 else A:=C+1; end; if L=0 then WriteLn(' Такого элемента нет') else WriteLn(' Номер этого элемента: ',C) end.

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

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

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

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

Исходные данные:	N - размер исходных массива;
	A, B -  упорядоченные массивы размером N;
	T - заданное значение, с которым сравниваются элементы массива.
Результат:	С - упорядоченный массив размером 2N;
Вспомогательные переменные:	I, J - индексы массивов А и В;  К - индекс массива С.

На языке TURBO PASCAL

Блок - схема.

PROGRAM Mas_1_15; USES Crt; Label 1,2,3,4; CONST   N=10; A : array[1..N] of integer = (21,33,35,68,72,80,83,92,134,156); B : array[1..N] of integer = (45,67,73,82,85,89,92,175,267,345); VAR I, J, K : integer; C : array[1..2*N] of integer; BEGIN ClrScr; J:=1; I:=1; K:=0; 1: If I>N then goto 2 else If J>N then goto 3 else begin  K:=K+1; if A[I]<B[J] then begin C[K]:=A[I]; I:=I+1 end else begin C[K]:=B[J];J:=J+1 end; end; goto 1; 3: While I<=N do begin K:=K+1; C[K]:=A[I]; I:=I+1 end; goto 4; 2: While J<=N do begin K:=K+1; C[K]:=B[J]; J:=J+1 end; 4: For i:=1 to 2*N do Write(C[I]:4) end.

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

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

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

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

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

Исходные данные:	N, М- размеры заданных массивов;
	А, В - упорядоченные массивы размером N и М;
Результат:	R - число совпадающих элементов массива A и B;
Вспомогательные переменные:	K, L - индексы массивов А и В.

На языке TURBO PASCAL

Блок - схема.

PROGRAM Mas_1_16; USES Crt; CONST N=10; M=15; VAR A : array[1..N] of integer; B : array[1..M] of integer; R, K, L : integer; BEGIN ClrScr; K:=1; R:=0; L:=1; WriteLn (' Введите массив А :'); For K:=1 to N do Read ( A[K]); WriteLn; WriteLn (' Введите массив B :'); For L:=1 to M do Read ( B[L]); While L<M do begin           If A[K]>B[L]  then L:=L+1           else if A[K]<B[L] then K:=K+1                  else begin R:=R+1; L:=L+1; K:=K+1 end;           if K>N then L:=M;      end;     WriteLn('R=',R) END.

Краткое описание документа:

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

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

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

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

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

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