Массивы (Методичка С++), страница 2

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

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

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

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

1.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 символов}

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

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 }

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

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}

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

1.2.1Первый класс задач.

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

Рассмотрим некоторые типовые алгоритмы задач первого класса.

Пример 1. Задана квадратная целочисленная матрица размера nn. Найти наибольший элемент матрицы и количество таких элементов.

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

Пример 2. Задана целочисленная матрица A(m, n). Вычислить сумму каждой стоки и результат записать в массив b(n).

Для вычисления суммы элементов некоторой строки с номером i необходимо организовать цикл для перебора всех элементов данной строки. Поэтому параметром этого цикла следует выбрать номер столбца j. Перед циклом с параметром j необходимо задать начальное значение суммы S=0. После окончания цикла результат присваивается соответствующему элементу массива b. Для обеспечения обхода всех строк матрицы параметром внешнего цикла следует выбрать номер строки i.

Рис. 6.2

Рис 6.1

1.2.2Второй класс задач.

В качестве примеров задач второго класса для матриц можно

Пример.1.. Дана действительная квадратная матрица порядка 2n. Получить новую матрицу, переставляя ее блоки размера nn в соответствии с рисунком.

Для решения этой задачи нужно определить правило, по которому будут преобразовываться индексы матрицы. Будем считать, что после преобразования получается новая квадратная матрица размерности 2n. Тогда внимательно изучив соответствие между элементами матрицы A и матрицы B, получаем следующий закон преобразования:

Алгоритм решения смотри на рисунке 6.3.

Рис. 6.3