Классы задач по обработке массивов
Перебор элементов массива
1) Элементы массива можно обрабатывать по одному элементу, двигаясь от начала массива к его концу (или в обратном направлении):
for(int i=0;i<n;i++) <обработка a[i]>
2) Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон массива к его середине:
int i=0,j=n-1;
while (i<j){
<обработка a[I] и a[j]>;
i++;j++;}
3) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 1(т. е. обрабатываются пары элементов a[0]и a[1], a[1]и a[2] и т. д.)
for(i=0;i<n-1;i++)
<обработка a[i] и a[i+1]>
4) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 2(т. е. обрабатываются пары элементов a[0]и a[1], a[2]и a[3] и т. д.)
i=1;
while(i<n){
<обработка a[i] и a[i+1]>
i:=i+2;}
1) К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка всех или указанных элементов массива. Решение таких задач сводится к установлению того, как обрабатывается каждый элемент массива или указанные элементы, затем подбирается подходящая схема перебора, в которую вставляются операторы обработки элементов массива. Примером такой задачи является нахождение среднего арифметического элементов массива.
2) К задачам 2 класса относятся задачи, в которых изменяется порядок следования элементов массива. Обмен элементов внутри массива выполняется с использованием вспомогательной переменной:
R=a[I];a[I]=a[J]; a[J]=R;//обмен a[I]и a[J]элементов массива.
3) К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких массивов или подмассивов одного массива. Массивы могут обрабатываться по одной схеме – синхронная обработка или по разным схемам – асинхронная обработка массивов.
4) К задачам 4 класса относятся задачи, в которых требуется отыскать первый элемент массива, совпадающий с заданным значением – поисковые задачи в массиве.
3. Сортировка массивов (дополнительно: Иванова, с. 97-106).
Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.
Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I=2, из исходной последовательности извлекается i-ый элемент и вставляется на нужное место готовой последовательности, затем i увеличивается на 1 и т. д.
готовая | исходная |
В процессе поиска нужного места осуществляются пересылки элементов больше выбранного на одну позицию вправо, т. е. выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с j:=i-1. Если выбранный элемент больше a[i], то его включают в отсортированную часть, в противном случае a[j] сдвигают на одну позицию, а выбранный элемент сравнивают со следующим элементом отсортированной последовательности. Процесс поиска подходящего места заканчивается при двух различных условиях:
- если найден элемент a[j]>a[i];
- достигнут левый конец готовой последовательности.
int i,j,x;
for(i=1;i<n;i++)
{
x=a[i]; // элемент, который будем вставлять
j=i-1;
while(x<a[j]&&j>=0) //поиск подходящего места
{
a[j+1]=a[j];/ /сдвиг вправо
j--;
}
a[j+1]=x;/ /вставка элемента
}
3.2. Сортировка методом простого выбора
Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.
мин |
int i,min,n_min,j;
for(i=0;i<n-1;i++)
{
min=a[i];n_min=i; // поиск мин-го
for(j=i+1;j<n;j++)
if(a[j]<min)
{
min=a[j];
n_min=j;
}
a[n_min]=a[i]; //обмен
a[i]=min;
}