| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Составление последовательности пар цифр |
| Автор: Rrader 7.7.2008, 05:21 |
Здравствуйте!  Есть произвольное количество пар цифр (цифры изменяются от 1 до 8). Нужно определить - возможно ли составить из этих пар последовательность, по принципу домино (т.е. в паре числа можно переставлять). Если возможно, то какую. Например: (1,4) (4,7) (7,5) (0,0) (0,6) (1,6) Составить можно такую последовательность: (0,0) - (0,6) - (6,1) - (1,4) - (4,7) - (7,5) Но вот не могу сообразить хороший алгоритм, как это определить... |
| Автор: Akina 7.7.2008, 08:03 |
| Можно выстроить цепь, если: 1) Цифр, количество которых в наборе нечетно, не более 2 (т.е. 0 или 2). 2) Для любой цифры, для которой в наборе есть "дубль", есть по крайней мере один "не-дубль". |
| Автор: Ln78 7.7.2008, 08:49 |
| Akina, набор (1,2), (1,3), (2,3), (5,6) твоим требованиям удовлетворяет? |
| Автор: Akina 7.7.2008, 08:52 |
| Ln78, логично. Нужно вводить требование "нераспадения на подмножества". |
| Автор: d06osipov 7.7.2008, 09:05 | ||
Не верно, по крайней мере так может быть два цикла. Пример: (1 2)-(2 3)-(3 1) (4 5)-(5 6)-(6 4) сдесь всех цифр чётно и каждой не более двух. Задача: в точности обход графа. Числа -- вершины. Если есть пара (n,m), то между вершинами n и m есть ребро. Если у связного графа степени всех вершин чётны, то существует цикл, весь его обходящий, проходящий по каждому ребру по одному разу (это почти то, что нужно, т. о. первое условие, данное Akinой, необходимо и достаточно вместе со связностью). Если есть возможность выделить память в размере O(n), где n --- количество пар, то задача определения связности решается рекурсивно за O(n). Экономней ---- пока не знаю. |
| Автор: Rrader 7.7.2008, 10:18 |
| http://www.pagat.com/tile/wdom/math.html |
| Автор: Rrader 7.7.2008, 14:47 |
| Я так понял, нужен алгоритм нахождения пути, в котором задействованы будут все ребра (доминошки). Допустим, у нас такие таблички: (4 2) - (2 6) - (6 5) - (5 4) - (4 6). В общем случае таблички перемешаны, но как видно, цепь существует. Я составил граф:  Задача решена, додумался! |
| Автор: Alix 7.7.2008, 16:21 |
Вообще граф у тебя интересный: если попадаешь в вершину по одному из ее концов, то выходить можно только из другого. По-идее, обыграть это можно разбив вершины на две и сделав связь между ними. Как-то так: только тогда надо как-то контролировать, чтобы придя в одну вершину выходили из соседней, а не из любой другой, например, сделав связь между ориентированной... хотя не... Подумать надобно )) |
