Возникла такая задача.
Преамбула. Простой вариант задачи.Дано: Алфавит из N символов.
Необходимо. Составить, из символов алфавита, строку максимальной длины, чтобы любая соседняя пара символов была различна.
Задача легко сводится к поиску Эйлерова пути в ориентированном графе. Соответсвенно строится строка длиной N*N+1.
Сложный вариант задачи.Дано: Алфавит из N символов.
Необходимо. Составить, из символов алфавита, строку максимальной длины, удовлетворяюющую условию:
Для каждого i (1<=i<=N-1). Любая пара символов находящихся на расстоянии i была различна. Расстоянием между двумя числами будем считать модуль разности их номеров позиции в строке.
Пример. Для алфавита {1,2,3,4} можно составить такую строку.
1,1,2,1,3,4,4,1,4,3,2,2,4,2,3,1
-- Ср июл 11, 2012 08:22:40 --Свободного времени нет совсем, на победу не претендую. Но у меня персональный соперник - Alexu007. У нас метод аналогичный, результаты у меня чуть похуже.
Вызов брошен. Ждем принятия вызова от Alexu007. Зрители запасаются попкорном.
Исходные позиции:
Цитата:
41 Alexu007 7.511470 07-07-2012 @ 19:16:09
45 Victor Dimitriev 6.424870 07-08-2012 @ 18:05:18