return n;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
Array *RaznostZ(int n,int &n1,Array *X,Spisok **Y,Array *Z)
/*обьединение в последовательном представлении
N - кол-во вершин в новом графе, N2 - кол-во дуг в Y.*/
{float i,j,newn=0;
Array *newX = new Array [n1]; //выделение памяти для графа в последоват представлении
//cout<<' ';
for(i=0;i<n1;i++){//cout<<"\b\"; //цикл для графа в пследовательном пред.
for(j=0;j<n;j++) //цикл для графа в связанном пред.
if(X[i].I==j){//cout<<"\bД"; //если совпали выходищие вершины...
Spisok *max=Y[j]; //max глядит на начало списка Y[j]
int Flag=0; //Просто флаговая переменная
while(max!=NULL){ //Проверяем на совпадения "входящие" вершины
if(X[i].J==max->index){Flag=1;break;}//если нашли повторение, то выход
max=max->next; //передвигаемся на следующий элемент списка
}
if(Flag==0){ //если не было совпадений вершин, то... всё понятно:
newX[newn].I=X[i].I;
newX[newn].J=X[i].J;
newn++;
}
//cout<<"\b|";
}
//cout<<"\b/";
}
//cout<<"\b \b";
n1=newn;
delete [] Z;
return newX;
}
////////////////////////////////////////////////////////////////////////
void DeleteY(Spisok **Z,int n)
{int i=0;
Spisok *rex;
for(i=0;i<n-1;i++){
rex=Z[i];
while(rex!=NULL){Z[i]=rex->next;delete rex;rex=Z[i];}
delete Z[i];
}
delete [] Z;
}
////////////////////////////////////////////////////////////////////////////////
Spisok** RaznostY(int n,int n1,Array *X, Spisok **Y)
{/*Расчет разности графов Z=X-Y
Z,Y - связанном представлении, X - в последовательном.
n - кол-во вершин графа, n1 - кол-во дуг графа*/
int i,j;
Spisok **Z = new Spisok *[n];//выделение памяти для графа в связанном представлении
for (i=0;i<n;i++) {Z[i] = new Spisok;Z[i]= NULL;}//выделение памяти для графа в связанном представлении
//cout<<' ';
for(i=0;i<n1;i++){//cout<<"\b\/"; //цикл для графа в пследовательном пред.
for(j=0;j<n;j++) //цикл для графа в связанном пред.
if(X[i].I==j){//cout<<"\bД"; //если совпали выходищие вершины...
Spisok *max=Y[j]; //max глядит на начало списка Y[j]
int Flag=0; //Просто флаговая переменная
while(max!=NULL){ //Проверяем на совпадения "входящие" вершины
if(X[i].J==max->index)Flag=1;//если нашли повторение, то выход
max=max->next; //передвигаемся на следующий элемент списка
}
if(Flag==0){ //если небыло совпадений вершин, то... всё понятно:
Spisok *end=Z[j], *beg=Z[j], *pred=Z[j];
while (end !=NULL) {pred = end ;end = end ->next;}
end = pred;
if((beg==NULL)&&(end==NULL))Z[j]=beg=end=new(Spisok);
else end = end -> next = new (Spisok);
end -> next = NULL;
end -> index = X[i].J;
}
//cout<<"\b|";
}
//cout<<"\b\";
}
//cout<<"\b \b";
DeleteY(Y,n); //Убийство связанного графа Игрыка!
return Z;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
void Demo(void)
/* Х - в последовательном представлении
У - в связанном представлении*/
{ int n=4,N2;
clrscr(); //очистка экрана
CursorOff();
cout<<"\t\tДемонстрация работоспособности программы."<<endl;
char st [] ="GrapH.txt"; //имя генерируемого файла
cout<<"\t\tИмя файла с данными задачи: "<<st<<endl;
WriteFile(st,n); //генерация файла с н вершинами
n=HowMuch(st); //подсчет числа вершин графов
int N1 = Number(N2,st); //подсчет числа дуг
Array *X = new Array [N1]; //выделение памяти для графа в последоват представлении
X = ReadFileX(X,st); //чтение графа в последовательном представлении
cout << "\n X в последовательном";
print3(X,N1,n); //вывод графа в последовательном представлении
Spisok **Y = new Spisok *[n]; //выделение памяти для графа в связанном представлении
for (int i=0;i<n;i++) Y[i] = new Spisok;//выделение памяти для графа в связанном представлении
Y = ReadFileY(Y,st); //чтение графа в связанном представлении
cout << "\n Y в свяанном";
print2(Y,n); //печать графа в связанном представлении
Array *Z = new Array[n]; //выделение памяти для графа в последоват представлении
int nZ=N1;
Z=RaznostZ(n,nZ,X,Y,Z); //считаем разность графов: первый параметр - число вершин, второй и третий
//граффы в соответствующем представлении.
cout<<"\n Z=X-Y в последовательном";
print3(Z,nZ,n); //вывод графа в последовательном представлении
//Spisok **Z1 = new Spisok *[n];//выделение памяти для графа в связанном представлении
//for (i=0;i<n;i++) {Z1[i] = new Spisok;Z1[i]= NULL;}//выделение памяти для графа в связанном представлении
Y=RaznostY(n,N1,X,Y); //считаем разность графа и записываем это в граф Y
cout<<"\n новый Y - в связанном представлении"; //Вывод подсказки - "Что делать"
print2(Y,n); //печать графа в связанном представлении
delete [] X; //удаление из памяти графа Х
delete [] Z;
DeleteY(Y,n); //Убийство связанного графа Игрыка!
//DeleteY(Z1,n); //Убийство связанного графа Зюблы!
cout<<"\n\t\t\tPress Any Key to continue\b"<<flush;//Вывод подсказки - "Что делать дальше"
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<N;i++)for(;j<M;j++) A[i][j]=0;
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<N;i++){cout<<'\n';for(j=0;j<M;j++) cout<<A[i][j]<<'\t';}
cout<<"\t\t\t O(nX,nY,nZ)=C1*nX*(nY+nZ)"<<endl;
for(i=0;i<N-1;i++) cout<<"\n\t\t\t\tC"<<i<<'='<<A[i][M];
cout <<"\n\nКол-во дуг Х\tКол-во дуг Y\tКол-во дуг Z\tЭксперимент\tТеория";//<<"Mas_tx Mas_Tnx";
double *Mas_Tnz=new double[N];
for(i=0;i<Tik;i++) Mas_Tnz[i]=0;
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"<<Mas_x[y]<<"\t\t"<< Mas_y[y]<<"\t\t"<<Mas_z[y]<<"\t\t"<<TikTak[y]<<"\t"<<Mas_Tnz[y];
}
}
////////////////////////////////////////////////////////////////////////////////
void TestTime(int n)
/* Х - в последовательном представлении
У - в связанном представлении
*/
{
clrscr(); //очистка экрана
cerr<<"\t\tНемного подождите - идут эксперименты...\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;Tik++){ //цикл начала экспериментов от Н до Н+45
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<n;i++){Y[i] = new Spisok;Y[i]=NULL;}//выделение памяти для графа в связанном представлении
Y = GenSeY(n,nY); //чтение графа в связанном представлении
Mas_y[Tik]=nY; //запоминаем кол-во вершин в графе ИгрикА
Array *Z = new Array[n]; //выделение памяти для графа в последоват представлении
cerr <<"\nЧисло вершин в графе = "<<n;
cout<<"\nRaznostZ...";
nZ=nX; //так надо Сергей Михайловичь
Z=RaznostZ(n,nZ,X,Y,Z); //считаем разность графов: первый параметр - число вершин, второй и третий
//граффы в соответствующем представлении.
//cout<<"\nnX="<<nX<<"\tnY="<<nY<<"\tnZ="<<nZ;
Mas_z[Tik]=nZ; //запоминаем кол-во вершин в графе зЮблА
cout<<"\t\t\tэтот комп пока ещё работает...\nRasnostY...\t\t\tПовторяю который раз?! Ответ: ";
for(int XXX=0;XXX<10;XXX++){ //цикл повторений
cout<<"\b"<<XXX; //Вывод количества повторений
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_x\tMas_y\tMas-z\tTikTak";
//for (int y = 0; y < Tik; y++)cout <<"\n"<<Mas_x[y]<<"\t"<< Mas_y[y]<<'\t'<<Mas_z[y]<<"\t"<<TikTak[y]<<" \t";
cout<<"\n\nесли вы видите эту надпись, значит эксперименты прошли удачно"
<<"\n\tPress any key для вывода результатов на экран."<<flush;
getch(); //Ждём нажатия любой клавиши
TimeOut(Tik,TikTak,Mas_x,Mas_y,Mas_z);//вызываем функцию общёта всего и вся
cout<<"\n\n\t\t Press Any Key for exit to you system."<<flush;//Вывод подсказки - "Что делать дальше"
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. |
В графе эксперимент я вывожу экспериментально время – время которое я получил при выполнение моей процедуры. В графе теория я вывожу значение времени получившееся при подстановке мультипликативных констант в исходное уравнение.