Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Поволжский государственный университет телекоммуникаций и
Информатики
Заочный факультет
РЕГИСТРАЦИОННЫЙ № ______
Контрольная работа № _______ Вариант _______
по _____________________________________________________
Студент _________________________________________________
________________________________________________________
Факультет _________ курс ________ шифр __________ гр.______
Работа выслана «_____»_________________ 201__г.
Оценка _______________ Дата _______________201___г.
Подпись преподавателя ___________________
Самара 2013
Задание
Рассматривается граф программы – дерево. Граф программы не задается, а строится в процессе выполнения этой работы по исходным данным, приведенным в индивидуальном задании.
После построения графа по нему необходимо определить число маршрутов - вариантов для отладки. Также необходимо построить зависимость значений структурного параметра от числа узлов в графе Р.
В зависимости от варианта задания граф может быть построен как случайный, так и как детерминированный.
Правила построения графа ПО приводятся по вариантам ниже.
Вариант 5А
Число ребер выходящих из каждого узла постоянно детерминировано и равно m-1(кроме висячих узлов, для которых это число равно 0). Значения m равно 4. Число ребер , входящих в каждый узел ,равно 1( кроме корневого). Число узлов в графе ПО N равно 150.
Правило остановки по достижению заданного числа узлов N построение графа завершается. В отчет по выполнению работы представляются:
Таблица с именами всех вершин, таблица с именами висячих вершин, подсчитанное значение параметра для всех вершин, график изменения значений как функция изменения числа вершин Р, графическое представление первых двадцати узлов графа.
Листинг программы
//
// main.cpp
// RegularGraph
//
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <fstream>
#include <clocale>
#include <conio.h>
// параметры для варианта 5A
const int m = 4;
const int N = 150;
// правило завершения - по достижению заданного числа узлов
static std::ofstream ver_f;
static std::ofstream vis_ver_f;
// функция для вычисления структурного параметра
double alpha(int B, int P)
{
return static_cast<double>(P) / B;
}
///////////////////////// Функция построения дерева ////////////////////////////////
// элемент выходного массива
class name_t
{
public:
// конструктор для класса по умолчанию
name_t()
{
index = parent = 0;
}
// номер узла
int index;
// номер родительского узла
int parent;
};
// в массиве a от родителя с индексом [i-1][uj] порождает mx потомков присваивая
// каждому порядковый номер count и занося их в массив a на строку i
bool input(name_t (&a)[300][300], int i, int& j, int& uj, int& count)
{
for (int x = 0, end = m - 1; x < end; ++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;
}
void CreateTree(int &P, int &B)
{
// массив вершин
name_t ver[300][300];
// массив висячих вершин
std::vector<name_t> 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
{
// заполнение вершин текущего уровня
tree_end = input(ver, i, j, uj, P);
// если дерево выродилось
if (tree_end)
{
// все вершины остальные вершины предыдущего уровня остаются висячими
while (ver[i - 1][uj].parent)
{
vis_ver.push_back(ver[i - 1][uj]);
++uj;
}
break;
}
} while (ver[i - 1][uj].parent != 0);
// если вершин = N или дерево выродилось - прекращаем работу с текущим деревом
if (tree_end)
{
// все вершины последнего уровня считаются висячими
for (int x = 0; x < 300; ++x)
if (ver[i][x].index != 0)
vis_ver.push_back(ver[i][x]);
break;
}
}
// выводим в файл массив вершин
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());
}
// главная функция программы
int main(int argc, const char * argv[])
{
// установка русского языка
setlocale(LC_ALL, "Russian");
// процесс рандомизации теперь зависит от времени
srand(static_cast<int>(std::time(NULL)));
// параметры
int P, B;
double alphaValue;
// открытие выходных файлов
ver_f.open("массив_вершин.txt", std::ios::trunc);
vis_ver_f.open("массив_висячих_вершин.txt", std::ios::trunc);
// построение графа, для которого будет выведена таблица вершин
// таблица висячих вершин, а также гистограмма значения числа вершин
CreateTree(P, B);
// закрытие файлов
ver_f.close();
vis_ver_f.close();
// вычисление структурного параметра
alphaValue = alpha(B, P);
std::cout << "P = " << P << std::endl;
std::cout << "B = " << B << std::endl;
std::cout << "alpha = " << alphaValue << std::endl;
_getch();
return EXIT_SUCCESS;
}
Результаты выполнения программы
Рис. 1 – «Результат вычисления структурного параметра»
Результат построение графа, для которого выведена таблица вершин в файл «массив_вершин.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 101-34 102-34 103-34 104-35 105-35 106-35 107-36 108-36 109-36 110-37 111-37 112-37 113-38 114-38 115-38 116-39 117-39 118-39 119-40 120-40 121-40
122-41 123-41 124-41 125-42 126-42 127-42 128-43 129-43 130-43 131-44 132-44 133-44 134-45 135-45 136-45 137-46 138-46 139-46 140-47 141-47 142-47 143-48 144-48 145-48 146-49 147-49 148-49 149-50 150-50
Результат построение графа, для которого выведена таблица висячих вершин в файл «массив_висячих_вершин.txt»:
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 101-34 102-34 103-34 104-35 105-35 106-35 107-36 108-36 109-36 110-37 111-37 112-37 113-38 114-38 115-38 116-39 117-39 118-39 119-40 120-40 121-40 122-41 123-41 124-41 125-42 126-42 127-42 128-43 129-43 130-43 131-44 132-44 133-44 134-45 135-45 136-45 137-46 138-46 139-46 140-47 141-47 142-47 143-48 144-48 145-48 146-49 147-49 148-49 149-50 150-50
Рис. 2 – «График изменения значений как функция изменения числа вершин Р»
Рис. 3 – «Графическое представление первых двадцати узлов графа»