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 элементов, удовлетворяет заданному условию
(для определенности пусть условие имеет вид Pi>T, где T -
заданное число).
Указание к решению задачи. Для решения
задачи следует организовать цикл по i и для каждого значения i
проверять условие Pi>T. Если условие удовлетворяется, то к
счетчику числа элементов прибавляется 1, а если не удовлетворяется (т.е.
Pi£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
элементов, удовлетворяющих заданному условию, (для определенности пусть
условие имеет вид Pi>T, где T - заданное число).
Указание к решению задачи. Для решения задачи следует организовать цикл по i и для каждого
значения i проверять условие Pi>T. Если условие
удовлетворяется, то к сумме элементов прибавляется элемент Pi, а
если не удовлетворяется (т.е. Pi£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)-го элемента, на одну позицию
влево, т.е. выполняя операции ai=ai+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.
Указание к решению задачи. Перед включением элемента в К-ую позицию необходимо раздвинуть массив,
т.е. передвинуть "хвост" массива вправо на одну позицию, выполняя операцию
ai+1= ai , i
= N, N-1, ..., K. Перемещение элементов массива нужно начинать с
конца. В противном случае весь "хвост" будет заполнен элементом ak. Далее, К-му элементу присваивается заданное значение В. Размер массива
увеличивается на 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 определяет позицию нового элемента.
Перед включением элемента в К-ую позицию необходимо раздвинуть массив, т.е. передвинуть
"хвост" массива вправо на одну позицию, выполняя операцию ai+1= ai , i = N, N-1, ..., K. Перемещение элементов массива нужно начинать с конца. В противном
случае весь "хвост" будет заполнен элементом ak. Далее, К-му элементу присваивается заданное значение В. Размер массива
увеличивается на 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=(a1, b1, a2, b2,
..., an, bn).
Указание к решению задачи. Можно заметить, что индекс элемента массива C
зависит от индекса пересылаемого в него элементов массива A и B,
а именно, c2i-1=ai, c2i=bi.
Таким образом, организовав цикл по 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. Для этого перешлем a1 в P (P=a1),
затем в a1 перешлем an (an=P).
Так же поступим с элементами a2 и an-1 и
т.д., пока не дойдем до середины массива. Последними элементами, которые нужно
поменять местами, будут an-2 и an/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 элементов,
выбрать элементы, удовлетворяющие заданному условию (например условию Ai>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 элементов из конца массива перемещается в начало. Например,
результатом циклической перестановки исходного массива А=(а1, а2,
а3, а4, а5) вправо на две позиции будет А=(а4,
а5, а1, а2, а3 ).
Указание к решению задачи. Рассмотрим
первый вариант алгоритма решения задачи: с использованием вспомогательного
массива.
В первом варианте
«хвост» массива (элементы аn-m+1, ..., an) пересылается во вспомогательный массив, все остальные элементы
перемещаются вправо на m позиций (ai+m=ai
, i=n-m, n-m-1, ..., 1). Следует обратить внимание на
обратный порядок перемещения элементов (с конца). Прямой порядок (с начала)
привел бы к искажениям исходного массива.
Далее, в первые
элементы массива A (a1, ..., am) пересылаются
элементы вспомогательного массива, в котором временно хранится
"хвост" исходного массива.
Список используемых переменных.
Исходные данные:
|
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 элементов из конца массива перемещается в начало. Например,
результатом циклической перестановки исходного массива А=(а1, а2,
а3, а4, а5) вправо на две позиции будет А=(а4,
а5, а1, а2, а3 ).
Указание к решению задачи. Рассмотрим
второй вариант алгоритма решения задачи: с использованием одной
вспомогательной переменной. Во втором варианте во вспомогательную
переменную каждый раз пересылается последний элемент массива А, затем все элементы
сдвигаются вправо на одну позицию ( в обратном порядке) и на место первого
элемента помещается содержимое вспомогательной переменной. Эта процедура повторяется
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 требуется
определить, является ли массив упорядоченным. Результат присвоить символьной
переменной.
Указание к решению задачи. Для
определенности предположим, что проверяется упорядоченность массива по
возрастанию. Если массив упорядочен, то для каждой пары соседних элементов
должно выполняться условие ai<ai+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 также упорядоченный по возрастанию (убыванию).
Указание к решению задачи. Индексы массивов А и В будем менять независимо.
Если выполняется условие ai<bj, то
в массив С начинаем пересылать элементы массива В (индекс 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.
|
|
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.