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

Тема: Перегрузка функций.

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

Используя алгоритм упорядочивания матрицы, разработанный в лабораторной работе №5, разработать и протестировать две перегруженные функции, одна из которых обрабатывает целочисленную матрицу, другая - вещественную матрицу (варианты 3-5, 9, 12, 13,19, 20) или матрицу, элементы которой строки (варианты 1, 2, 6-8, 10, 11, 14-18).

 

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

Задание: Используя алгоритм упорядочивания матрицы, разработанный в лабораторной работе №5, разработать и протестировать две перегруженные функции, одна из которых обрабатывает целочисленную матрицу, другая - вещественную матрицу (варианты 3-5, 9, 12, 13,19, 20).

 

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

 

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

 

#pragma hdrstop

#pragma argsused

 

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <iomanip.h>

 

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

 

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);

}

 

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

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

{

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

int count=0,i=0,k;

float 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);

}

 

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

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]=rand()%100-50;

   }

}

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

void fill(float 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]=(rand()%1000-500)/100.0;

   }

}

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

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;

}

 

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

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

{ int i,j;

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

{

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

       cout<<setprecision(2)<<setw(6)<<a[i][j];

   cout<<endl;

}

cout<<endl;

}

 

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

void main(void)

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

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

   float b[100][50];

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

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

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

   cout<<endl;

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

   fill(a,n,m);

   fill(b,n,m);

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

   print(a,n,m);

   print(b,n,m);

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

   sort(a,n,m);

   sort(b,n,m);

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

   print(a,n,m);

   print(b,n,m);

   //задержка

   getch();

}

 

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

 

Rows (from 1 to 100) >10

Cols (from 1 to 50) >10

 

 -22 -26 -6 -9 -31 29 -39 32 -44 -13

37 39 -34 21 35 -30 -33 27 -22 26

9 30 -47 -21 -10 -21 12 -41 28 29

 -45 13 -1 7 -28 -2 47 5 -17 -22

 -29 24 -4 20 33 -33 43 -1 -5 -7

-7 11 44 40 -45 -3 42 -36 39 10

 -28 -8 7 18 0 -8 -38 -13 -17 35

0 26 -5 34 -35 -34 16 2 -44 -4

 -10 -6 41 -25 -17 -31 -47 33 0 14

9 -31 -11 28 -3 18 44 0 2 40

 

-4.7 0.24 1.4 3.4 -4.8 -1.2 -3.9 3.8 1.1 -1.6

-3.1 2.9 3.2 -4.3 -4.2 -2.8 3.2 4.8 -0.72 -3.2

0.59 -3.2 0.03 1.3 -1.6 0.29 4.6 -3.9 -3.2 2.8

-4 0.63 -1.5 2.6 2.2 0.48 2 3.5 -3.7 0.28

3.2 3.7 3.5 -2.3 -1.2 3.2 3.9 -2.5 0.45 -2.6

1.4 -0.39 -1.1 2.9 0.05 3.5 -1.1 -0.86 -3.1 -2.4

3.2 0.42 -1.4 4.7 -0.5 4.4 2.1 0.37 3.3 3.8

1.5 -4.2 -2.5 -1.2 1.1 -4.8 -1.3 1.5 0.06 0.46

3.4 0.44 0.91 -4.8 4.3 0.19 -4 1.8 -2.5 4.6

 -0.41 2.2 -4.6 -0.22 -1.5 -0.32 -3.1 2.5 -3.5 -0.1

 

40 39 5 47 29 -30 -33 -47 -22 -10

37 39 27 21 35 -21 -25 -41 -6 0

9 30 32 12 33 -2 -21 -34 -17 -22

14 13 44 7 -28 -33 -9 -1 -5 -7

35 24 16 20 -45 -3 -11 -36 -8 -28

10 11 44 40 0 -8 -38 -13 -17 -7

29 28 7 18 -35 -34 -5 -6 -44 -4

26 26 42 34 -17 -31 -47 -31 0 -29

2 33 41 18 -3 -31 -4 0 -26 -45

9 2 43 28 -10 -39 -1 -44 -13 -22

 

4.6 0.24 1.4 3.4 3.9 3.5 -0.5 -4.8 -0.72 -3.2

0.46 2.9 3.2 0.37 2 3.2 -1.2 -3.9 -3.2 -0.39

0.59 2.8 0.03 1.3 4.6 0.29 -1.6 -1.2 -3.7 -3.2

3.8 0.63 0.45 2.6 2.2 0.48 -4.2 -2.5 -1.1 -2.6

3.2 3.7 3.5 3.5 3.2 -2.8 -1.1 -0.86 -3.1 -2.4

1.4 0.06 1.1 2.9 0.05 -1.2 -4.8 -2.3 -1.5 -0.41

3.2 0.42 2.5 4.7 0.19 -4.8 -1.3 -4.3 -4.2 -4

1.5 3.3 1.8 4.8 1.1 -1.5 -4 -4.6 -2.5 -3.1

3.4 0.44 0.91 3.8 4.3 -0.32 -3.1 -2.5 -3.5 -0.1

0.28 2.2 1.5 2.1 4.4 -3.9 -0.22 -1.4 -1.6 -4.7

 

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

Тема: Шаблоны функций

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

Создать шаблон функции, выполняющей сортировку или поиск элементов в массиве. Протестировать шаблон для массивов с элементами различных типов: для вариантов 2, 10 и 20 – int , short и char , а для остальных вариантов - int , float и char . Варианты заданий:

№.	Метод сортировки (поиска)
1	Сортировка простой (линейной) вставкой
2	Бинарный поиск
3	Сортировка слиянием (метод фон Неймана)
4	Сортировка методом бинарной вставки без использования рабочего массива
5	Сортировка Шелла (слияние с обменом)
6	Быстрая сортировка (метод Хоара)
7	Комбинированный метод быстрой сортировки с методом «пузырька»
8	Внешняя двухфазная сортировка прямым слиянием
9	Челночная сортировка (сортировка с просеиванием)
10	Интерполяционный поиск
11	Сортировка методом центрированной вставки (нахождение медианы)
12	Шейкер – сортировка
13	Сортировка методом бинарной вставки с использованием рабочего массива
14	Обменная сортировка
15	Внешняя однофазная сортировка прямым слиянием
16	Внешняя сортировка естественным слиянием
17	Сортировка Шелла (слияние с обменом)
18	Внешняя сортировка сбалансированным слиянием
19	Сортировка простой (линейной) вставкой
20	Бинарный поиск

 

 

Методические указания

Пример шаблона функции перестановки значения двух числовых переменных приведен на рис. 3.

 

template <class t>

void change (t a, t b)

{

t c;

c=a; a=b; b=c;

}

           Рис. 3. Шаблон функции

 

 

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

 

Задание: Создать шаблон функции, выполняющей сортировку или поиск элементов в массиве. Протестировать шаблон для массивов с элементами различных типов: для вариантов 2, 10 и 20 – int , short и char , а для остальных вариантов - int , float и char .

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

 

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

//Использование шаблона функции

 

#pragma hdrstop

#pragma argsused

 

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <iomanip.h>

 

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

template <class TP>

void sort(TP a[], int n)

{

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

int left, right, middle, i, j;

TP newElement;

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 fill(int a[], int n)

{

randomize();

int i;

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

   a[i]=rand()%1000;

}

 

void fill(float a[], int n)

{

randomize();

int i;

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

   a[i]=(rand()%1000)/100.0;

}

 

void fill(char a[], int n)

{

randomize();

int i;

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

   a[i]=rand()%200+56;

}

 

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

//(перегруженная функция)

void print(int a[], int n)

{

int i;

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

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

cout<<endl<<endl;

}

 

void print(float a[], int n)

{

int i;

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

   cout<<setprecision(2)<<setw(6)<<a[i];

cout<<endl<<endl;

}

 

void print(char a[], int n)

{

int i;

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

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

cout<<endl<<endl;

}

 

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

void main(void)

{

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

float a[100]; int b[100]; char c[100]; int n;

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

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

cout<<endl;

//Заполнение массивов

fill(a,n); fill(b,n); fill(c,n);

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

print(a,n); print(b,n); print(c,n);

cout<<endl<<endl;

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

sort(a,n); sort(b,n); sort(c,n);

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

print(a,n); print(b,n); print(c,n);

//Задержка

getch();

}

 

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

 

Number of elements (from 1 to 100) >10

 

2 8.4 8.9 7.4 9.7 8.7 9.4 2.7 5.8 4.3

 

197 836 885 736 966 867 943 266 577 431

 

э \ Ќ А Ю { З z й W

 

2 2.7 4.3 5.8 7.4 8.4 8.7 8.9 9.4 9.7

 

197 266 431 577 736 836 867 885 943 966

 

Ќ А З Ю й э W \ z {