Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Поволжский государственный университет телекоммуникаций и
Информатики
Заочный факультет
РЕГИСТРАЦИОННЫЙ № ______
Контрольная работа № _______ Вариант _______
по _____________________________________________________
Студент _________________________________________________
________________________________________________________
Факультет _________ курс ________ шифр __________ гр.______
Работа выслана «_____»_________________ 201__г.
Оценка _______________ Дата _______________201___г.
Подпись преподавателя ___________________
Самара 2013
Задание
Рассматривается граф программы – дерево. Граф программы не задается, а строится в процессе выполнения этой работы по исходным данным, приведенным в индивидуальном задании.
После построения графа по нему необходимо определить число маршрутов - вариантов для отладки. Также необходимо построить зависимость значений структурного параметра от числа узлов в графе Р.
В зависимости от варианта задания граф может быть построен как случайный, так и как детерминированный.
Правила построения графа ПО приводятся по вариантам ниже.
Варианты 10А-21А
Число ребер выходящих из каждого узла случайно и определяется с помощью датчика случайных чисел. Максимальное число ребер, выходящих из узла равно m-1(кроме висячих, для которых это число всегда равно 0).
Таким образом, число ребер, выходящих из узла распределено по равномерному закону в диапазоне 0 – (m-1). Правило остановки построения графа – по достижению числа узлов графа значения N, приведенного в задании.
После завершения построения одного случайного графа и определения для него структурного параметра необходимо построить еще R случайных графов ,для которых также определить параметр .
Все R значений , а также значений Р и В, из которых они получены помещаются в отдельную таблицу, там же определяются значение математического ожидания и дисперсии для .
Данная таблица, таблица вершин и таблица висячих вершин для одного из полученных случайных графов, а так же гистограмма полученных при построении графа значении числа исходящих из узлов ребер (m-1) предоставляются в отчете по выполнению работы.
В отчете также приводится граф (таблица вершин и таблица вися чих вершин), полученный при детерминированном значении числа исходящих из вершины ребер равным (m-1). Данный граф должен быть построен по тому же алгоритму с блокированием (обходом) датчика случайных чисел и должен быть использован при отладке алгоритма.
Таблица 1. Исходные данные для выполнения контрольной работы
|
Вариант |
15А |
|
m |
4 |
|
Число узлов в графе N |
100 |
|
Число графов R |
100 |
Листинг программы
//
// main.cpp
// RegularGraph
//
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <fstream>
#include <clocale>
#include <iomanip>
#include <conio.h>
// параметры для варианта 15A
const int m = 4;
const int N = 100;
const int R = 100;
// правило останова - достижение заданного числа вершин в графе
static std::ofstream ver_f;
static std::ofstream vis_ver_f;
// функция для вычисления структурного параметра
double alpha(int B, int P)
{
return static_cast<double>(P) / B;
}
//////////////// Классы для получения числа потомков для вершины //////////////////
// рандомное получение числа потоков
class RandChild
{
public:
int operator()(void) const
{
return std::rand() % m;
}
void printHist() const
{ }
};
// рандомное получение числа потоков накоплением гистограммы
class WriteRandChild
{
public:
// конструктор по умолчанию для класса
WriteRandChild() :
hist(m, 0)
{
}
// печать гистграммы
void printHist() const
{
// вывод значений гистограммы
std::cout << "\tZnacheniya dlya gistigrammy 1-ogo grafa: " << std::endl;
for (int i = 0; i < m; ++i)
std::cout << i << "-" << hist[i] << std::endl;
std::cout << "\tMatematicheskoe ojidanie dlya gistogrammy: " << std::endl;
double mo = 0.0;
int s = 0;
for (int i = 0; i < m; ++i)
{
mo += i * hist[i];
s += hist[i];
}
mo /= s;
std::cout << mo << std::endl;
}
int operator()(void) const
{
int value = std::rand() % m;
++hist[value];
return value;
}
private:
// гистограмма
mutable std::vector<int> hist;
};
// детерминированное получение числа потоков (то есть получаем регулярное дерево)
class RegularChild
{
public:
int operator()(void) const
{
return m - 1;
}
void printHist() const
{ }
};
///////////////////////// Функция построения дерева ////////////////////////////////
// элемент выходного массива
struct name
{
// номер узла
int index;
// номер родительского узла
int parent;
// конструктор для класса по умолчанию
name() :
index(), parent()
{
}
};
// в массиве a от родителя с индексом [i-1][uj] порождает mx потомков присваивая
// каждому порядковый номер count и занося их в массив a на строку i
bool input(name (&a)[300][300], int i, int& j, int& uj, int& count, int mx)
{
for (int x = 0; x < mx; ++x, ++j)
{
if (count - 1 == N)
return true;
a[i][j].index = count++;
a[i][j].parent = a[i-1][uj].index;
}
++uj;
return false;
}
template <typename GetChild>
bool CreateTree(int &P, int &B, bool print = false)
{
GetChild childGetter;
// массив вершин
name ver[300][300];
// массив висячих вершин
std::vector<name> vis_ver;
// высота текущего дерева
P = 2u;
// корень дерева имеет порядковый номер 1 и номер родителя 1
ver[0][0].index = ver[0][0].parent = 1u;
// дерево не выродилось
bool tree_end = false;
int i;
for (i = 1u; i < 300; i++)
{
int uj = 0; // столбец верхней строки
int j = 0; // столбец текущей строки
// цикл до тех пор, пока все вершины текущего уровня не будут пройдены
do
{
int mx = childGetter();
if (mx == 0)
{
// если у корня 0 потомков, такое дерево не считаем
if (i == 1u)
continue;
// поскольку у вершины нет потомков, то по определению она считается
// висячей
vis_ver.push_back(ver[i - 1][uj]);
// переходим на следующую вершину верхнего уровня
++uj;
// если дерево выродилось
if (ver[i][0].index == 0 && ver[i-1][uj].index == 0)
tree_end = true;
}
else
{
// заполнение вершин текущего уровня
tree_end = input(ver, i, j, uj, P, mx);
// если достигнуто правило останова, то все
if (tree_end)
{
// все вершины остальные вершины предыдущего уровня остаются висячими
while (ver[i - 1][uj].parent != 0)
{
vis_ver.push_back(ver[i - 1][uj]);
++uj;
}
break;
}
}
} while (ver[i - 1][uj].parent != 0);
// если вершин = N или дерево выродилось - прекращаем работу с текущим деревом
if (tree_end)
{
if (P - 1 < N)
{
// сгенерировалось маленькое дерево
// значит генерируем другое
return false;
}
// все вершины последнего уровня считаются висячеми
for (int x = 0; x < 300; ++x)
if (ver[i][x].index != 0)
vis_ver.push_back(ver[i][x]);
break;
}
}
if (print)
{
// выводим в файл массив вершин
bool printed = true;
for (int x = 0, end = i + 1; x < end && printed; x++)
{
printed = false;
for (int y = 0; y < 300; y++)
if (ver[x][y].parent != 0)
{
ver_f << ver[x][y].index << "-" << ver[x][y].parent << " ";
printed = true;
}
ver_f << std::endl;
}
// выводим в файл массив висячих вершин
for (int x = 0, end = static_cast<int>(vis_ver.size()); x < end; x++)
vis_ver_f << vis_ver[x].index << "-" << vis_ver[x].parent << " ";
}
--P;
B = static_cast<int>(vis_ver.size());
// вывод гистограммы
childGetter.printHist();
return true;
}
// главная функция программы
int main(int argc, const char * argv[])
{
// установка русского языка
setlocale(LC_ALL, "Russian");
// процесс рандомизации теперь зависит от времени
srand(static_cast<int>(std::time(NULL)));
// построение R случайных деревьев
{
// таблица значений alpha
double alphaTable[R];
// таблица значений P
int PTable[R];
// таблица значений B
int BTable[R];
// открытие выходных файлов
ver_f.open("массив_вершин.txt", std::ios::trunc);
vis_ver_f.open("массив_висячих_вершин.txt", std::ios::trunc);
// построение графа, для которого будет выведена таблица вершин
// таблица висячих вершин, а также гистограмма значения числа вершин
while (!CreateTree<WriteRandChild>(PTable[0], BTable[0], true))
;
// закрытие файлов
ver_f.close();
vis_ver_f.close();
for (int i = 1u; i < R; ++i)
{
// построение дерева с номером i
while (!CreateTree<RandChild>(PTable[i], BTable[i]))
;
}
// вычисление структурного параметра
for (int i = 0; i < R; ++i)
alphaTable[i] = alpha(BTable[i], PTable[i]);
// вывод таблицы значений
std::cout << std::setw(4) << "N";
std::cout << std::setw(4) << "P";
std::cout << std::setw(4) << "B";
std::cout << std::setw(10) << "alpha" << std::endl;
for (int i = 0; i < R; ++i)
{
std::cout << std::setw(4) << i << ".";
std::cout << std::setw(4) << PTable[i];
std::cout << std::setw(4) << BTable[i];
std::cout << std::setw(10) << std::setprecision(3) << alphaTable[i] << std::endl;
}
// определение математического ожидания параметра альфа
double M = 0.0;
for (int i = 0; i < R; ++i)
M += alphaTable[i];
M /= R;
std::cout << "Matematicheskoe ojidanie alpha: " << M << std::endl;
// определени дисперсии
double D = 0.0;
for (int i = 0; i < R; ++i)
D += std::pow(M - alphaTable[i], 2.0);
D /= R;
std::cout << "Dispersiya alpha: " << D << std::endl;
std::cout << std::endl << std::endl;
std::cout << "Dannye dlya sluchaino postroennogo grafa (kotoryi vyveden v fail): " << std::endl;
std::cout << "P = " << PTable[0] << std::endl;
std::cout << "B = " << BTable[0] << std::endl;
std::cout << "alpha = " << alphaTable[0] << std::endl;
}
// построение детерминированного графа
{
int P = 0, B = 0;
// открытие выходных файлов
ver_f.open("детер_массив_вершин.txt", std::ios::trunc);
vis_ver_f.open("детер_массив_висячих_вершин.txt", std::ios::trunc);
// генерация графа
CreateTree<RegularChild>(P, B, true);
// закрытие файлов
vis_ver_f.close();
ver_f.close();
std::cout << std::endl << std::endl;
std::cout << "Dannye dlya determinirovannogo grafa (kotoryi vyveden v fail): " << std::endl;
std::cout << "P = " << P << std::endl;
std::cout << "B = " << B << std::endl;
std::cout << "alpha = " << alpha(B, P) << std::endl;
}
_getch();
return EXIT_SUCCESS;
}
Результаты выполнения программы
Рис. 1 – «Результат построения случайных графов»
Рис. 2 – «Результат вычисления, структурного параметра, математического ожидания и дисперсии структурного параметра»
Результат построение графа, для которого выведена таблица вершин в файл «массив_вершин.txt»:
1-1
2-1 3-1 4-1
5-2 6-3 7-4
8-7
9-8
10-9 11-9 12-9
13-11 14-12 15-12
16-13 17-13 18-15 19-15 20-15
21-17 22-17 23-18 24-18 25-19 26-19 27-19 28-20 29-20 30-20
31-21 32-21 33-22 34-24 35-25 36-25 37-25 38-26 39-26 40-26 41-27 42-28 43-28 44-30 45-30 46-30
47-32 48-32 49-33 50-33 51-33 52-34 53-34 54-36 55-36 56-36 57-39 58-41 59-41 60-42 61-43 62-43 63-45 64-45 65-45 66-46 67-46
68-47 69-47 70-48 71-48 72-48 73-49 74-50 75-50 76-51 77-51 78-51 79-52 80-53 81-53 82-55 83-55 84-57 85-57 86-57 87-58 88-58 89-59 90-59 91-60 92-60 93-60 94-62 95-62 96-63 97-63 98-63 99-65 100-65
Результат построение графа, для которого выведена таблица висячих вершин в файл «массив_висячих_вершин.txt»:
5-2 6-3 10-9 14-12 16-13 23-18 29-20 31-21 35-25 37-25 38-26 40-26 44-30 54-36 56-36 61-43 64-45 66-46 67-46 68-47 69-47 70-48 71-48 72-48 73-49 74-50 75-50 76-51 77-51 78-51 79-52 80-53 81-53 82-55 83-55 84-57 85-57 86-57 87-58 88-58 89-59 90-59 91-60 92-60 93-60 94-62 95-62 96-63 97-63 98-63 99-65 100-65
Результат построение детерминированного графа, для которого выведена таблица вершин в файл «детер_массив_вершин.txt»:
1-1
2-1 3-1 4-1
5-2 6-2 7-2 8-3 9-3 10-3 11-4 12-4 13-4
14-5 15-5 16-5 17-6 18-6 19-6 20-7 21-7 22-7 23-8 24-8 25-8 26-9 27-9 28-9 29-10 30-10 31-10 32-11 33-11 34-11 35-12 36-12 37-12 38-13 39-13 40-13
41-14 42-14 43-14 44-15 45-15 46-15 47-16 48-16 49-16 50-17 51-17 52-17 53-18 54-18 55-18 56-19 57-19 58-19 59-20 60-20 61-20 62-21 63-21 64-21 65-22 66-22 67-22 68-23 69-23 70-23 71-24 72-24 73-24 74-25 75-25 76-25 77-26 78-26 79-26 80-27 81-27 82-27 83-28 84-28 85-28 86-29 87-29 88-29 89-30 90-30 91-30 92-31 93-31 94-31 95-32 96-32 97-32 98-33 99-33 100-33
Результат построение детерминированного графа, для которого выведена таблица висячих вершин в файл «детер_массив_висячих_вершин.txt»:
34-11 35-12 36-12 37-12 38-13 39-13 40-13 41-14 42-14 43-14 44-15 45-15 46-15 47-16 48-16 49-16 50-17 51-17 52-17 53-18 54-18 55-18 56-19 57-19 58-19 59-20 60-20 61-20 62-21 63-21 64-21 65-22 66-22 67-22 68-23 69-23 70-23 71-24 72-24 73-24 74-25 75-25 76-25 77-26 78-26 79-26 80-27 81-27 82-27 83-28 84-28 85-28 86-29 87-29 88-29 89-30 90-30 91-30 92-31 93-31 94-31 95-32 96-32 97-32 98-33 99-33 100-33