Решение задач первого класса

Классы задач по обработке массивов

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

Классы задач:

1) однотипная обработка всех или указанных элементов массива;

2) задачи, в результате решений которых изменяется структура (порядок следования элементов) массива;

3) обработка нескольких массивов одновременно. Сюда же относятся задачи, когда по-разному обрабатываются подмассивы одного и того же массива;

4) поисковые задачи для массивов.

Решение задач первого класса

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

Пример 1. Найти сумму (произведение) элементов одномерного массива.

Решение. Каждый элемент массива прибавляется к сумме s=s+a[i] или умножается на произведение предыдущих элементов массива p=p*a[i]. Поскольку требуется перебрать все элементы массива, можно выбрать схему перебора элементов по одному, двигаясь с начала или с конца массива.

{сумма элементов массива} {произведение элементов массива}

s=0; p=1;

i=0; i=n;

while (i<n) while( i>=0)

{ {

s=s+a[i]; p=p*a[i];

i=i+1; i=i-1;

} }

Пример 2. Подсчитать количество элементов массива, совпадающих по величине с заданным.

Решение. В этой задаче исходными данными являются одномерный массив и некоторое число, которое обозначим Х. Для ответа на вопрос задачи нужно каждый элемент массива сравнить с заданным. Если они совпадут, то счетчик совпавших элементов нужно увеличить на единицу. Поскольку нужно сравнить каждый элемент, то нужно выбрать схему перебора по одному элементу. В приведенном здесь решении выбрана схема перебора по одному от последнего элемента к первому. Ответ задачи будет храниться в счетчике совпавших элементов. Исходя из приведенных рассуждений, можно предложить такой вариант решения:

s=0;

for (i=n-1; i>=0; i--)

if (a[i] = =x) s++;

Пример 3. Найти максимальный элемент одномерного массива.

Решение. В этой задаче «действующие лица» - одномерный массив и его максимальный элемент. Одномерный массив является исходным данным, а максимальный элемент - результатом. Максимальный элемент массива будем хранить в переменной max. Для его поиска достаточно каждый элемент массива сравнить с max (max<a[i]). Начальным значением максимального элемента может быть значение произвольного элемента массива, чаще всего для этой цели выбирают первый элемент. Исходя из этих соображений, получаем следующий фрагмент программы:

const int n=10;

int[] a =new int[n]; //исходный массив

int i; //индекс массива

int max; //максимальный элемент массива

max=a[0];

for (i=1; i< n; i++)

if (max<a[i] ) max=a[i];

Console.WriteLine(«Максимальный элемент массива = »+max);

Пример 4. Найти номер максимального элемента массива.

Решение. В задаче используются понятия массива и номера максимального элемента. Обозначим массив так же, как в предыдущих примерах: номер текущего элемента массива будем обозначать i, а номер максимального элемента - kmax. Как обычно, для определения максимального элемента нужно сравнить каждый элемент с максимальным. В выбранных обозначениях такое сравнение запишется так: if (a[kmax]<a[i]) kmax =i. Поскольку нужно просмотреть все элементы массива, то, выбрав подходящую схему перебора, например, перебор по одному от первого элемента к последнему, получим следующее решение задачи. Здесь начальное значение номера максимального элемента выбрано равным 0, но оно может быть любым от 0 до n-1.

kmax =0;

for (i=1; i< n; i++)

if (a[kmax]<a[i]) kmax =i;

Console.WriteLine(«Номер максимального элемента массива »+kmax);

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

i=0; j=n-1;

while (i<j)

if (a[i]<a[j])

i=i+1;

else j=j-1;

Console.WriteLine(«Максимальный элемент массива = »+ a[i]);

Console.WriteLine(«Номер максимального элемента массива »+j)

Пример 5. Подсчитать количество элементов массива, совпадающих по величине с максимальным.

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

max=a[0];

for (i=1; i< n; i++)

if (max<a[i]) max=a[i];

s=0;

for (i=0; i< n; i++)

if (a[i] = =max) s+=1;

Сравнив два цикла в приведенном решении, заметим, что их можно объединить в один, увеличив скорость работы алгоритма.

max=a[0]; s=1; /* один совпавший с текущим максимальным уже есть, это a[1]*/

for (i=1; i< n; i++)

if (max<a[i])

{ //найден новый кандидат на максимум

max=a[i];