Сортировка массивов
Задачи 4-ого класса
Задачи 3-ого класса
Задачи 2-ого класса
Задачи 1-ого класса
Классы задач по обработке массивов
Перебор массива по два элемента
1) Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон массива к его середине:
int I=0, J=N-1;
while( I<J)
{обработка a[I] и a[J];I++;J--;}
2) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 1(т. е. обрабатываются пары элементов a[1]и a[2], a[2]и a[3] и т. д.):
for (I=1;I<N;I++)
{обработка a[I] и a[I+1]}
3) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 2 (т. е. обрабатываются пары элементов a[1]и a[2], a[3]и a[4] и т. д.)
int I=1;
while (I<N-1 )
{обработка a[I] и a[I+1];
I+=2;}
1) К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка всех или указанных элементов массива.
2) К задачам 2 класса относятся задачи, в которых изменяется порядок следования элементов массива.
3) К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких массивов или подмассивов одного массива. Массивы могут обрабатываться по одной схеме – синхронная обработка или по разным схемам – асинхронная обработка массивов.
4) К задачам 4 класса относятся задачи, в которых требуется отыскать первый элемент массива, совпадающий с заданным значением – поисковые задачи в массиве.
Решение таких задач сводится к установлению того, как обрабатывается каждый элемент массива или указанные элементы, затем подбирается подходящая схема перебора, в которую вставляются операторы обработки элементов массива. Примером такой задачи является нахождение максимального элемента массива или среднего арифметического массива.
#include<iostream.h>
#include<stdlib.h>
void main()
{
int a[100];
int n;
cout<<”\nEnter the size of array:”;cin>>n;
for(int I=0;I<n;I++)
{a[I]=rand()%100-50;
cout<<a[I]<<” “;
}
int Sum=0;
for(I=0;I<n;I++)
Sum+=a[I];
Cout<<”Среднее арифметическое=”<<Sum/n”;
}
Обмен элементов внутри массива выполняется с использованием вспомогательной переменной:
int R=a[I];a[I]=a[J]; a[J]:=R; // обмен a[I] и a[J] элементов массива.
Пример1.
Перевернуть массив.
//формирование массива
for(int i=0,j=n-1;i<j;i++,j--)
{int r=a[i];
a[i]=a[j];
a[j]=r;}
//вывод массива
Пример 2.
Поменять местами пары элементов в массиве: 1и2, 3 и 4, 5 и 6 и т. д.
for(int i=0;i<n-1;i+=2)
{int r=a[i];
a[i]=a[i+1];
a[i+1]=r;}
Пример 3.
Циклически сдвинуть массив на к элементов влево (вправо).
int k,i,t,r;
cout<<"\nK=?";cin>>k;
for(t=0;t<k;t++)
{
r=a[0];
for(int i=0;i<n-1;i++)
a[i]=a[i+1];
a[n-1]=r;
}
При синхронной обработке массивов индексы при переборе массивов меняются одинаково.
Пример 1. Заданы два массива из n целых элементов. Получить массив c, где c[I]=a[I]+b[I].
For(int I=0;I<n;I++)c[I]=a[I]+b[I];
При асинхронной обработке массивов индекс каждого массива меняется по своей схеме.
Пример 2. В массиве целых чисел все отрицательные элементы перенести в начало массива.
int b[10];//вспомогательный массив
int i,j=0;
for(i=0;i<n;i++)
if(a[i]<0){b[j]=a[i];j++;}//переписываем из а в b все отрицательные элементы
for(i=0;i<n;i++)
if(a[i]>=0){b[j]=a[i];j++;}// переписываем из а в b все положительные элементы
for(i=0;i<n;i++) cout<<b[I]<<” “;
Пример3.
Удалить из массива все четные числа
int b[10];
int i,j=0;
for(i=0;i<n;i++)
if(a[i]%2!=0){b[j]=a[i];j++;}
for(i=0;i<j;i++) cout<<b[i]<<" ";
cout<<"\n";
В поисковых задачах требуется найти элемент, удовлетворяющий заданному условию. Для этого требуется организовать перебор массива и проверку условия. Но при этом существует две возможности выхода из цикла:
- нужный элемент найден ;
- элемент не найден, но просмотр массива закончен.
Пример1. Найти первое вхождение элемента К в массив целых чисел.
int k;
cout<<"\nK=?";cin>>k;
int ok=0;//признак найден элемент или нет
int i,nom;
for(i=0;i<n;i++)
if(a[i]==k){ok=1;nom=i;break;}
if(ok==1)
cout<<"\nnom="<<nom;
else
cout<<"\nthere is no such element!";
Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.
Сортировки массивов подразделяются по быстродействию. Существуют простые методы сортировок, которые требуют n*n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют n*ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, поэтому для небольших массивов простые методы более эффективны.
Простые методы подразделяются на три основные категории:
- сортировка методом простого включения;
- сортировка методом простого выделения;
- сортировка методом простого обмена;