Algofil Сообщение 01/11/2011 12:11 Копия темы
Развращение джедаев сала. Есть набор кусков сала, которые (предположительно) нарезаны так, что можно состыковать каждый кусок со следующим (там ширина края, тип разреза подходит, как две половинки шпиёнской открытки) и замкнуть мега-кольцо из сала ))
Предложить алгоритм стыковки или выяснения факта нестыковки сала в кольцо

alex1153 Сообщение 01/11/2011 12:16 Копия темы
ТЗ непонятно ) Что за шпиёнска открытка – с устройством не знаком 

кольцо должно напоминать шайбу (для болта) или обруч (для бочки) ?

Algofil Сообщение 01/11/2011 12:20 Копия темы
шпиёнская открытка – берем открытку и режем/рвем на две части, одну резиденту, вторую засланцу, при контакте должно совпасть, так и сало...
ну обручем или шайбой – пофигу, лишь бы срезы совпали, но с точки зрения забоя свиней – обручем выгоднее ))

alex1153 Сообщение 01/11/2011 12:23 Копия темы
не, без картинки не пойму, задача геометрическая что ли ?

А сало сегодня куплю – зряплату дали ))

Algofil Сообщение 01/11/2011 12:35 Копия темы
ладно уж, даю задачу в интерпретации А.Л.Хижи:
есть набор слов, нужно составить замкунтую цепочку (аврал-лето-оптимист-трава), возможно с подциклами (картина-арбуз-зрение-епанча-артист-товар-рыба-анорак), так и с салом (АЛ тоже хохол, но до сала не додумался)
щя я еще заверну тему про сало, но в личных блогах, тут уже низзя...

Algofil Сообщение 01/11/2011 12:40 Копия темы
Восстание сала.

alex1153 Сообщение 01/11/2011 12:51 Копия темы
решение, оченвидно, может быть не одно. Но достаточно найти любое

1)первый шаг:

составляем массив звеньев AB , где буква A и буква B может принимать различные ключи

аврал-лето-оптимист-трава
->

ал
ло
от
та


2) дальше построим граф, где каждое звено может быть связано с множеством других звеньев (как оно там по науке нызывается? ) : "затравочное" звено – любое, к примеру "ал" , назначим уровень 0

у каждого звена – список правых и левых указателей на уровень 1

правые будут содержать ссылки на все звенья уровня 1, заканчивающиеся на "л",
левые будут содержать ссылки на все звенья уровня 1, начинающиеся на "а".

когда весь граф построен, смотрим среди узлов последнего уровня возможность соединиться с 0-м уровнем. Где это возможно сделать – от того последнего звена надо прощагать по убыванию уровня к 0 – это будут решения


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

Не компилировал, не отлаживал, наверняка есть ошибки и возможна оптимизация ))  Я домой утопал

hardcoder Сообщение 01/11/2011 12:53 Копия темы
Это не то же самое, что шпиёнская открытка – набор букв заведомо ограничен.
Шпионская открытка, наоборот, заведомо имеет только одну пару.

Algofil Сообщение 01/11/2011 12:55 Копия темы
отнюдь, кто мешает резать шпиёнские открытки пачками? набор каких букв ограничен? раньше хватало набора АНСИ, теперь УТФ ))

hardcoder Сообщение 01/11/2011 12:58 Копия темы
Тогда смысл шпиёнской открытки теряется :) 
Именно так я понял первоначальные условия.

В общем вам нужно определить складывается ли из произвольного набора костяшек домино одно (и только одно???) кольцо?

Algofil Сообщение 01/11/2011 12:59 Копия темы
типа неправильно, это просто цикл Эйлера, насчет графов – молодца, но там нет "звеньев", есть вершины и ребра, в данном случае вершины – конечные буквы, ребра – слова.

Algofil Сообщение 01/11/2011 13:01 Копия темы
заплюсовать не могу, знакомая личность ))
из костяшек домино можно сложить и одно кольцо и не одно и "рыбу" – всё зависит от алгоритма

jenner247450 Сообщение 01/11/2011 13:09 Копия темы
выяснение факта нестыковки – это у какого-то среза сала нет аналога на другом куске.
построение кусков сала будет напоминать сборку паззлов, точнее один из этапов, когда паззл уже рассортирован по типу кусочков (угловые/боковые/срединные) и из угловых и боковых начинается сбор рамочки паззла.

Algofil Сообщение 01/11/2011 13:17 Копия темы
да я ж уже напейсал ответ – цикл Эйлера (неважно кольцо или паззл, планарный граф он и есть планарный граф), я затвре еще одну задачку с салом подгоню ))

alex1153 Сообщение 01/11/2011 17:55 Копия темы
звенья – это я про двухбуквенные ключи говорю ) Поэтому я не называю их рёбрами

"цикл Эйлера" – не знаю такой, гляжу сейчас.

Ну вот как бы это его и ищем , только я умных названий не знал )))