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

Графы. Нахождение максимального пути - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Prefix http://www.cyberforum.ru/cpp-beginners/thread569552.html
Здраствуйте! Пишу чит для Cs 1.6 на С++. Нужно чтоб в файле prefix.ini Хранился префикс функций в чите т.есть есть функия : speed = g_pEngine->pfnRegisterVariable( "Тут префикс которный хранится и...
C++ Строки. Определить минимальное количество первых символов, по которым можно различать слова с заданного текста. Задача. Определить минимальное количество первых символов, по которым можно различать слова с заданного текста. Направьте, пожалуйста, куда копать. http://www.cyberforum.ru/cpp-beginners/thread569546.html
C++ Перевод char массива в int массив
Делаю так: int inmas; char outmas; fgets(outmas,40,write); outmas2=atoi(outmas); Пишет что типы несовместимы.
удалить элементы между минимумом и максимумом в двусвязном списке C++
Дан шаблон класса для работы с двунаправленным некольцевым списком. В шаблоне реализовала следующие действия: добавление звена в начало списка; удаление звена из начала списка; добавление...
C++ Написать программы на одномерные и двумерные массивы http://www.cyberforum.ru/cpp-beginners/thread569522.html
1.Дан одномерный массив. Найти элементы, имеющие в своей записи только чётные цифры. Сформировать новый массив из элементов с чётными цифрами и указать индекс максимального элемента. Использовать...
C++ isaplha Ввести с клавиатуры строку символов. Признак окончания ввода строки – нажатие клавиши "Ввод". Программа должна определить длину введенной строки L, и, если длина L=10, то удаляются все A...Z. ... подробнее

Показать сообщение отдельно
El HaZaRD
0 / 0 / 0
Регистрация: 08.02.2012
Сообщений: 27
10.05.2012, 20:33  [ТС]
Появилась идея реализации.
Так как для меня главное найти только правильный порядок следования столбцов друг за другом, то пришла в голову следующая мысль.
Берем за точку отсчета столбец 1.
Веса переходов из столбца 1 в остальные 3 столбца указан в первой строке массива per[4][4].
Делаем цикл.
Берем первую строку и ищем в ней максимальный элемент. Найдя его запоминаем номер его столбца (обозначим его stnum).
Номеру следующей строки для поиска максимума присваиваем значение stnum.
Затем обнуляем весь столбец с номером stnum. Таким образом мы исключим возможность перехода в этот столбец (нам ведь надо во все по одному разу зайти).
И далее опять ищем максимум в следующей строке.

Для того чтобы запомнить маршрут нам надо будет куда то записывать все значения stnum по порядку, а первым значением в этом списке будет 0 (или 1, т.к. первый столбец).

Помогите, пожалуйста, кто-нибудь воплотить это в коде.

Добавлено через 24 минуты
Сам вопрос задал, сам на него и ответил =)

Для удобства была создана функция для поиска максимума в одномерном массиве, куда будет передаваться строка из таблицы переходов.

C++
1
2
3
4
5
6
7
8
9
int maximum(int mass[4])
{
    int maxx=0;
        for (int j=0;j<4;j++)
        {
            if (mass[j]>maxx) maxx=mass[j];
        }
    return maxx;
}
А вот так я реализовал само решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//ищем маршрут
    i=0;
    int ans[4]={0,0,0,0};
    for(int k=0;k<3;k++)
    {
        for (j=0;j<4;j++)
        {
            if (maximum(per[i])==per[i][j]) ans[k+1]=j;
        }
        i=ans[k+1];
        for(j=0;j<4;j++)
        {
            per[j][i]=0;
        }
    }
 
    cout<<endl<<"Путь: ";
    for (j=0;j<4;j++)
    {
        cout<<ans[j]+1<<" ";
    }
Добавлено через 12 минут
Небольшой косячек.. забыл обнулить первый столбец в массиве переходов после того, как i=0.

Получится в итоге так:

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
//ищем маршрут
    i=0;
    for(j=0;j<4;j++)
    {
        per[j][i]=0;
    }
    int ans[4]={0,0,0,0};
    for(int k=0;k<3;k++)
    {
        for (j=0;j<4;j++)
        {
            if (maximum(per[i])==per[i][j]) ans[k+1]=j;
        }
        i=ans[k+1];
        for(j=0;j<4;j++)
        {
            per[j][i]=0;
        }
    }
 
    cout<<endl<<"Путь: ";
    for (j=0;j<4;j++)
    {
        cout<<ans[j]+1<<" ";
    }
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru