VPF::поиск всех цепочек фирм - Форум программистов

kuzyara

Дата 19.10.2009, 15:19 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 215
Регистрация: 13.11.2006

Репутация: нет
Всего: 1

День добрый, знатоки! smile

Недавно встретился вот с такой задачей:

Код


Есть несколько фирм, каждая из них продает и покупает какой-то товар. Для прост[I]a[/I]ты товары будут a, b, c, d и т.д. ))

firm1 : buy [I]a,b[/I] sell [I]a,c[/I]
firm2 : buy [I]b [/I]sell [I]а[/I]
firm3 : buy [I]a,c,d[/I] sell [I]a,b[/I]

Найти все возможные замкнутые цепочки фирм.

Например фирма firm1 продаёт товар [I]С [/I]фирме firm3 , та в свою очередь продает например отвар [I]В [/I] фирме firm2 , та в свою очередь продаёт свой товыр первой фирме. Всё, цепочка замкнулась.

Ещё возможные цепочки:
firm2 -> firm3
firm1 -> firm2 и т.д. 

Естественно фирм и товаров будет много.

Я уже реализовал решение этой задачи перебором, где вместо фирм использовал символы, и работал со строками 1, 12, 123, 13, 132, 2, 21, 213, 23, 231, 3, ... 321 (мне это легче всего показалось...). Но так как это долго, доработал чтобы после данного символа можно было ставить только тот... только ту фирму которая может купить товар у данной. Вот так вот собираю строку и даю на выход...

Внимание, вопрос! smile

Есть ли готовые алгоритмы, подходящие для этой задачи?
---------------------------------
ап
ну поскажите, как ещё её пожно решить?

Это сообщение отредактировал(а) kuzyara - 20.10.2009, 13:32

--------------------

подпись