Классы задач по обработке массивов
Все задачи по обработке массивов можно разбить на перечисленные ниже классы, причем, отнесение задачи к тому или иному классу определяет выбор возможных методов решения задачи. Эти классы относятся как к одномерным, так и к двумерным массивам. Здесь рассматривается применение вводимой классификации для одномерных массивов. Двумерным массивам будет посвящена отдельная глава.
Классы задач:
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];
s=1;
}
else if (max= =a[i]) s+=1;
