Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Другие методич. материалы / Одномерные массивы

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


  • Информатика

Документы в архиве:

Название документа Mas_1.doc

Поделитесь материалом с коллегами:

25



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[IK+1]=A[JK+1]+R;

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

I=JK+1; A[I]=A[I]+R;

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

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

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

Z= A[JK+1]; Y=Z Z+X;

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

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


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

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

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

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

Исходные данные:

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.


hello_html_m50993034.png

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

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

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

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

Исходные данные:

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.



hello_html_4e61f4e6.png

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.


















hello_html_m6439344.gif

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.










hello_html_4d870017.png

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

Указание к решению задачи. Сначала необходимо найти элемент, перед которым необходимо включать заданное значение В. Для этого нужно проверять условие Bдля 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.






hello_html_2ca5582e.png

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]

begin

P:=A[I]; K:=I;

end;

WriteLn('Минимальный элемент :',P);

WriteLn('Индекс минимального элемента :', K)

end.




hello_html_7fcf36a1.png

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..2N] of integer;

I, T, S : integer;

begin ClrScr;

for i:=1 to N do

begin

C[2I-1]:=A[i]; C[2I]:=B[I]

end;

for i:=1 to 2N do WriteLn('C[',I,']=',C[I])

end.



hello_html_mb9b1d12.gif

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.



hello_html_6e617618.png

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.



hello_html_2f8ee980.png

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.



hello_html_4aed73bf.png

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.

hello_html_68ccc14a.png

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.

hello_html_m460cafb2.png

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]

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.

hello_html_m57f919e.png

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

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

Указание к решению задачи. Для определенности предположим, что проверяется упорядоченность массива по возрастанию. Если массив упорядочен, то для каждой пары соседних элементов должно выполняться условие aii+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.



hello_html_727af563.png

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

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

Указание к решению задачи. Если в заданном массиве поиск осуществляется многократно, то целесообразно сначала массив упорядочить, чтобы затем быстро производить поиск. Предположим, что массив упорядочен по возрастанию. Рассмотрим алгоритм так называемого бинарного поиска. Идея алгоритма заключается в следующем. Заданное число К сравнивается со средним элементом массива М ( имеющим, например, индекс hello_html_6b06a7cc.gifгде А - нижняя граница, В - верхняя граница индексов ( в начале А=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.

hello_html_m4fa53789.png

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

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

Указание к решению задачи. Индексы массивов А и В будем менять независимо. Если выполняется условие aij, то в массив С начинаем пересылать элементы массива В (индекс 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..2N] 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]

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 2N do Write(C[I]:4)

end.

hello_html_m65c9b28e.png

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

begin

If A[K]>B[L] then L:=L+1

else if A[K]

else begin

R:=R+1; L:=L+1; K:=K+1

end;

if K>N then L:=M;

end;

WriteLn('R=',R)

END.

hello_html_24e81fa2.png



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

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

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

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

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

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

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

Автор
Дата добавления 14.05.2015
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров1167
Номер материала 280010
Получить свидетельство о публикации

Похожие материалы

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