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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
El HaZaRD
0 / 0 / 0
Регистрация: 08.02.2012
Сообщений: 27
#1

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

09.05.2012, 18:18. Просмотров 1868. Ответов 1
Метки нет (Все метки)

Добрый день.
Пытаюсь написать программу для помощи в криптоанализе методом двойной перестановки и столкнулся с проблемой. Изложу суть задачи:
Перехвачено сообщение АЗЮЖЕ_СШГТООИПЕР
16 символов, загоняем в матрицу 4х4.
Получилось 4 столбца, переставленных в неизвестном порядке:
А З Ю Ж
Е _ С Ш
Г Т О О
И П Е Р

Метод «вскрытия» шифров двойной перестановки основан на определении маловероятных сочетаний букв и нахождении на их основе истинной последовательности столбцов в шифровальной таблице.

При решении получаем матрицу из сумм логарифмов сочетаний:

0 21 30 27
23 0 26 24
19 22 0 20
28 17 14 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
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
112
#include <iostream>
#include <locale.h>
#include <stdio.h>
#include <fstream>
#include <string.h>
using namespace std;
 
void Rus(char* in, char* out)
{
    int len = strlen(in);
    for(int i = 0; i < len; i++)
    {
        unsigned char simb = (*in);
        if((simb>=128)&&(simb<=175))
            simb += 64;
        else
        if((simb>=224)&&(simb<=239))
            simb += 16;
        *out = simb;
        out++;
        in++;
    }
}
 
void main()
{
setlocale(LC_ALL,"Russian");
int i,j,num[4][4],per[4][4];
char mas[4][4],head[33];
int log[33][33];
 
 
 
 
    cout<<"введите сообщение:"<<endl;
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            cin>>mas[i][j];
        }
        Rus(mas[i],mas[i]);
    }
    
 
    cout<<endl<<"получилась таблица:"<<endl;
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            cout<<mas[i][j]<<" ";
        }
        cout<<endl;
    }
 
//считываем таблицу логарифмов
    ifstream f("nums.txt");
    for(i=0;i<33;i++) 
    {
        for(j=0;j<33;j++) 
        {
            f>>log[i][j];
        }
    }
    ifstream e("head.txt");
    for(i=0;i<33;i++) 
        {
            e>>head[i];
        }
//получаем таблицу из указателей на строки и столбцы в таблице логарифмов
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            for (int k=0;k<33;k++)
            {
                if (strncmp(&mas[i][j],&head[k],1)==0) num[i][j]=k;
            }
        }
    }
//получаем таблицу переходов
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            per[i][j]=0;
            if (i!=j) 
            {   
                for (int k=0;k<4;k++)
                {
                    per[i][j]=per[i][j]+log[num[k][i]][num[k][j]];
                }
            }
        }
    }
 
cout<<endl<<"получилась таблица переходов:"<<endl;
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            cout<<per[i][j]<<" ";
        }
        cout<<endl;
    }
 
//ищем маршрут
    
 
cout<<endl<<endl;
system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2012, 18:18     Графы. Нахождение максимального пути
Посмотрите здесь:

Нахождение критического пути C++
Нахождение кратчайшего пути от одной вершины графа до другой C++
Нахождение эйлерова пути C++
нахождение времени, потраченного на прохождение путником половины пути C++
C++ Нахождение максимального елемента..
C++ Графы,исключение из пути определённых вершины
Нахождение пути от одной ячейки к другой в массиве C++
C++ Нахождение кратчайшего пути, поиск с возвратом
C++ Графы, нахождение наименьшего пути между вершинами обходом в ширину
C++ Нахождение максимального элемента
C++ Нахождение кратчайшего пути
C++ Нахождение пути к папке с файлом

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
El HaZaRD
0 / 0 / 0
Регистрация: 08.02.2012
Сообщений: 27
10.05.2012, 20:33  [ТС]     Графы. Нахождение максимального пути #2
Появилась идея реализации.
Так как для меня главное найти только правильный порядок следования столбцов друг за другом, то пришла в голову следующая мысль.
Берем за точку отсчета столбец 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<<" ";
    }
Yandex
Объявления
10.05.2012, 20:33     Графы. Нахождение максимального пути
Ответ Создать тему
Опции темы

Текущее время: 10:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru