Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Курсач "Алгоритм Ершова" - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ invalid floating point operation http://www.cyberforum.ru/cpp/thread194559.html
помогите решить вот такую вот задачу: Коэффициенты системы линейных уравнений заданы в виде квадратной матрицы. С помощью допустимых преобразований привести матрицу к треугольному виду. Найти...
C++ надо скачать киньте плиз нормальную ссылку от куда можно скачать С++ http://www.cyberforum.ru/cpp/thread194359.html
C++ время запуска/конца выполнения программы с точностью до миллисекунд
С. как сделать чтобы в начале программы выводилась дата и время с миллисекундами и тоже самое при её завершении?
C++ Использование указателя на метод вместо виртуального метода
Имеется базовый класс Base. Имеется производный от Base класс Derived. В классе Derived требуется выполнить некоторое действие, которое практически полностью эквивалентно для любого производного от...
C++ Компилятор http://www.cyberforum.ru/cpp/thread193991.html
Здравствуйте. Пишу компилятор pas->asm на с++ Может кто-то подскажет генератор конструкцый или что-то подобное: <переменная1>+<переменная2> mov...
C++ Дан файл F, содержащий координаты множества точек на плоскости. Переписать в файл G попарно точки, через которые проходят медианы этого множества. Помогите плз. Дан файл F, содержащий координаты множества точек на плоскости. Переписать в файл G попарно точки, через которые проходят медианы этого множества. Медианой множества, состоящего... подробнее

Показать сообщение отдельно
marselo_io_off
2 / 2 / 0
Регистрация: 12.02.2010
Сообщений: 53

Курсач "Алгоритм Ершова" - C++

21.11.2010, 14:58. Просмотров 699. Ответов 1
Метки (Все метки)

Вот, что-то написал такое, естественно позаимствовал куски кода, работает... НО! получается алгоритм раскраски путем перебора вершин! а мне надо алгоритмом Ершова. если надо будет уяснить, что это за алгоритм, то можно написать, а пока вот.. кто знает, подскажите, как его реализовать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <conio.h>
using namespace std;
 
struct graf{
int stepeni;
int color;
int number;
};
 
 
void VyvodGrafa(graf arr[22],int n);
int ProverkaCvetov(graf arr[22],int n);
void InicializaciaGrafa(graf arr[22],int n);
 
int main()
{ 
 int color1[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}; 
 struct graf arr[22]; 
 const int n(9);
 int i, j;
 int m[n][n]= {0, 1, 1, 1, 0, 0, 0, 1, 0,
                 1, 0, 0, 1, 1, 0, 0, 0, 1,
                 1, 0, 0, 1, 0, 1, 0, 0, 0,
                 1, 1, 1, 0, 1, 1, 1, 1, 1,
                 0, 1, 0, 1, 0, 0, 1, 0, 0,
                 0, 0, 1, 1, 0, 0, 0, 1, 0,
                 0, 0, 0, 1, 1, 0, 0, 0, 1,
                 1, 0, 0, 1, 0, 1, 0, 0, 1,
                 0, 1, 0, 1, 0, 0, 1, 1, 0};
for(i = 0; i < n; i++,cout<<endl)
      for(j = 0; j < n; j++)
            cout<<m[i][j]<<' ';                                                                                            
  
int versh=0,z;  
InicializaciaGrafa(arr,n);//Цвета по умолчанию
 
//Находим степени вершин
for(int i=0; i < n; i++,versh++)
     {
       arr[versh].stepeni=0;  
       arr[versh].number=i;
     for(int j=0; j < n; j++)
       if( m[i][j] == 1 )
         arr[versh].stepeni++;
     }
      
//Алгоритм присвоения счетов
int x=0,t,st,flag=0,metk=0,s;
for(x=0; ProverkaCvetov(arr,n)!=0 ; x++) //Цикл по цветам
 {   
   if(arr[x].color == 66) arr[x].color = color1[x];   //Присваиваем первый цвет 
     for(i=0; i < n; i++) //Цикл, который красит несмежную вершину
       {      
         t=arr[i].number; //Номер строки матрицы смежности
         flag=0;          
         for(j=0; j < n; j++)    //Идем в строку матрицы смежности 
         {
           if((m[t][j] == 1 && t!=j))  //Если вершина несмежна с данной вершиной
            {
               for(s=0; s < n; s++)
               m[t][j]+=m[t][j];  
                if(j == arr[s].number && arr[s].color != color1[x] )
                  {
                    flag++;
                       }
             }     
           if( arr[j].number == t ) metk=j;          
           if(flag==arr[metk].stepeni && arr[metk].color == 66 )   
             arr[metk].color = color1[x];   
          }
       }
               cout<<endl;
  }   
VyvodGrafa(arr,n); 
getch();
return 0;
}
 
 
//инициализируем все цвета в структуре
void InicializaciaGrafa(graf arr[22],int n)
{
         for(int s=0;s < n; s++)
         {
           arr[s].color=66;
         }
} 
 
 
//вывод результатов
void VyvodGrafa(graf arr[22],int n)
{
         for(int s=0;s < n; s++)
         {
           cout<<arr[s].number<<"-"<<arr[s].stepeni<<"-"<<arr[s].color<<endl;
         }
} 
 
//возвращает 0, если все цвета уже присвоены
int ProverkaCvetov(graf arr[22],int n) 
{
  int flag2=0;  
  for(int xx=0; xx < n; xx++) //проверяем, все ли цвета присвоены
  {
   if(arr[xx].color <= 16)
   ++flag2;
      }
   if(flag2==n) return 0;
   else return 1;   
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru