Автор: Пользователь скрыл имя, 03 Марта 2013 в 03:36, курсовая работа
При конструкторском проектировании ЭВС решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задания и максимально учитывающего возможности технологической базы производства. Тесная взаимосвязанность задач и большая размерность каждой из них обычно не позволяет предложить метод поиска конструктивного оптимального решения в едином цикле в связи с трудностями создания общей математической модели, комплексно учитывающей особенности конструкторско-технологической базы производства. Поэтому разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования: компоновки, размещения и трассировки,- до сих пор остаются актуальными проблемами, решение которых неотъемлемо связано с развитием систем автоматизации проектирования.
Введение…………………………………………………………… 3
1. Теоретическая часть
1.1 Алгоритмы компоновки……….…………………………..….. 4
1.2 Последовательный алгоритм компоновки ………………….. 5
1.3 Алгоритм компоновки……………………..………………….. 6
2. Практическая часть
2.1 Анализ задания………………………………………………… 8
2.2 Инструкция пользователя…..…….………………………….. 10
3. Заключение…………………………………………….….……… 14
4. Список используемой литературы……………………….….… 15
5. Приложение
5.1 Листинг программы………………………………………….... 16
5.2 Ручной счет…………………………………………………….. 31
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
/*----------------------------
typedef struct
{
int *m;
int c;
} ms;
/*----------------------------
typedef struct
{
int **m;
int c;
} matr;
/*----------------------------
int mr_inp(int *c, int ***ms);
int mr_2pr(int c, int **ms);
mr_2pr2(int c, int **ms, ms *gn, int l);
int mr_sub(matr *mr, ms g);
int mr_cpy(matr mr, matr *cpmr);
int razb(matr mr, int l, ms q, ms *gn);
int add_ver(ms *g, int xi);
int sp_sm_vr(matr mr, ms g, ms *sm, ms q);
int smej_ver(matr mr, ms g, ms sm, int *xs);
int rez(ms *gn, int l);
int ms_inp(ms *q);
int ms_pr(ms q);
/*----------------------------
/*****************************
/* Главная функция */
/*****************************
main()
{
int i;
matr mr;
ms q;
int l;
ms *gn;
char s;
/*---------------------------*
clrscr();
/*---------------------------*
/* Ввод матрицы */
/*---------------------------*
if(mr_inp(&mr.c, &mr.m) == 1)
{ printf("\n^Error: mr_inp return 1!");
getch(); return; }
/*---------------------------*
printf("\nЗаданная матрица смежности:");
mr_2pr(mr.c, mr.m);
/*----------------------------
/* Ввод вектора запрещенных вершин */
/*----------------------------
if(ms_inp(&q) == 1)
{ printf("\n^Error: ms_inp return 1!");
getch(); return; }
/*---------------------------*
printf("\nВектор запрещенных вершин:\n");
ms_pr(q);
/*---------------------------*
gn=(ms*)calloc(l, sizeof(ms));
if(gn == NULL)
{ printf("\nError: gn == NULL !");
getch(); return; }
/*---------------------------*
getch();
l=q.c;
if(razb(mr, l, q, gn) == 1)
{ printf("\n^Error: razb return 1!");
getch(); return; }
/*---------------------------*
/* Вывод результата */
/*---------------------------*
rez(gn, l);
/*---------------------------*
/* Освобождение памяти */
/*---------------------------*
for(i=0; i < mr.c; i++)
{
if(mr.m[i] == NULL)
{ printf("\nError: mr.m[%d] == NULL !", i);
getch(); return; }
free(mr.m[i]);
}
/*---------------------------*
if(mr.m == NULL)
{ printf("\nError: mr.m == NULL !");
getch(); return; }
free(mr.m);
/*+++++++++++++++++++++++++++*
if(q.m == NULL)
{ printf("\nError: q.m == NULL !");
getch(); return; }
free(q.m);
q.c=0;
/*+++++++++++++++++++++++++++*
for(i=0; i < l; i++)
{
if(gn[i].m == NULL)
{ printf("\nError: gn[%d].m == NULL !", i);
getch(); return; }
free(gn[i].m);
}
/*---------------------------*
if(gn == NULL)
{ printf("\nError: gn == NULL !");
getch(); return; }
free(gn);
/*---------------------------*
getch();
return;
}
/*****************************
/* Ввод матрицы в память */
/*****************************
int mr_inp(int *c, int ***ms)
{
int i,
j;
/*---------------------------*
printf("\nВведите количество вершин графа и нажмите <Enter>: ");
scanf("%d", c);
/*---------------------------*
(*ms)=(int**)calloc((*c), sizeof(int*));
if(ms == NULL)
{ printf("\nError: ms == NULL !");
getch(); return 1; }
/*---------------------------*
printf("\nВведите дуги матрицы. После каждой нажмите <Enter>:\n");
for(i=0; i < (*c); i++)
{
(*ms)[i]=(int*)calloc((*c), sizeof(int));
if((*ms)[i] == NULL)
{
printf("\nError: (*ms)[i] == NULL !", i);
getch();
return 1;
}
/*-------------------------*/
for(j=0; j < (*c); j++)
{
printf("[%d][%d]= ", (i+1), (j+1));
scanf("%d", &(*ms)[i][j]);
}
/*-------------------------*/
}
/*---------------------------*
return 0;
}
/*****************************
/* Ввод списка запрещенных вершин */
/*****************************
int ms_inp(ms *q)
{
int i;
/*---------------------------*
printf("\nВведите количество запрещенных вершин (кусков графа) и нажмите <Enter>: ");
scanf("%d", &(*q).c);
/*---------------------------*
(*q).m=(int*)calloc((*q).c, sizeof(int));
if((*q).m == NULL)
{ printf("\nError: (*q).m == NULL !");
getch(); return 1; }
/*---------------------------*
printf("\nВведите запрещенные вершины. После каждой нажмите <Enter>:\n");
for(i=0; i < (*q).c; i++)
{
printf("[%d]= ", (i+1));
scanf("%d", &(*q).m[i]);
}
/*---------------------------*
return 0;
}
/*****************************
/* Вывод матрицы на экран */
/*****************************
mr_2pr(int c, int **ms)
{
int i,
j;
/*---------------------------*
printf("\n |");
for(j=0; j < c; j++)
{
printf(" %2d", (j+1));
}
/*---------------------------*
printf("\n");
for(j=0; j < (c+1); j++)
{
printf("---");
}
/*---------------------------*
for(i=0; i < c; i++)
{
printf("\n%2d|", (i+1));
for(j=0; j < c; j++)
{
printf(" %2d", ms[i][j]);
}
}
/*---------------------------*
return 0;
}
/*****************************
/* Вывод матрицы без вычеркнутых вершин */
/*****************************
mr_2pr2(int c, int **ms, ms *gn, int l)
{
int i,
j,
k,
n,
m;
short pr, pr2;
/*---------------------------*
printf("\n |");
m=0;
for(j=0; j < c; j++)
{
pr=0;
for(k=0; k < l; k++)
for(n=0; n < gn[k].c; n++)
{
if((j+1) == gn[k].m[n])
{
pr=1;
}
}
if(pr == 0)
{
printf(" %2d", (j+1));
m++;
}
}
/*---------------------------*
printf("\n");
for(j=0; j < (m+1); j++)
{
printf("---");
}
/*---------------------------*
for(i=0; i < c; i++)
{
pr=0;
for(k=0; k < l; k++)
for(n=0; n < gn[k].c; n++)
{
if((i+1) == gn[k].m[n])
{
pr=1;
}
}
if(pr == 0)
{
printf("\n%2d|", (i+1));
for(j=0; j < c; j++)
{
pr2=0;
for(k=0; k < l; k++)
for(n=0; n < gn[k].c; n++)
{
if((j+1) == gn[k].m[n])
{
pr2=1;
}
}
if(pr2 == 0)
{
printf(" %2d", ms[i][j]);
}
}
}
}
/*---------------------------*
return 0;
}
/*****************************
/* Функция выбора смежной
/*****************************
int smej_ver(matr mr, ms g, ms sm, int *xs)
{
int i,
j,
k;
int b,
minsg,
imaxro;
ms ro,
sigma;
/*---------------------------*
if((g.m == NULL) || (g.c == 0))
{ printf("\nError: (g.m == NULL) || (g.c == 0) !");
getch(); return 1; }
/*---------------------------*
sigma.c=sm.c;
sigma.m=(int*)calloc(sigma.c, sizeof(int));
if(sigma.m == NULL)
{ printf("\nError: sigma.m == NULL !");
getch(); return 1; }
/*---------------------------*
ro.c=sm.c;
ro.m=(int*)calloc(ro.c, sizeof(int));
if(ro.m == NULL)
{ printf("\nError: ro.m == NULL !");
getch(); return 1; }
for(i=0; i < sm.c; i++)
{
/*----------------------------
/* Определение локальной степени вершины */
/*----------------------------
ro.m[i]=0;
for(j=0; j < mr.c; j++)
{
if(mr.m[j][(sm.m[i]-1)] == 1)
{
ro.m[i]++;
}
}
/*----------------------------
/* Определение числа ребер, соединяющих */
/* вершину xi с вершинами xj, вошедшими в g*/
/*----------------------------
b=0;
for(j=0; j < g.c; j++)
{
if(mr.m[(sm.m[i]-1)][(g.m[j]-
{
b++;
}
}
/*----------------------------
/* Определение относительного веса вершины */
/*----------------------------
sigma.m[i]=ro.m[i]-b;
}
/*----------------------------
/* Выбор вершины с минимальным относительным весом */
/*----------------------------
minsg=sigma.m[0];
imaxro=0;
for(i=0; i < sigma.c; i++)
{
if(sigma.m[i] < minsg)
{
minsg=sigma.m[i];
imaxro=i;
}
}
/*----------------------------
/* Выбор вершины с большей локальной степенью */
/*----------------------------
for(i=0; i < sm.c; i++)
{
if(sigma.m[i] == minsg)
{
if(ro.m[i] > ro.m[imaxro])
{
imaxro=i;
}
}
}
/*----------------------------
(*xs)=sm.m[imaxro];
/*----------------------------
return 0;
}
/*****************************
/* Функция разбиения графа */
/*****************************
int razb(matr mr, int l, ms q, ms *gn)
{
int i, j, k, h;
int n;
int xs;
ms sm;
matr cpmr;
short pr;
/*----------------------------
/* Проверка матрицы на
/*----------------------------
pr=0;
for(i=0; i < mr.c; i++)
{
for(j=0; j < mr.c; j++)
{
if(mr.m[i][j] != mr.m[j][i])
{
pr=1;
break;
}
}
if(pr == 1)
{
printf("\nМатрица не симметрична!");
getch();
return 1;
}
}
/*----------------------------
/* Проверка на кратность
/*----------------------------
if((mr.c%l) != 0)
{
printf("\nВходные данные ведены неправильно!");
printf("\nРазмерность матрицы должна быть кратна количеству запрещенных вершин.");
getch();
return 1;
}
/*----------------------------
n=(mr.c)/l;
if(mr_cpy(mr, &cpmr) == 1)
{ printf("\nError: cpmr return 1 !");
getch(); return 1; }
/*---------------------------*
for(i=0; i < l; i++)
{
/*-------------------------*/
gn[i].m=NULL;
gn[i].c=0;
/*-------------------------*/
clrscr();
/*-------------------------*/
printf("\nЭтап N%d", (i+1));
/*--------------------------*/
printf("\nИсходная матрица:");
mr_2pr2(cpmr.c, cpmr.m, gn, l);
/*--------------------------*/
printf("\nНомер запрещенной вершины= %d", q.m[i]);
/*-------------------------*/
if((i+1) == l)
{
printf("\nПоследний фрагмент графа формируется ");
printf("\nиз оставшихся вершин автоматически:");
/*-----------------------*/
if(add_ver(&(gn[i]), q.m[i]) == 1)
{ printf("\n^Error: add_ver return 1!");
getch(); return 1; }
/*-----------------------*/
for(j=0; j < cpmr.c; j++)
{
pr=0;
for(k=0; k < l; k++)
for(h=0; h < gn[k].c; h++)
{
if((j+1) == gn[k].m[h])
{
pr=1;
}
}
if(pr == 0)
{
if(add_ver(&(gn[i]), (j+1)) == 1)
{ printf("\n^Error: add_ver return 1!");
getch(); return 1; }
/*-------------------------*/
if(mr_sub(&cpmr, gn[i]) == 1)
{ printf("\n^Error: mr_sub return 1!");
getch(); return 1; }
}
}
printf("\nG%d: ", (i+1));
ms_pr(gn[i]);
getch();
/*-------------------------*/
return 0;
}
/*---------------------------*
if(add_ver(&(gn[i]), q.m[i]) == 1)
{ printf("\n^Error: add_ver return 1!");
getch(); return 1; }
/*-------------------------*/
do
{
sm.m=NULL;
sm.c=0;
/*-------------------------*/
if(sp_sm_vr(cpmr, gn[i], &sm, q) == 1)
{ printf("\n^Error: sp_sm_vr return 1!");
getch(); return 1; }
/*-------------------------*/
smej_ver(cpmr, gn[i], sm, &xs);
/*-------------------------*/
if(add_ver(&(gn[i]), xs) == 1)
{ printf("\n^Error: add_ver return 1!");
getch(); return 1; }
}
while(gn[i].c < n);
/*---------------------------*
if(mr_sub(&cpmr, gn[i]) == 1)
{ printf("\n^Error: mr_sub return 1!");
getch(); return 1; }
/*---------------------------*
if(sm.m == NULL)
{ printf("\nError: sm.m == NULL !");
getch(); return 1; }
free(sm.m);
sm.c=0;
/*---------------------------*
printf("\nG%d: ", (i+1));
ms_pr(gn[i]);
/*---------------------------*
getch();
}
/*----------------------------
for(i=0; i < mr.c; i++)
{
if(cpmr.m[i] == NULL)
{ printf("\nError: cpmr.m[%d] == NULL !", i);
getch(); return 1; }
free(cpmr.m[i]);
}
/*----------------------------
if(cpmr.m == NULL)
{ printf("\nError: cpmr.m == NULL !");
getch(); return 1; }
free(cpmr.m);
/*----------------------------
return 0;
}
/*****************************
/* Функция удаления (заполнения нулями) */
/* заданых строк и столбцов */
/*****************************
int mr_sub(matr *mr, ms g)
{
int i,
j,
k,
c;
/*---------------------------*
if((*mr).m == NULL)
{ printf("\nError: (*mr).m == NULL !");
getch(); return 1; }
/*---------------------------*
if(g.m == NULL)
{ printf("\nError: g.m == NULL !");
getch(); return 1; }
/*---------------------------*
for(i=0; i < (*mr).c; i++)
{
for(j=0; j < (*mr).c; j++)
{
for(k=0; k < g.c; k++)
{
if(((i+1) == g.m[k]) || ((j+1) == g.m[k]))
{
(*mr).m[i][j]=0;
}
}
}
}
/*---------------------------*
return 0;
}
/*****************************
/* Функция вывода кусков */
/*****************************
int rez(ms *gn, int l)
{
int i;
/*---------------------------*
clrscr();
/*---------------------------*
printf("\nКуски графа:");
/*---------------------------*
for(i=0; i < l; i++)
{
printf("\nG%d: ", (i+1));
ms_pr(gn[i]);
}
/*---------------------------*
return 0;
}
/*****************************
/*****************************
int mr_cpy(matr mr, matr *cpmr)
{
int i,
j;
/*----------------------------
if(mr.m == NULL)
{ printf("\nError: mr.m == NULL !");
getch(); return 1; }
/*----------------------------
(*cpmr).c=mr.c;
(*cpmr).m=(int**)calloc((*
if((*cpmr).m == NULL)
{ printf("\nError: (*cpmr).m == NULL !");
getch(); return 1; }
/*----------------------------
for(i=0; i < (*cpmr).c; i++)
{
(*cpmr).m[i]=(int*)calloc((*
if((*cpmr).m[i] == NULL)
{
printf("\nError: (*cpmr).m[i] == NULL !", i);
getch();
return 1;
}
/*--------------------------*/
for(j=0; j < (*cpmr).c; j++)
{
(*cpmr).m[i][j]=mr.m[i][j];
}
}
/*----------------------------
return 0;
}
/*****************************
/* Функция формирования списка */
/* смежных вершин */
/*****************************
int sp_sm_vr(matr mr, ms g, ms *sm, ms q)
{
int i, j, k, r;
short pr;
ms tp;
/*---------------------------*
if(((*sm).m != NULL) || ((*sm).c != 0))
{ printf("\nError: ((*sm).m != NULL) || ((*sm).c != 0)");
Информация о работе Последовательный алгоритм компоновки с равными числу вершин в каждом куске