Общие пояснения

1. Описание и использование двумерных массивов. Как и одномерные, двумерные массивы представляют совокупность однотипных переменных, имеющих одинаковое имя и размещенных в памяти ЭВМ подряд. Однако, для обращения к отдельному элементу (компоненту) массива, требуется указывать уже два индекса. Для наглядности, двумерные массивы изображают на бумаге в форме прямоугольной таблицы, поэтому часто такие массивы с числовыми значениями элементов называют матрицами.

B Turbo Pascal компоненты массива могут быть любого (в том числе – составного) типа, индексы могут быть любого порядкового типа (т.е. не вещественного), но не Longint. В данной лабораторной работе будут рассматриваться компоненты только простого типа.

Описание массива можно производить двумя способами: через задание типа массива и непосредственно.

Например:

TYPE {Создание массивов с использованием описателей типов}

mas1 = array[1..100] of integer; { описатель для целочисленных одномерных массивов длиной не более 100 элементов }

vector = array [1..30] of real; { описатель для вещественных одномерных массивов длиной не более 20 элементов }

mas2 = array[1..8, 1..10] of Char; { описатель для символьных двумерных массивов размерами не более 8 строк и 10 столбцов }

matrix = array[1..12] of vector; { описатель для вещественных двумерных массивов размерами не более 10 строк и 20 столбцов}

Последний описатель можно было бы задать без использования описателя типа vector:

matrix = array[1..12, 1..30] of real; }

VAR {здесь выделяется место под все массивы }

Names: mas2;

Numbers, Ages: mas1;

Day_Tempr, Day_Wind: vector;

Tempr1996: matrix;

Создание массивов без использования специальных описателей типов:

VAR Ball_Groop_1, B_M170: array[1..30] of real;

{ выделение места под два одномерных вещественных массива}

Prizn: array [1..10, 1..10] of boolean;

{ квадратный массив логических переменных}

B_M175: array[1..30] of real;

Ball_Kurs: array[1: 12, 1..30] of real;

{ выделение места под двумерный вещественный массив}

Массивы, созданные одним оператором описания или разными операторами, но использующими общий описатель, являются совместимыми; для них возможны операции присваивания, операции отношения (только равно и не равно). Для массивов описанных выше можно написать операторы:

...

Ball_Groop1: = B_M170;

Numbers: = Ages;

If Day_Tempr=Day_Wind then...

Но недопустим ни один из операторов:

Ball_Kurs: = Tempr1996;

Ball_Groop1: = B_M175;

B_M175: = B_M170;

While B_M175< > B_M170 do...

2. Алгоритмы основных методов сортировок (для всех случаев как пример рассмотрена сортировка чисел по возрастанию)

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

Алгоритм сортировки выбором. Это метод сортировки на месте (в одном массиве). В массиве ищется минимальный элемент и переставляется на место первого элемента (а первый элемент – на место найденного минимального). Потом этот процесс повторяется, но массив рассматривается со второго элемента (первый уже на месте). Найденный минимальный элемент меняется местами со вторым. Это повторяется до (n–1)-го элемента (n-ый элемент автоматически окажется на месте). Примечание: при поиске минимального элемента нужно находить и запоминать его место – для перестановки элементов.

Алгоритм сортировки обменом. Это также метод сортировки на месте (в одном массиве); некоторые алгоритмы этого метода носят название метода пузырька. Сравниваются два соседних элемента (первый и второй), если они в правильном порядке – ничего не делается, если порядок нарушен – они меняются местами. Потом этот процесс повторяется для второго и третьего элементов, и так до конца (n–1 и n-ый элементы). В результате самый большой элемент оказывается в самом конце (на n-ом месте). Затем весь этот процесс повторяется, но уже до n–1-го элемента (так как n-ый уже на месте); затем – до n–2-го и так всего n–1 раз. Тем самым n–1 элементов снизу окажутся упорядоченными, а следовательно и первый элемент тоже.

Алгоритм сортировки вставками. Этот метод относится к сортировкам в двух массивах. Имеется два массива. Один заполнен неупорядоченными числами, второй – пустой. Из первого берется первое число и переписывается на первое место во второй массив. Берется второе число и сравнивается с переписанным во второй массив. Если уже записанное число больше второго, оно переписывается на одну позицию ниже (на второе место), а последнее взятое число – на место первого. Затем из исходного массива берется третье число и сравнивается со вторым из выходного массива. Если оно должно вставляться выше второго, второе переписывается на позицию ниже. Далее сравнение проводится с первым числом и, если вставляемое число больше или равно первому, оно записывается на место, освободившееся от второго числа, иначе первое переписывается на позицию ниже, а вставляемое – на его место. Процесс повторяется, пока не будут вставлены на нужные места во второй массив все числа из первого.

Сортировка слиянием. Этот метод предполагает, что имеется два или несколько наборов данных, каждый из которых уже упорядочен. Нужно объединить их в один упорядоченный набор данных. Как входные, так и выходной наборы могут размещаться во внешней памяти (в файлах). Алгоритм заключается в том, что заводится столько указателей, сколько входных наборов данных объединяется одновременно; каждый указатель сначала указывает на первый элемент в каждом наборе. Выбирается самый маленький элемент из тех, на которые указывают эти указатели, и он переписывается в выходной массив, после чего указатель набора, из которого был переписан элемент, увеличивается на единицу (и теперь указывает на второй элемент этого набора). Далее снова производится выбор наименьшего элемента из тех, на которые указывают указатели, и так пока не будут выбраны все элементы из всех наборов. Если кончается один из наборов, а их всего два, то оставшиеся элементы второго набора дописываются в конец выводного файла. Если сливаются одновременно более двух наборов, вычерпанный набор перестает рассматриваться при выборе минимального элемента, или в этом наборе искусственно создается дополнительный элемент с очень большим ключом (каких не может быть у реальных элементов) и при выборе он никогда не будет взят. При этом не меняется схема выбора. Если первоначально было N упорядоченных коротких наборов данных, то объединяя их попарно этим методом, после первого прохода станет N/2 упорядоченных наборов, но каждый из них будет уже в два раза длиннее. Повторяя этот процесс и беря каждый раз выходные наборы в качестве входных для слияния, можно в итоге получить один упорядоченный набор. Первоначальные N наборов можно получить из исходного, например, беря по паре элементов, поменяв их местами, если они не в правильном порядке.

Разбор контрольного варианта