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

Поиск минимального гамильтонова цикла в матрице - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Составить новую строку из цифр, соответствующих данным буквам и отсортировать их по возростанию. http://www.cyberforum.ru/cpp-beginners/thread83831.html
Задача такая: даны цифры от 1 до 9 которые соответствуют каким-либо буквам от X до Y. С клавиатуры вводятся различные буквы. Далее должна появится строка состоящая из цифр соответсвующих буквам...
C++ Работа с мышью в с++ Заранее спасибо всем откликнувшимся! Подскажите ,пожалуйста, что надо для управления программой с помощью мыши. К примеру, если программа просто выводит слово "Выход" и при кликанье на нем... http://www.cyberforum.ru/cpp-beginners/thread83830.html
Заменить каждый элемент массива на среднее арифметическое его и его соседей слева и справа C++
Помогите пожалуйста. Нужно Объявить массив целых чисел и заполнить его случайными значениями. Размерность масссива: 100 Диапазон значений: -100-100 Что нужно сделать: Заменить каждый элемент на...
C++ Сформировать и вывести строку...
Дано целое число N (> 0) и символ С. Сформировать и вывести строку длины N, которая состоит из символов С.
C++ Перевод из 10СС в 2,8,16СС. http://www.cyberforum.ru/cpp-beginners/thread83819.html
Не знаю как написать программу на языке си по переводу любого вводимого целого числа в 10 сс(системе счисления) в любую другую 2,8 или 16.Заранее благодарна
C++ Считывание текста из файла (Visual studio) Написать программу, которая считывает текст из файла и выводит на экран только строки, не содержащие двузначных чисел. подробнее

Показать сообщение отдельно
Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62

Поиск минимального гамильтонова цикла в матрице - C++

09.01.2010, 01:06. Просмотров 410. Ответов 2
Метки (Все метки)

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
    #include <iostream>
    using namespace std;
    #define n 10
    int c[n] ; // номер хода, на котором посещается вершина
    int path[n]; // номера посещаемых вершин
    int v0=2; // начальная вершина
    //Матрица смежности
    int a[n][n]=
    {
 
            0,0,0,0,0,7,0,0,0,0,
 
            0,0,2,0,0,0,5,0,0,0,
 
            0,4,0,11,0,0,0,9,0,0,
 
            0,0,8,0,9,0,0,0,6,0,
 
            3,0,0,6,0,0,0,0,0,9,
 
            0,0,0,0,0,0,4,0,0,2,
 
            0,0,0,9,0,0,0,6,0,0,
 
            0,0,0,0,3,0,0,0,0,0,
 
            0,0,0,0,0,0,0,0,0,6,
 
            0,0,0,0,0,0,0,0,0,0
 
    };
    void prnt(void)
    {
        int p;
        for ( p = 0 ; p<n ; p++)
        printf("%d ", path[p] ) ;
        printf("%d ", path[0] ) ;
        printf("\n") ;
    }
    //подпрограмма нахождения гамильтонова цикла
    int gamilton ( int k)
    {
        int v,q1=0;
        for(v=0; v<n && !q1; v++)
        {
            if(a[v][path[k-1]]||a[path[k-1]][v])
            {
                if (k==n && v==v0 ) q1=1;
                else if (c[v]==-1)
                {
                    c[v] = k ; path[k]=v;
                    q1=gamilton (k+1) ;
                    if (!q1) c[v]=-1;
                } else continue;
            }
        } return q1;
    }
    int main()
    {
        setlocale (LC_ALL, "Russian");
    int j;
    printf("Гамильтонов цикл:\n");
    for(j=0;j<n;j++) c[j]=-1;
    path[0]=v0 ;
    c[v0]=v0;
    if(gamilton (1)) prnt(); else printf("Нет решений\n");
    system ("pause");
    }
Эта программа ищет гамельтонов цикл в матрице. Помогите сделать так чтобы прога искала минимальный гамельтонов цикл...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru