Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Var

A: array [1..10] of integer;

I: byte; {переменная I вводится как индекс массива}

Begin

For i:=1 to 10 do

Readln (a[i]); { ввод i- го элемента производится с клавиатуры }

Рассмотрим теперь случай, когда массив Паскаля заполняется автоматически случайными числами, для этого будем использовать функцию random (N).

Пример фрагмента программы заполнения массива Паскаля случайными числами

Var

A: array [1..10] of integer;

I: byte; {переменная I вводится как индекс массива}

Begin

For i:=1 to 10 do

A [ i ]:= random (10); { i -му элементу массива присваивается «случайное» целое число в диапазоне от 0 до 10}

Вывод массива Паскаля

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

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

Var

A: array [1..10] of integer;

I: byte; {переменная I вводится как индекс массива}

Begin

For i:=1 to 10 do

Write (a [ i ],’ ‘); {вывод массива осуществляется в строку, после каждого элемента печатается пробел}

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

Пример программы вывода массива Паскаля в столбик

Var

A: array [1..10] of integer;

I: byte; {переменная I вводится как индекс массива}

Begin

For i:=1 to 10 do

Writeln (‘a[‘, i,’]=’, a[i]); { вывод элементов массива в столбик }

На экране мы увидим, к примеру, следующие значения:

a [1]=2

a [2]=4

a [3]=1 и т.д.

Сортировка одномерного массива.

Сортировка выбором основана на определении наибольшего (наименьшего) элемента, который переносится в начало или конец массива в зависимости от вида сортировки (по возрастанию или по убыванию). Затем эта процедура применяется ко всем оставшимся элементам, кроме уже перемещенных элементов, всего (N - 1) раз. Приведем пример операторов для сортировки элементов массива “Х” по возрастанию:

for j: = 1 to N-1 do begin { цикл по числу "проходов" }

k:= N-j+1; { k - номер последнего элемента в проверяемой части массива }

m:= k; { m - номер элемента с наибольшим значением }

for i:= 1 to N-j do {цикл сравнения элементов в оставшейся части массива}

if x[i] > x[m] then m: = i; { запоминаем значение "m" }

b:= x[k]; x[k]:= x[m]; x[m]:= b { переставляем элементы }

End;

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

Сортировка обменом (метод пузырька) основана на последовательном сравнении пары соседних элементов x[i] и x[i+1]. Если пара расположена не в требуемом порядке, то элементы переставляются. Например, при сортировке по возрастанию после первого "прохода" массива от первого до последнего элемента на последнем месте окажется наибольший элемент массива. Далее сортируется оставшаяся часть массива. С каждым очередным "проходом" наибольший элемент массива в оставшейся части массива будет занимать последнее место в проверяемой части массива. Наибольшее число проходов j равно "N - 1", причем число проверок при очередном проходе уменьшается на единицу:

for j:= 1 to N-1 do { цикл по числу "проходов" }

for i:= 1 to N-j do { цикл сравнения элементов в оставшейся части массива }

if x[i] > x[i+1] then begin { запоминаем значение x[i] и }

b:=x[i]; x[i]:=x[i+1]; x[i+1]:=b end; { переставляем элементы }

Поскольку при сортировке сравниваются каждые два соседних элемента массива, то для упорядочения данных общее число "проходов" может быть меньше, чем "N - 1". Избежать лишних проходов можно используя оператор цикла с условием:

j:= 0;

repeat j:= j+1; pr:= 0; { pr - признак необходимости "прохода" }

for i:= 1 to N-j do {цикл сравнения элементов в проверяемой части массива}

if x[i] > x[i+1] then begin pr:= 1; { изменяем значение признака }

b:=x[i]; x[i]:=x[i+1]; x[i+1]:=b end; { переставляем элементы }

until pr = 0;

Если при проходе проверяемой части массива не было перестановок, то pr=0 и процесс заканчивается. Оптимальным с математической точки зрения считается алгоритм с наименьшим числом перестановок. Однако при программировании необходимо учитывать также, что время выполнения логических операций, как правило, значительно превышает время выполнения арифметических операций. Таким образом, время выполнения программы определяется не только числом перестановок, но существенно зависит от количества выполнений логических операций.

Сортировка вставками основана на внедрении в отсортированную часть массива элемента следующего за этой частью, если он удовлетворяет условию сортировки. На первом шаге сортировки второй элемент сравнивается с первым, на втором шаге третий элемент сравнивается с двумя первыми и т. д. Среди уже отсортированных i - 1 элементов массива вставляют i - й элемент без нарушения порядка, т. е. при вставке i - го элемента на j - е место (j < i) элементы с индексами >j и <i увеличивают свой номер на единицу. Приведем пример операторов для сортировки данных по возрастанию:

for i:= 2 to N do begin { цикл по числу шагов }

b:=x[i]; {значение элемента, следующего за отсортированной частью массива}

j:= 1;

while b > x[j] do j:= j+1; { определение номера j для вставки элемента}

for k:=i downto j+1 do x[k]:=x[k-1]; { увеличение индексов элементов }

x[j]:= b { вставка значения b на место j - го элемента }

End;

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

Cамым простым методом сортировки является метод "пузырька". Чтобы понять, как он работает, представим, что массив (таблица) расположен вертикально.
Элементы с большим значением всплывают вверх наподобие больших пузырьков.
При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом: * если встречается элемент с меньшим значением, то они меняются местами; * при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним. В результате наибольший элемент оказывается в самом верху массива. Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д. При втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они уже больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.

Программа:

begin
for j:=1 to N-1 do
for i:=1 to N-j do
if M[i] > M[i+1] then
begin
t:=M[i];
M[i]:=M[i+1];
M[i+1]:=t;
end;end;

19)Двумерные массивы (описание, ввод –вывод, доступ к элементам массива)