5. Пятый класс задач.

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

6. Шестой класс задач.

Примерами подобного рода задач могут служить поиск первого отрицательного, первого положительного и любого первого элемента, отвечающего некоторому условию, поиск единственного элемента, равного некоторому конкретному значению. Особенность задач этого класса в том, что нет необходимости просматривать весь массив. Просмотр нужно закончить сразу, как только требуемый элемент будет найден. При этом может производиться как поэлементный просмотр, так и выборочная обработка массива. Однако, в худшем случае, для поиска элемента требуется просмотреть весь массив. Такой тип поиска называется линейным. Если массив не очень большой, затраты времени линейного поиска не столь заметны. Но при солидных объемах информации время поиска становится серьезным показателем. Поэтому существуют методы, позволяющие уменьшить время поиска: поиск с барьером и двоичный поиск. Чаще всего при программировании поисковых задач используются циклы с пред или пост условием, в которых условие выхода формируется из двух условий. Одно условие - пока элемент не найден, а второе - пока есть элементы массива. После выхода из цикла осуществляется проверка по какому из условий произошел выход.

Рассмотрим следующие примеры.

Пример1. Задан целочисленный массив из n элементов. Присвоить переменной k значение true, если в массиве существуют два одинаковых элемента, стоящих рядом, и false в противном случае.

Эту задачу можно решить, например, если последовательно сравнить каждый элемент массива с последующим. Так как рассматриваются все элементы, то одно условие - это достижение конца массива, а другое - обнаружение двух одинаковых соседних элементов. Именно переменная k и может быть использована в качестве второго условия. Пример алгоритма для решения этой задачи см. на рисунке 4.3.

Пример 2. Пусть необходимо отыскать в массиве отсортированном по убыванию элемент равный введенному.

Пример 3. Необходимо определить среди элементов, стоящих на четных местах первый отрицательный элемент.

2. Приемы программирования обработки матриц.

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

в разделе описания переменных VAR двумя способами:

1. как одномерный массив одномерных массивов

VAR

M: array[1..8] of array[char] of integer; {массив из 8 массивов на 256 целых чисел}

A,B: array[boolean] of array[byte] of real; {массив из 2-х массивов на 256 вещественных чисел}

C: array[1..5] of array[1..10] of char; {массив из 5 массивов на 10 символов}

2. как двумерный массив

VAR

MATR: array[1..8,char] of real; {матрица 8х256 вещественных чисел}

CMATR: array[1..5,1..10] of char; {символьная матрица 5х10 символов}

BMATR: array[byte,’A’..’Z’] of boolean; {матрица логических переменных 256х26 значений}

в разделе описания типов TYPE двумя способами:

1. как одномерный массив одномерных массивов

TYPE

MAS =array[char] of integer; {тип - массив на 256 целых чисел}

MASA = array[byte] of real; {тип - массив на 256 вещественных чисел}

MASC = rray[1..10] of char; {тип массив на 20 символов}

VAR

M:array[1..8] of MAS; {массив из 8 элементов типа MAS }

A,B: array[boolean] of MASA; {массив из двух элементов типа MASA }

C: array[1..5] of MASC; {массив из 5 элементов типа MASC }

2. как двумерный массив

TYPE

TMATR = array[1..8,char] of real; { тип -матрица 8х256 вещественных чисел}

TCMATR= array[1..5,1..6] of char; { тип - символьная матрица 5х10 символов}

TBMATR = array[byte,’A’..’Z’] of boolean; { тип - матрица логических переменных 256х26 значений}

VAR

MATR:T:TMATR; {переменная типа TMATR}

CMATR: TCMATR; {переменная типа TCMATR}

BMATR: TBMATR; {переменная типа TBMATR}

Рассмотрим наиболее распространенные приемы программирования обработки матриц, в соответствии с принятой классификации задач. Следует отметить, что программирование всех классов задач для матриц имеет свою специфику, основанную на том, что матрица, фактически, является массивом одномерных массивов. Это значит, что в каждом классе имеется гораздо больше различных вариантов решений да и самих задач тоже. Особенно много сочетаний различных классов задач в одной конкретно поставленной задаче обработки некоторой матрицы. Хотя можно выделить круг задач, который точно укладывается в классификацию.