Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных
delete [] Z;
DeleteY(Y,n); //Убийство связанного графа Игрыка!
//DeleteY(Z1,n); //Убийство связанного графа Зюблы!
cout<<"ntttPress
Any Key to continueb"<
getch(); //Ждём
нажатия любой
клавиши
}
////////////////////////////////////////////////////////////////////////////////
void
TimeOut(int Tik, float TikTak[], int Mas_x[], int Mas_y[],int
Mas_z[])
{
clrscr();
int
i=0,j=0,k=0,h=0,count=0;
cout<<'n';
for(;i
for
(k = 0; k < Tik; k++)
for
(i = 0; i < Tik; i++){
for
(int j = 0; j < Tik; j++) A[i][j] +=
(*MyMenu[j])(Mas_x[k],Mas_y[k],Mas_z[k]) *
(*MyMenu[i])(Mas_x[k],Mas_y[k],Mas_z[k]);
A[i][N]+=(*MyMenu[i])(Mas_x[k],Mas_y[k],Mas_z[k])*TikTak[k];
}
if(gordanA(N,M))cout<<"Матрица
вырождена!!!"; //N-колво
строк, M-кол-во
столбцов
//for(i=0;i
cout<<"ttt
O(nX,nY,nZ)=C1*nX*(nY+nZ)"<
for(i=0;i
cout
<<"nnКол-во дуг
ХtКол-во дуг
YtКол-во дуг
ZtЭкспериментtТеория";//<<"Mas_tx
Mas_Tnx";
double
*Mas_Tnz=new double[N];
for(i=0;i
for
(int y = 0; y < Tik; y++){
for
(i = 0; i < N; i++){Mas_Tnz[y] +=
((*MyMenu[i])(Mas_x[y],Mas_y[y],Mas_z[y]))*(A[i][N]);}
cout
<<"n"<
}
}
////////////////////////////////////////////////////////////////////////////////
void
TestTime(int n)
/* Х
- в последовательном
представлении
У
- в связанном
представлении
*/
{
clrscr(); //очистка
экрана
cerr<<"ttНемного
подождите -
идут эксперименты...n";
int
i,nX=0,nZ=0,nY=0;
float
TikTak[19],Secundomer=0;
int Mas_x[12],Mas_y[12],Mas_z[12];
for(int
Tik=0;Tik
n=n+Tik*5; //количество
генерируемых
вершин
Array
*X = new Array [nX]; //выделение
памяти для
графа в последоват
представлении
X
= GenSeX(n,nX); //чтение графа
в последовательном
представлении
Mas_x[Tik]=nX; //запоминаем
кол-во вершин
в графе ЫксА
Spisok
**Y = new Spisok *[n];//выделение
памяти для
графа в связанном
представлении
for
(int i=0;i
Y
= GenSeY(n,nY); //чтение графа
в связанном
представлении
Mas_y[Tik]=nY; //запоминаем
кол-во вершин
в графе ИгрикА
Array
*Z = new Array[n]; //выделение
памяти для
графа в последоват
представлении
cerr
<<"nЧисло вершин
в графе = "<
cout<<"nRaznostZ...";
nZ=nX; //так
надо Сергей
Михайловичь
Z=RaznostZ(n,nZ,X,Y,Z); //считаем
разность графов:
первый параметр
- число вершин,
второй и третий
//граффы
в соответствующем
представлении.
//cout<<"nnX="<
Mas_z[Tik]=nZ; //запоминаем
кол-во вершин
в графе зЮблА
cout<<"tttэтот
комп пока ещё
работает...nRasnostY...tttПовторяю
который раз?!
Ответ: ";
for(int
XXX=0;XXX<10;XXX++){ //цикл повторений
cout<<"b"<
Secundomer=clock(); //"..на
старт... внимпние
... марш!!!" - засекли
начала эксперимента.
Y=RaznostY(n,nX,X,Y); //считаем
разность графа
и записываем
это в граф Y
TikTak[Tik]=(clock()-Secundomer);//"Финиш!!!"
- получили конец
эксперимента
} //к.ц.
цикла вовторений
TikTak[Tik]=TikTak[Tik]/(10
* CLK_TCK);//Вычисление
тиков!!!
delete
[] X; //удаление из
памяти графа
Х
DeleteY(Y,n); //Убийство
связанного
графа Игрыка!
delete
[] Z;//удаление из
памяти графа
в последовательном
представлении
n-=Tik*5; //"предохраитель"
от геометрической
прогрессии...
} //к.ц.
для экспериментов!!!
//cout
<<"nMas_xtMas_ytMas-ztTikTak";
//for
(int y = 0; y < Tik; y++)cout <<"n"<
cout<<"nnесли
вы видите эту
надпись, значит
эксперименты
прошли удачно"
<<"ntPress
any key для вывода
результатов
на экран."<
getch(); //Ждём
нажатия любой
клавиши
TimeOut(Tik,TikTak,Mas_x,Mas_y,Mas_z);//вызываем
функцию общёта
всего и вся
cout<<"nntt
Press Any Key for exit to you system."<
getch(); //Ждём
нажатия любой
клавиши
}
///////////////////////////////////////////////////////////////////////////
void
main (void)
{
Demo();
TestTime(85);
}
///////////////////////////////////////////////////////////////////////////
Тесты.
Демонстрация
работоспособности
программы.
Имя файла
с данными задачи:
GrapH.txt
X в последовательном
0: 2
1: 1 3 0
2: 2 0 3
3: 3 0
Y в свяанном
0: 1 3
1: 1 0
2: 3 2
3: 2 3 1
Z=X-Y в последовательном
0: 2
1: 3
2: 0
3: 0
новый Y - в
связанном
представлении
0: 2
1: 3
2: 0
3: 0
Press
Any Key to continue
После предложения
программы
нажать любую
клавишу вы
видите перед
собой экран
следующего
содержания:
Немного
подождите -
идут эксперименты...
Число вершин
в графе = 85
RaznostZ... этот
комп пока ещё
работает...
RasnostY... Повторяю
который раз?!
Ответ:9
Число вершин
в графе = 90
RaznostZ... этот
комп пока ещё
работает...
RasnostY... Повторяю
который раз?!
Ответ:9
Число вершин
в графе = 95
RaznostZ... этот
комп пока ещё
работает...
RasnostY... Повторяю
который раз?!
Ответ:9
Число вершин
в графе = 100
RaznostZ... этот
комп пока ещё
работает...
RasnostY... Повторяю
который раз?!
Ответ:9
Число вершин
в графе = 105
RaznostZ... этот
комп пока ещё
работает...
RasnostY... Повторяю
который раз?!
Ответ:9
Число вершин
в графе = 110
RaznostZ... этот
комп пока ещё
работает...
RasnostY... Повторяю
который раз?!
Ответ:9
если вы
видите эту
надпись, значит
эксперименты
прошли удачно
Press any key для
вывода результатов
на экран.
После предложения
программы
нажать любую
клавишу вы
видите перед
собой экран
следующего
содержания:
O(nX,nY,nZ)=C1*nX*(nY+nZ)
C0=3.894613e-06
C1=1.953171e-06
C2=1.941442e-08
C3=7.187807e-12
C4=3.05476e05
Верш Кол-во
дуг Х Кол-во
дуг Y Кол-во
дуг Z Эксперимент
Теория
70 3028
3045 1120 0.06044
0.058657
75 3507 3531
1289 0.071429 0.074507
80 4032 3978
1471 0.082418 0.082331
85 4488 4577
1608 0.104396 0.103425
90 5136 5061
1898 0.126374 0.125175
95 5692
5638 2075 0.137363
0.138322
Press Any Key for exit
to you system.
В графе
эксперимент
я вывожу экспериментально
время – время
которое я получил
при выполнение
моей процедуры.
В графе теория
я вывожу значение
времени получившееся
при подстановке
мультипликативных
констант в
исходное уравнение.
Для демонстрации
работоспособности
программы я
вывожу некий,
случайно
сформированный
граф на дисплей
для маленькой
размерности
(в данном примере
4 вершины), далее
вывожу на экран
разность этих
графов. Как
легко убедиться,
в том что это
правильная
разность, можно
предположить,
что это будет
справедливо
и для графов
большей размерности.