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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
#1

Эйлеров путь - C++

10.12.2013, 23:08. Просмотров 1448. Ответов 18
Метки нет (Все метки)

Я примерно написал програму, но мой вариант работает долго - 28(иногда меньше, иногда больше) минут.Подскажите пожалуйста есть ли какой-то более быстрый вариант. У меня есть только 5 минут каждый раз.
Мой заключается в следующем - берем одну из 10000 вершин ну и начинаем искать, подходит-добавили-опять ищем-нашли-добавали ну и если ничего не осталось то вывели.
Но работает долго.
К сожалению графы и алгоритмы на них еще не изучал - подскажите пожалуйста какой-либо алгоритм который будет быстрее. Можно не пример, а типа блок-схемы

Добавлено через 22 минуты
C другой стороны при использовании 3 i7 и 1 i3 расписав точки начала проверок как 0, 2500, 5000, 7500 можно конечно упеть за 3-4 минуты в среднем, но я верю что есть более цивилизованные пути решения
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2013, 23:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Эйлеров путь (C++):

Эйлеров цикл - C++
Есть программа: def euler_circuit(G): EP= # Эйлеров цикл - массив вершин. #возвращает локальный замкнутый цикл ...

Путь - C++
Помогите, плиз, с кодом для функции выбирающей из всех возможных путей от точки до точки кратчайший.Карта(задачка про лабиринт) это...

путь к файлу - C++
String x,n,v; x=Form1->Memo2->Text; // имя файла n= Form1->Memo1->Text; // имя папки v=".txt"; // разрешение файла...

Путь символа - C++
Здорова господа! Есть интересная задачка: "Проследите путь символа в вашей системе от клавиатуры до экрана на примере следующего...

Нужный путь - C++
Доброй ночи, форумчане! Я программист ранга начинающего. Подскажите пожалуйста, что можно закодить, чтобы зависнуть в проецировании кода на...

Путь к файлу - C++
Как сделать чтоб пользователь указывал путь к файлу который используеться дл читения?

18
Байт
Эксперт C
16541 / 10811 / 1638
Регистрация: 24.12.2010
Сообщений: 20,847
10.12.2013, 23:11 #2
В качестве начальной и конечной вершины можно рассматривать только вершины нечетных степеней. Их должно быть ровно 2, иначе эйлерова пути (не замкнутого) нет.
Если все вершины имеют четную степень, то имеется (обязательно!) эйлеров цикл (замкнутый путь). И тогда без разницы с какой из вершин начинать..
2
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
10.12.2013, 23:20  [ТС] #3
Тут, к сожалению, не так я задал вопрос.
Те изначально известно что нечетных вершин 2 - не ноль - то есть не цикл, а именно путь - но на входе у меня 10000 строк и как определить нечетную я не пойму, хотя пока пишу это уже пару идей пришло.
Спасибо
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 09:47 #4
Цитата Сообщение от Aliru Посмотреть сообщение
28(иногда меньше, иногда больше) минут
жесть!
сие творение ищет эйлеров путь за N*logN (можно избавиться от логарифма если set заменить на что-нибудь на хешах, например unordered_map):
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
#include <cstdio>
#include <set>
#include <stack>
using namespace std;
 
const int N = 10001;
 
set< int > adj[ N ]; // граф на списках смежности
stack< int > st;
 
void insert_edge( int v, int w )
{
    adj[ v ].insert( w );
    adj[ w ].insert( v );
}
 
void remove_edge( int v, int w )
{
    adj[ v ].erase( w );
    adj[ w ].erase( v );
}
 
int traverse( int v )
{
    for ( set< int >::iterator it; ( it = adj[ v ].begin() ) != adj[ v ].end(); v = *it )
    {
        st.push( v );
        remove_edge( v, *it );
    }
    return v;
}
 
void print_euler( int v )
{
    st.push( v = traverse( v ) );
    while ( !st.empty() )
    {
        printf( "%d ", v = st.top() ); st.pop();
        traverse( v );
    }
}
 
int find_odd_degree()
{
    for ( int v = 0; v < N; ++v )
        if ( adj[ v ].size() & 0x01 )
            return v;
    return -1;
}
 
int main()
{
    for ( int v, w; 1 < scanf( "%d%d", &v, &w ); insert_edge( v, w ) );
    print_euler( find_odd_degree() );
 
    return 0;
}
0
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:05  [ТС] #5
Сейчас я дописал поиск нечетной вершины.
На входе у меня 260-280Кб строк
такого типа(на самом деле они по-моему по 25 или 30 символов но это не важно)
ATGCG
GCATG
CATGC
AGGCA
GGCAT
Ответ типа такой(отсортирован по алфавиту)
AGGCA -> GGCAT
CATGC -> ATGCG
GCATG -> CATGC
GGCAT -> GCATG
Все одинаковой длины.
Нечетное ребро - это когда первые (размер() -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
112
113
114
115
// OGP2.0.cpp : Defines the entry point for the console application.
//
 
// Overlap Graph Problem.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include "conio.h"
#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include <algorithm>
#include <iterator>
#include "vector"
 
using namespace std;
 
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    list<string> Lines;
    list<string>::iterator it;
    vector <string> lines;
    string s1, s2, example;
    ifstream Fin;
    Fin.open("d:\\dataset_52_7.txt");
    if (!Fin.is_open())
    {
        cout << "Can't open file-d:\\dataset_52_7.txt" << endl;
        exit(EXIT_FAILURE);
    }
    while (Fin.good())
    {
      getline(Fin, s1);
      Lines.push_back(s1);
      s1.clear();
    }
    if (Fin.eof())
        cout << "EOF" << endl;
    else 
        if (Fin.fail())
        cout << "Fuck a duck, HAX!!!" << endl;
    else
        cout << "!!!---!!!" << endl;
    Fin.close();
    //End of input
 
    
    //Lines.sort();
    for ( it = Lines.begin(); it != Lines.end(); it++)
        lines.push_back(*it);
    //sort & send dna to the vector
 
    int count = 0;
    for (int i = 0; i < lines.size(); i++)
    {
        s1 = lines.at(i);
        s1.erase(s1.begin() + s1.size() - 1);
        for (count = 0; count < lines.size(); count++)
        {
            example = lines.at(count);
            example.erase(example.begin());
            if (i != count)
            {
                if (s1 == example)
                    break;
            }
        }
        if (count == lines.size())
        {
            s1 = lines.at(i);
            break;
        }
    }
    //cout << s1;
    ofstream f_out("d:\\Result.txt", ios::app);
        if (!f_out) 
            {
                cout<<"Файл Result.txt невозможно открыть";
                exit(EXIT_FAILURE);
            }
        f_out << s1;
    while (lines.size() != 0)
    {
        example = s1;
        example.erase(example.begin());
        for (unsigned int i = 1; i < lines.size(); i++)
        {
            for (unsigned int j = 0; j < (s1.size() - 1); j++)
            {
                if (example.at(j) == lines.at(i).at(j))
                {
                    count++;
                }
            }
            if (count == example.size())
            {
                //f_out << s1 << " -> " << lines.at(i) << endl;
                //cout << s1 << " -> " << lines.at(i) << endl;
                s1.clear();
                s1 = lines.at(i);
                lines.erase(lines.begin() + i);
                break;
            }
            count = 0;
        }
        cout << lines.size();
        example.clear();
    }
    f_out.close();
    _getch();
    return 0;
}
Доходит до 4500 и потом не находит продолжения.
В чем может быть проблема?
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:10 #6
Цитата Сообщение от Aliru Посмотреть сообщение
ATGCG
GCATG
CATGC
AGGCA
GGCAT
можете поведать смысл этих строк
0
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:10  [ТС] #7
Ну это ДНК, вернее ее куски нарезанные по н штук
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:18 #8
а как из этих строк строится граф? что является узлом? буквы или что? и как определяются ребра? соседние буквы образуют ребро или что? можете поподробнее объяснить
0
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:34  [ТС] #9
Пусть длина строки н
(н-1) последних символов одной сторки это (н-1) первых символов другой строки.
Я там нашел строку и потом проверил ее у которой начальные н-1 символов не повторяются нигде кроме нее самой - значит это нечетная вершина. Есть еще одна но у нее последнии н-1 символов не повторяются.
2 нееных вершины - значит это эйлеров путь
И так мы выстраиваем этот путь - ну типа
AACACTT->ACACTTG
CACTTGT->ACTTGTA
CTTGTAA->TTGTAAG
Ну вот так

Добавлено через 6 минут
Извиняюсь точнее так
AACACTT->ACACTTG
ACACTTG->CACTTGT
CACTTGT->ACTTGTA
ACTTGTA->CTTGTAA
CTTGTAA->TTGTAAG
Исправил
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:35 #10
я вас правильно понял: вам надо по кускам восстановить полную цепочку? и
Цитата Сообщение от Aliru Посмотреть сообщение
Я там нашел строку и потом проверил ее у которой начальные н-1 символов не повторяются нигде кроме нее самой - значит это нечетная вершина.
нечетная - значит начальная, а это
Цитата Сообщение от Aliru Посмотреть сообщение
Есть еще одна но у нее последнии н-1 символов не повторяются.
значит конечная вершина?
если так, то при чём здесь эйлеров путь, никак не уловлю?
0
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:38  [ТС] #11
да, но я думал это граф. я их еще не учил, но...
а о чем тогда задача, натолкнте на алгоритм пожалуйста
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 12:29 #12
продолжаем разговор
Цитата Сообщение от ya_noob Посмотреть сообщение
я вас правильно понял: вам надо по кускам восстановить полную цепочку?
я не услышал ответа. да или нет?
0
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 12:32  [ТС] #13
Да.
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 12:48 #14
хорошо. мне сложно запомнить ATGC, так что давайте далее будем говорить про ABCD.
итак, может ли во входных данных встретиться такое

AABC
ABCD
BCDD
CDDB
ABCD
BCDB
CDBA
DBAB
BABC
? попробуйте нарисовать эту цепочку
0
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 17:58  [ТС] #15
ТУТ есть AABC->ABCD->BCDD->CDDB и ABCD->BCDB->CDBA->DBAB->BABC
а у меня будет типа
Вход:
BCDD
DDBB
BBAB
DBBA
CDDB
AABC
ADCD
Выход
AABC->ABCD->BCDD->CDDB->DDBB->DBBA->BBAB
то есть AABC это начало так как комбинация AAB больше нигде не встеекается как последние 3 символа(н-1),
а вот ВСD - это начало BCDD И конец ABCD
я вот опять день думал периодически впринципе то мой код должен работать - но он доходит до 6311 отрезков и больше не находит
0
11.12.2013, 17:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 17:58
Привет! Вот еще темы с ответами:

Путь к файлу - C++
Добрый день форумчане! Хотелось бы узнать, как указывать путь к файлу выше по каталогу. Например: *****---folder---****** ...

путь к файлу - C++
ofstream fout; fout.open(&quot;file.txt&quot;) Так создается file.txt прямо в папке приложении, но я хочу создать его в C/Program...

Дальнейший путь - C++
Всем доброго времени суток. На данный момент прочитал 2 книги по С++ (Шилдт - руководство для начинающих и Лафоре - ооп в С++. Хотелось бы...

Путь к процессам - C++
Нашел вот такой код#include &lt;windows.h&gt; #include &lt;Psapi.h&gt; int main(){ int pid = 3432; // PID of notepad.exe char...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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