Задачи 4-ого класса

В поисковых задачах требуется найти элемент, удовлетворяющий заданному условию. Для этого требуется организовать перебор массива и проверку условия. Но при этом существует две возможности выхода из цикла:

- нужный элемент найден ;

- элемент не найден, но просмотр массива закончен.

Пример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) сравнений. Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, поэтому для небольших массивов простые методы более эффективны.

Простые методы подразделяются на три основные категории:

- сортировка методом простого включения;

- сортировка методом простого выделения;

- сортировка методом простого обмена;

Сортировка методом простого включения (вставки)

Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с 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;//вставка элемента

}