Симферопольский Форум: Нужна помощь программиста/математика - Симферопольский Форум

Перейти к содержимому

Внимание! Для всех новых пользователей введена премодерация сообщений и тем.
Страница 1 из 1
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

Нужна помощь программиста/математика ткните, в какую сторону копать

#1 Пользователь онлайн   Инквизитор 

  • Vexilla regis prodeunt inferni
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 10 759
  • Регистрация: 20 Сентябрь 10
  • Сказали спасибо раз:

Отправлено 15 Декабрь 2015 - 18:03

Хау, народ)

Имею задачу, которую не знаю как решить. Гуглеж заводит или не туда, или в такие дикие дебри, что у меня отказывают пониматоры.

Собственно, воть она:

Дано:
N пар объектов вида X->Y. Объекты в парах могут повторяться.

Пример этих пар:
A->С
B->A
C->E
D->E
E->B
F->A
G->C


Требуется:
1. Построить цепь из этих объектов таким образом, что:
а) Второй объект в каждой паре является первым объектом в следующей
б) Объекты не повторяются
в) Направление стрелок предпочтительно слева направо, но в целом не имеет значения
г) Цепь должна быть максимальной длины

Цепь может иметь ответвления (когда в нескольких парах один и тот же одинаковый второй объект) и кольца.
Пример цепи, построенной из вышенаписанных пар:
         F
         |
         V
D->E->B->A->С<-G
   ^        |
   |________|



Собственно, прошу ткнуть меня носом в подходящий алгоритм или их комбинацию. Или еще как-то наставить на путь истинный...

Высочайшее достижение нейтронной мегалоплазмы! Ротор поля наподобие дивергенции градуирует себя вдоль спина и там, внутре, обращает материю вопроса в спиритуальные электрические вихри, из коих и возникает синекдоха отвечания...

#2 Пользователь офлайн   Rumlin 

  • Добрый волшебник
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 24 816
  • Регистрация: 16 Сентябрь 10
  • Сказали спасибо раз:
  • ГородHavana
  • Страна:  

Отправлено 15 Декабрь 2015 - 18:05

видимо графы


Я детей вообще то боюсь, милостивый мой государь, - шумливы, жестоки и себялюбивы, а коли дети правят державой? ©Юлиан Семёнов
Ничего не делается к лучшему © Борис Раушенбах
Люди, люди — это самое главное. Люди дороже даже денег. © Ф.М. Достоевский


Какой ты любопытный.

Поблагодарили: 1

#3 Пользователь онлайн   Инквизитор 

  • Vexilla regis prodeunt inferni
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 10 759
  • Регистрация: 20 Сентябрь 10
  • Сказали спасибо раз:

Отправлено 15 Декабрь 2015 - 18:16

Просмотр сообщенияRumlin сказал:

видимо графы

Перекопал википедию... из того, что понял - все не то (

Высочайшее достижение нейтронной мегалоплазмы! Ротор поля наподобие дивергенции градуирует себя вдоль спина и там, внутре, обращает материю вопроса в спиритуальные электрические вихри, из коих и возникает синекдоха отвечания...

#4 Пользователь офлайн   Rumlin 

  • Добрый волшебник
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Старая гвардия
  • Сообщений: 24 816
  • Регистрация: 16 Сентябрь 10
  • Сказали спасибо раз:
  • ГородHavana
  • Страна:  

Отправлено 15 Декабрь 2015 - 18:44

но что- то явно из тех степей. В принципе похоже на генерацию лабиринтов m.habrahabr.ru/post/176671/


Я детей вообще то боюсь, милостивый мой государь, - шумливы, жестоки и себялюбивы, а коли дети правят державой? ©Юлиан Семёнов
Ничего не делается к лучшему © Борис Раушенбах
Люди, люди — это самое главное. Люди дороже даже денег. © Ф.М. Достоевский


Какой ты любопытный.

#5 Пользователь онлайн   ravemassacre 

  • Пользователь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Активный участник
  • Сообщений: 1 715
  • Регистрация: 20 Июнь 15
  • Сказали спасибо раз:
  • ГородОрджоникидзе
  • Страна:  

Отправлено 15 Декабрь 2015 - 19:48

Вначале убрать дубликаты, если входные данные это позволяют.
Потом каждой такой паре перехода назначить уникальный ID, т.е. в данном случае это будет обыкновенный массив ['a->b', 'd->f'] где номер значения и есть id.
Потом создать массивы для каждого a, b, c из ID возможных переходов.
Затем для каждого a, b, c придумать аглоритм поиска цепочек, и находить самые длинные, если цепочка достигла длинны массива возможных переходов - получили замкнутую цепь с кротчайшим путем.
А так конечно нужно думать, много нюансов вылезет наверняка, на бумажке такое не придумаешь...


#6 Пользователь офлайн   Mim 

  • Новичок
  • Pip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Новичок
  • Сообщений: 9
  • Регистрация: 20 Октябрь 14
  • Сказали спасибо раз:
  • Страна:  

Отправлено 15 Декабрь 2015 - 20:43

Возможно стоит построить обобщенный граф последовательно добавляя в него правила. Потом искать самую длинную цепочку. Надо учесть, что может быть набор несвязанных графов, например для случая A->B, C->D.


#7 Пользователь офлайн   Местный Сусанин 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Активный участник
  • Сообщений: 1 391
  • Регистрация: 10 Апрель 12
  • Сказали спасибо раз:
  • ГородСимферополь
  • Страна:  

Отправлено 15 Декабрь 2015 - 21:46

Я очень дико извиняюсь конечно... Но не могу пройти мимо данной темы.. Ээээммм, о чем вообще речь идет то?


#8 Пользователь офлайн   SlavaD 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Технический администратор
  • Сообщений: 1 119
  • Регистрация: 16 Сентябрь 10
  • Сказали спасибо раз:
  • Страна:  

Отправлено 15 Декабрь 2015 - 22:54

DOT
digraph SI{
    A->С;
    B->A;
    C->E;
    D->E;
    E->B;
    F->A;
    G->C;
}

Прикрепленные изображения

  • Прикрепленное изображение: si.png


#9 Пользователь офлайн   SlavaD 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Технический администратор
  • Сообщений: 1 119
  • Регистрация: 16 Сентябрь 10
  • Сказали спасибо раз:
  • Страна:  

Отправлено 16 Декабрь 2015 - 10:04

И на сколько я понял, у вас в задании ошибка, в строке "A->С", "С" - русская, собственно DOT все правильно построил, если заменить на лат. будет так:

Прикрепленные изображения

  • Прикрепленное изображение: si2.png


Поблагодарили: 1

#10 Пользователь онлайн   Инквизитор 

  • Vexilla regis prodeunt inferni
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Модераторы
  • Сообщений: 10 759
  • Регистрация: 20 Сентябрь 10
  • Сказали спасибо раз:

Отправлено 16 Декабрь 2015 - 17:00

Просмотр сообщенияSlavaD сказал:

И на сколько я понял, у вас в задании ошибка, в строке "A->С", "С" - русская, собственно DOT все правильно построил, если заменить на лат. будет так:

Возможно, русская.
DOT - есть либы под жабкоскрипт?

Высочайшее достижение нейтронной мегалоплазмы! Ротор поля наподобие дивергенции градуирует себя вдоль спина и там, внутре, обращает материю вопроса в спиритуальные электрические вихри, из коих и возникает синекдоха отвечания...

#11 Пользователь офлайн   SlavaD 

  • Живу здесь
  • PipPipPipPipPip
  • Вставить ник
  • Цитировать
  • Раскрыть информацию
  • Группа: Технический администратор
  • Сообщений: 1 119
  • Регистрация: 16 Сентябрь 10
  • Сказали спасибо раз:
  • Страна:  

Отправлено 16 Декабрь 2015 - 18:52

Просмотр сообщенияИнквизитор сказал:

DOT - есть либы под жабкоскрипт?


Javascript не увлекаюсь, не скажу, для всяких perl, php, python - точно есть.


Поделиться темой:


Страница 1 из 1
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

1 человек читают эту тему
0 пользователей, 1 гостей, 0 скрытых пользователей