Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Разное >> Номер 6

[Назад]    [Содержание ]    [Вперед]

  


Номер 6


  Условие: Номер 6


Задача 5. Пусть слово - это последовательность от 1 до 8 символов, не включающая пробелов. Вводится n слов A1,...,An. Можно ли их переупорядочить так, чтобы получилась "цепочка", т.е. для каждого слова Aj его первая буква должна совпадать с последней буквой предыдущего слова, а последняя буква в Aj - с первой буквой последующего слова; соответственно последняя буква последнего слова должна совпадать с первой буквой первого слова. В цепочку входят все n слов без повторений. Дать ответ в виде "Можно"\"Нельзя". Если такое упорядочение возможно, то вывести какую-нибудь цепочку слов. Слова при выводе разделяются пробелами.

  Решение задачи: Номер 6


Решение задачи 5. Если n=1, и единственное слово начинается и заканчивается на одну и ту же букву, то цепочка построена. Для того, чтобы можно было переупорядочить слова A1, ..., An из набора A в "цепочку", необходимо, чтобы совокупность букв, на которые заканчиваются слова, совпадала с совокупностью букв, на которые эти слова начинаются (другими словами, чтобы каждой завершающей букве слова соответствовала такая же начальная буква какого-то слова). То, что это не достаточное условие, показывает пример: AB, BC, CA, DE, ED. "Цепочку" построить нельзя. Так как цепочка обязана пройти через каждое слово, то все равно, с какого слова набора A начинать. Возьмем слово A1. Удаляем его из множества A: A:=A\A1. Ищем в A какое-нибудь слово Ai, начинающееся с последней буквы слова A1 (такое слово всегда существует, так как мы считаем, что необходимое условие, упомянутое выше, выполняется). Удаляем Ai из A: A:=A\Ai, ищем в A какое-нибудь Aj, начинающееся с последней буквы Ai и т.д. Продолжаем до тех пор, пока либо все слова A1, ... ,An не войдут в цепочку (тогда задача решена), либо пока не окажется, что A не пусто, и в нем нет слова, начинающегося на последнюю букву x последнего слова (кстати, из необходимого условия следует, что эта буква x совпадает с первой буквой первого слова). Мы нашли какую-то подцепочку. Пример: A=(AB,BC,CA,BD,DC,CB). Подцепочка1: AB,BC,CA. Цепочка существует: AB,BD,DC,CB,BC,CA. Пусть мы нашли подцепочку 1. Берем опять какое-нибудь слово из A в качестве начального для очередной подцепочки и опять повторяем построение следующей подцепочки, и т.д. В конце концов пусть множество A стало пустым, и весь начальный набор слов A1, ... ,An распался на k подцепочек. Начнем их склеивать: Пусть в подцепочках i и j соответственно есть слова u и v такие, что в u и v совпадают первые буквы. Пусть цепочка i имеет вид i=BuC, а j=EvD (тут B,C,D,E - некоторые последовательности слов). Склеенная из i и j цепочка будет иметь вид EuCBvD. (Проверьте, что такая склейка корректна!) Склеивая все подцепочки, получим искомую цепочку. Если на каком-то шаге окажется, что склейка никаких двух подцепочек невозможна, то задача неразрешима. Пример 1. Для приведенного в предыдущем примере набора слов будет 2 подцепочки: AB, BC, CA и BD, DC, CB. У них совпадают первые буквы в словах BC и BD. После склейки получаем AB, BD, DC, CB, BC, CA. Пример 2. A=(ACA, BB). Две подцепочки: ACA и BB. Слов с совпадающими первыми буквами в них нет, задача неразрешима. Вариант #2 решения задачи. Если при составлении цепочки оказалось, что в наборе A нет слова с первой буквой, совпадающей с последней буквой последнего слова Aj цепочки, то Aj "отщепляем" от нее и пытаемся найти другое подходящее слово. Если это не удается, то "отщепляем" очередное последнее слово цепочки и т.д. Если на каком-то шаге A пусто, то задача решена, иначе если на каком-то шаге цепочка стала пустой, то задача неразрешима. Пусть есть набор слов A=(A1, ... ,An). Каждому слову приписан его уникальный номер, равный индексу. Слова упорядочены по возрастанию индекса. Цепочка = A1 A=A\A1; инд=1. Пока (A не пусто) и (цепочка не пустая) повторять нц Если в A есть подходящее слово с индексом > инд то приписываем к цепочке это слово, слово удаляем из A инд=1 иначе "отщепляем" от цепочки последнее слово Aj инд=j Aj заносим в A кц Если A пусто, то цепочка найдена иначе задача не имеет решения. Этот метод называется "перебор с возвратом" ("backtracking").

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017