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

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

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

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

10.12.2013, 23:08. Просмотров 1652. Ответов 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
ya_noob
_
314 / 148 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 19:52 #16
Цитата Сообщение от Aliru Посмотреть сообщение
ТУТ есть AABC->ABCD->BCDD->CDDB и ABCD->BCDB->CDBA->DBAB->BABC
а я изначально имел ввиду такую последовательность (всего одну):
AABC->ABCD->BCDB->CDBA->DBAB->BABC->ABCD->BCDD->CDDB
сможет ли ваша программа найти эту последовательность?

и еще вдогонку вопрос. может ли быть на входе такая последовательность (начало первого куска совпадает с концом последнего):
AABC->ABCD->BCDB->CDBA->DBAB->BABC->ABCD->BCDA->CDAA->DAAB ?

Добавлено через 4 минуты
или такая (конец уникальный, а начало AAB встречается в куске DAAB):
AABC->ABCD->BCDA->CDAA->DAAB->AABD->ABDC ?
1
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
12.12.2013, 03:31  [ТС] #17
да протупил, делал на глаз
сейчас проверю
варианты 2 и 3 не должны быть

Добавлено через 6 часов 26 минут
Вообщем что-то понял, что-то надо читать-понимать
0
ya_noob
_
314 / 148 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.12.2013, 08:03 #18
Цитата Сообщение от Aliru Посмотреть сообщение
Overlap Graph Problem.cpp
я понял что вам надо. а надо вам по исходным строкам найти все их пары такие, что префикс одной строки равен суффиксу другой, т.е. построить списки смежности для строк. только и всего.
у меня были сомнения насчет того, что надо восстановить всю цепочку (хотя вы и ответили "да"), т.к. способов восстановления может быть очень много.
вот вам ссыль на решение вашей задачи: http://bioalgo.blogspot.ru/2013/01/o...sic-graph.html
1
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
12.12.2013, 11:27  [ТС] #19
Самое интересное что я вчера ночью я наконец то понял что надо сделать и решил ее. Зато много нового узнал. Вам огромное спасибо за труды.
Подскажите пожалуйста такой еще вопрос. Есть входные данные:
0 -> 2
1 -> 3
2 -> 1
3 -> 0,4
6 -> 3,7
7 -> 8
8 -> 9
9 -> 6
Из них необходимо построить Эйлеров цикл:
6->8->7->9->6->5->4->2->1->0->3->2->6
Но я не могу понять как считывать входящие данные.
Строками?А потом отделять их и записывать по массивам?
0
12.12.2013, 11:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2013, 11:27
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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