Интерполяционный поиск.

Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x . Если известно, что х находится между элементами a_l и a_r, то номер очередного элемента для сравнения вычисляется по формуле

 m=l+(r-l)*(x-a_l)/(a_r-a_l)

 Если совпадение найдено, то возвращается индекс элемента (m), иначе определяется, в какой части массива следует выполнять поиск, применяя к ней алгоритм интерполяционного поиска.

 

#include <iostream.h>

#include <conio.h>

void sort(int a[], int n)

{

 int i,j;

 int c;

 for(j=1;j<=n-1;j++)

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

if(a[i]>a[i+1])

   {c=a[i];a[i]=a[i+1];a[i+1]=c;}

}

void main(void)

{

 int a[10];

 int n;

 int i;

 cout<<"n? ";

 cin>>n;

 cout<<"a?";

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

cin>>a[i];

 sort(a,n);  //вызов функции сортировки

 cout<<"a: ";

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

cout<<a[i]<<' ';

 getch();

}

Рис. 2. Сортировка массива методом «пузырька»

 

Пример решения (вариант 13).

Задание: Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. Метод: Сортировка методом бинарной вставки.

 

Текст программы:

 

//Сортировка массива методом бинарной вставки

 

/*В программе первый элемент рассматривается как упорядоченный массив.

Далее из оставшейся части массива последовательно берутся элементы

И вставляются без нарушения упорядоченности в уже отсортированную часть

Массива. Так как массив отсортирован, то для поиска места элемента

Используется метод бинарного поиска*/

 

#pragma hdrstop

#pragma argsused

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <iomanip.h>

 

//Функция сортировки массива методом бинарной вставки

void sort(int a[], int n)

{

//Объявление переменных

int newElement, left, right, middle, i, j;

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

{

   //Обрабатываемый на данном этапе элемент

   newElement=a[i];

   //Границы отсортированной части массива

   left=0; right=i-1;

   while (left<=right)

   {

       //Средний элемент в отсортированной части

       middle=(left+right)/2;

       //Анализ отношения обрабатываемого и среднего элемента

       if (a[middle]<=newElement)

           left=middle+1;

       else

           right=middle-1;

   }

   //Сдвиг элементов вправо и вставка обрабатываемого элемента

   //на новое место

   for (j=i;j>right+1;j--) a[j]=a[j-1];

   a[right+1]=newElement;

}

}

 

//Основная программа

void main(void)

{

//Объявление переменных

int a[100],n,i;

//Ввод числа элементов массива

cout<<"Number of elements (from 1 to 100) >"; cin>>n;

cout<<endl;

//Заполнение массива и вывод его на экран

randomize();

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

{

   a[i]=rand()%100;

   cout<<setw(4)<<a[i];

}

cout<<endl<<endl;

//Вызов функции сортировки массива

sort(a,n);

//Вывод отсортированного массива на экран

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

   cout<<setw(4)<<a[i];

//Задержка

getch();

}

 

Тестовый пример:

 

Number of elements (from 1 to 100) >100

 

26 16 32 25 32 39 5 77 82 67 12 91 68 91 76 87 8 17 60 32 43 89 30 57 52 49 38 17 19 97 85 50 63 45 7 64 24 5 34 90 18 75 88 85 89 95 76 19 49 47 37 26 41 49 31 86 57 17 55 0 66 7 28 57 36 45 99 18 63 89 46 33 10 85 15 11 31 87 65 11 45 32 2 23 77 11 89 5 80 47 10 21 69 4 97 28 73 53 51 52

 

0 2 4 5 5 5 7 7 8 10 10 11 11 11 12 15 16 17 17 17 18 18 19 19 21 23 24 25 26 26 28 28 30 31 31 32 32 32 32 33 34 36 37 38 39 41 43 45 45 45 46 47 47 49 49 49 50 51 52 52 53 55 57 57 57 60 63 63 64 65 66 67 68 69 73 75 76 76 77 77 80 82 85 85 85 86 87 87 88 89 89 89 89 90 91 91 95 97 97 99

Лабораторная работа №5

Тема: Упорядочивание элементов массива.

Постановка задачи.

Разработать программу, которая вводит целочисленную матрицу из n строк и m столбцов (1<n<=100, 1<m<=50) и упорядочивает элементы матрицы. Правило упорядочивания определяется вариантом. Варианты заданий приведены в табл. 2.

Таблица 2.

Варианты заданий

№	Правило упорядочивания элементов матрицы
1	Упорядочить каждую строку по возрастанию элементов
2	Упорядочить строки по возрастанию последних элементов строк
3	Переместить в каждой строке все отрицательные элементы в начало строки, а неотрицательные – в конец
4	Разместить все положительные элементы в верхнюю левую область матрицы (заполняя ими матрицу по строкам слева направо), а неположительные – в нижнюю правую область
5	Разместить все максимальные элементы в верхнюю левую область матрицы (заполняя ими матицу построчно), а остальные – в нижнюю правую область
6	Упорядочить столбцы по убыванию первых элементов столбцов
7	Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по строкам ее элементы образовывали отсортированный по убыванию массив
8	Упорядочить каждую строку по убыванию элементов
9	Разместить все минимальные элементы в нижнюю правую область матрицы (заполняя ими матицу построчно), а остальные – в верхнюю левую область
10	Упорядочить каждый столбец по возрастанию элементов
11	Упорядочить столбцы по возрастанию последних элементов столбцов
12	Переместить в каждом столбце все отрицательные элементы в начало столбца, а неотрицательные – в конец
13	Разместить все положительные элементы в левую верхнюю область матрицы (заполняя ими матрицу по столбцам сверху вниз), а неположительные – в правую нижнюю область.
14	Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по столбцам ее элементы образовывали отсортированный по возрастанию массив
15	Упорядочить каждый столбец по убыванию элементов
16	Упорядочить столбцы по убыванию последних элементов столбцов
17	Упорядочить строки по возрастанию первых элементов строк
18	Упорядочить все элементы матрицы таким образом, чтобы при чтении матрицы по строкам ее элементы образовывали отсортированный по возрастанию массив
19	Разместить все максимальные элементы в верхнюю правую область матрицы (заполняя ими матицу по столбцам), а остальные – в нижнюю левую область
20	Разместить все отрицательные элементы в верхнюю левую область матрицы (заполняя ими матицу по строкам), а неотрицательные – в нижнюю правую область

Пример решения (вариант 13).

Задание: Разработать программу, которая вводит целочисленную матрицу из n строк и m столбцов (1<n<=100, 1<m<=50) и упорядочивает элементы матрицы. Правило упорядочивания: Разместить все положительные элементы в левую верхнюю область матрицы (заполняя ими матрицу по столбцам сверху вниз), а неположительные – в правую нижнюю область.

 

Текст программы:

//Упорядочивание матрицы

#pragma hdrstop

#pragma argsused

 

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <iomanip.h>

 

//Функция упорядочивания матрицы

/* Программа начинает просматривать матрицу по столбцам из левого верхнего угла, находя неположительный элемент, она меняет его местом с последним на данном проходе элементом, и сдвигает индекс последнего элемента на единицу влево (вверх

по столбцам из правого нижнего угла), начиная новый проход с начала матрицы. Проходы прекращаются при совпадении индекса просматриваемого элемента и индекса последнего на данном проходе элемента (если до этого не было найдено ни одного неположительного элемента*/

void sort(int a[][50], int n, int m)

{

int count=0,i=0,k,b; bool p;

do

{

   p=false;

   for (k=0;k<(n*m-1);k++)

   {

       if ((((n-1)-count%n)==k%n) && (((m-1)-count/n)==k/n))

       {

           p=true;

           break;

       }

       if (a[k%n][k/n]<0)

       {

           b=a[k%n][k/n];

           a[k%n][k/n]=a[(n-1)-count%n][(m-1)-count/n];

           a[(n-1)-count%n][(m-1)-count/n]=b;

           count++;

           break;

       }

   }

   i++;

}

while (p!=true);

}

 

//Функция заполнения матрицы

void fill(int a[][50], int n, int m)

{

int i,j;

randomize();

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

   for (j=0;j<m;j++)

   {

       //cout<<"a["<<(i+1)<<','<<(j+1)<<"]=";

       //cin>>a[i][j];

       a[i][j]=random(100)-50;

   }

}

 

//Функция вывода матрицы на экран

void print(int a[][50], int n, int m)

{

int i,j;

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

{

   for (j=0;j<m;j++)

       cout<<setw(4)<<a[i][j];

   cout<<endl;

}

cout<<endl;

}

 

//Основная программа

void main(void)

{

   //объявление переменных

   int a[100][50],i,j,n,m;

   //ввод числа строк и столбцов

   cout<<"Rows (from 1 to 100) >"; cin>>n;

   cout<<"Cols (from 1 to 50) >"; cin>>m;

   cout<<endl;

   //заполнение матрицы

   fill(a,n,m);

   //вывод матрицы на экран

   print(a,n,m);

   //упорядочивание

   sort(a,n,m);

   //вывод упорядоченной матрицы на экран

   print(a,n,m);

   //задержка

   getch();

}

 

Тестовый пример:

 

Rows (from 1 to 100) >10

Cols (from 1 to 50) >10

 

-3 35 7 11 -8 -23 9 -42 36 35

49 -16 -43 -23 37 35 -16 -36 23 1

 -43 37 26 29 18 -36 -7 -12 -44 0

0 -44 18 -40 35 39 -35 20 26 -45

39 -32 -23 -35 -28 -33 -24 -7 -47 -34

44 -35 -43 10 -45 31 -45 -47 13 7

16 5 41 38 -20 28 -12 -42 26 -40

 -48 -43 -37 -45 -28 48 -39 -31 16 17

15 40 20 26 -49 16 -27 -29 -2 29

 -15 5 -47 -12 11 -44 -4 5 13 6

 

6 35 7 11 28 -28 -16 -36 -47 -32

49 0 26 5 37 -36 -7 -12 -44 -44

29 37 26 29 18 -20 -35 -35 -37 -45

0 1 18 20 35 -33 -24 -7 -47 -34

39 35 13 9 31 -45 -45 -47 -43 -16

44 13 26 10 39 -28 -12 -42 -23 -40

16 5 41 38 35 -8 -39 -31 -43 -15

17 16 23 16 11 -12 -27 -29 -2 -48

15 40 20 26 -49 -44 -4 -40 -43 -43

7 5 36 48 -23 -45 -42 -23 -35 -3