Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Нужны исходники программы по нахождению гамильтонов циклов  (Прочитано 5842 раз)
0 Пользователей и 1 Гость смотрят эту тему.
антонха
Гость
« : 22-03-2004 10:10 » 

Нужны исходники программы по нахождению гамильтонов циклов
Записан
stragner
Гость
« Ответ #1 : 22-03-2004 13:14 » 

антонха, насколько мне известно, не существует эффективного алгоритма по нахождению гамильтоновых циклов, так что надо решать в лоб - полным перебором. Исходники под рукой нет, да к тому же неизвестно, на каком языке вам они нужны, может на FORTRAN'e :twisted:
Записан
антонха
Гость
« Ответ #2 : 22-03-2004 19:31 » 

stragner, Мне нужны они на С++, можете мне помочь? Отлично
Записан
stragner
Гость
« Ответ #3 : 23-03-2004 06:10 » 

вот примерная программа, для построения гамильтонова цикла:

Цитата

#define MAXN 1000

int matrix[MAXN][MAXN]; //Матрица смежности - должна быть симметричная
bool flag[MAXN];      //Использованные вершины
int stack[MAXN];
int n;

void Solve(int ver, int num)
{
   if (num == n && matrix[ver][stack[0]] == 1) {
      //Печать цикла. Например так...
      for (int i = 0; i < n; i++)
         cout << stack+1 << ' ';
      cout << endl;
   }

   for (int i = 0; i < n; i++)
      if (i != ver && !flag && matrix[ver])
      {
         stack[num] = i;
         flag = true;
         Solve(i, num + 1);
         flag = false;
      }
}

int main()
{
   //ввод матрицы
   EnterToMatrix();
//Строем цикл для первой вершины
   flag[0] = true;
   stack[0] = 1;
   Solve(1, 1);
}

Записан
антонха
Гость
« Ответ #4 : 23-03-2004 22:59 » 

Спасибо за код , буду разбираться
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines