Задания для самостоятельного выполнения лабораторной работы 13.

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

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

3 Напишите программу, которая вводит с клавиатуры 15 реальных чисел, организовывает их хранение в массиве и определяет индексы (номера) элементов массива, значение которых равно значению первого элемента массива. Если такого элемента нет, вывести соответствующее сообще­ние на экран.

4 Напишите программу, которая вводит с клавиатуры 10 реальных чисел, и организовывает их хранение в массиве. После этого массив пересор­тировывается по закону: первый элемент меняется с последним, второй с предпоследним и т.д.

5 Напишите программу, которая вводит с клавиатуры 10 целых чисел, ор­ганизовывает их хранение в массиве и определяет количество чётных и количество нечётных элементов в массиве.

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

7 Дан массив, состоящий из 10 символов. Определить и вывести на экран индексы символов равных первому символу.

8 Дан массив, состоящий из 10 символов. Организовать массив целых чисел и заполнить его номерами символов исходного массива. Вывести содержимое массива на экран.

Лабораторная работа 14.

Упорядочивание (сортировка) массива

В большинстве случаев, массивы применяются для хранения большого количества однотипной информации, создания и организации баз и банков данных и т.д. Во многих случаях номер (индекс) элемента в массиве не играет большой роли. Важно именно его значение, т.е. сама информация. Базы и банки данных, в свою очередь, необходимы не только для того, чтобы "складывать" в них информацию, но и для того, чтобы в любой мо­мент была возможность удобного и быстрого доступа к ней. В обычном "неотсортированном" массиве информацию найти можно, но только уже из­вестным Вам способом последовательного перебора-просмотра всех его элементов, до тех пор, пока нужный элемент не будет обнаружен. Этот самый простой метод обладает только одним, но очень существенным недос­татком - на поиск одного элемента уходит много времени. Все остальные методы поиска информации намного эффективнее, быстрее, но применяются только в упорядоченных, отсортированных массивах. Поэтому часто возни­кает задача об упорядочивании массива.

Рассмотрим простой случай такой задачи: дан числовой массив xl, х2, ... хn, элементы которого попарно различны; требуется переставить элементы массива так, чтобы после перестановки они были упорядочены в порядке возрастания: xl < х2 < ... < хn.

Существует несколько алгоритмов решения этой задачи. Мы рассмот­рим два наиболее популярных.

Алгоритм сортировки выбором

Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе - наименьший из всех остальных, третий - наи­меньший из оставшихся и т.д.

Для этого необходимо выполнить следующую последовательность дейс­твий:

Определить минимальный элемент массива;

Поменять его местами с первым элементом;

Определить минимальный элемент среди оставшихся;

Поменять его местами со вторым элементом и т.д.;

Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.

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

Первая - поиск минимального элемента. Предлагаемый фрагмент прог­раммы напомнит Вам, как это делается.

min:=m[l]; {допустим, что 1-й элемент - минимален}

t:=l;  {и его номер =1}

FOR i:=l ТО 30 DO if m[i]<m[t] then t:=j; {условие для определение минимума}

buf:=m[t]; {замена}

m[t]:=m[i];

m[i]:=buf;

END;

Описанный метод сортировки массивов можно применять как для сор­тировки массивов по возрастанию, так и для сортировки массивов по убы­ванию. Для этого просто необходимо определять не минимальный элемент массива, а максимальный. В тексте программы это выражается заменой в некоторых местах знака "<" на знак ">".

Алгоритм пузырьковой сортировки

Алгоритм так называемой "пузырьковой" сортировки более оригинален и в большинстве случаев более эффективен. При использовании этого ал­горитма весь массив просматривается несколько раз подряд. При каждом таком просмотре сравниваются последовательно только соседние элементы массива: сначала первый со вторым, потом второй с третьим, и в конце предпоследний с последним. Если при сравнении окажется, что предыдущий элемент больше следующего, они меняются местами описанным выше спосо­бом. Так в результате одного последовательного просмотра элементы, значение которых больше, "всплывают" образно говоря на поверхность, т.е. ближе к концу массива. Если провести такой последовательный прос­мотр массива несколько раз, то "тяжёлые" элементы окончательно "всплы­вут" и массив окажется отсортированным. Остаётся нерешённым ещё один вопрос. Сколько раз необходимо выполнять такой просмотр? Ведь может оказаться, что и одного просмотра будет достаточно. Столько, сколько нужно для полной сортировки, т.е. пока при просмотре элементы не будут меняться местами. Для этого удобно организовать логическую переменную ind, и присваивать ей значение ложь в случае, если замена происходила хотя бы один раз. Если значением этой переменной останется истина, то просмотры необходимо прекратить.

Предлагаемый Вам ниже фрагмент программы реализован на основе ме­тода пузырьковой сортировки. Он выполняет полную сортировку массива состоящего из 40 элементов.

REPEAT

ind:=true; {предположим, что массив уже отсортирован}

FOR i:=l ТО 39 DO {цикл для организации просмотра}

if m[i]>m[i+l] then {сравнение двух соседних элементов}

begin

buf:=m[i]; {меняем соседние элементы местами}

m[i]:=m[i+l];

m[i+l]:=buf;

ind:=false; {как оказалось, массив неотсортирован}

end;

UNTIL ind; {выполняем просмотры пока ind=false}

Контрольные вопросы.

1 Опишите идею сортировки массива методом выбора и последовательность действий для его реализации на языке Turbo Pascal.

2 Опишите идею сортировки массива "пузырьковым" методом и последова­тельность действий для его реализации на языке Turbo Pascal.