Вирусы(#1010) КВН(#1012)
#1011

Задача g6_1011: Города.
Широко известна игра "Города". Называется какой-нибудь город, допустим, "Саратов". Кончается на "в", значит требуется назвать другой город, у которого в названии первая буква "в". Это может быть "Воронеж". Следующий город должен начинаться на "ж" и т.д. Запрещено повторять название городов. Надо написать программу, которая из набора названий городов (все названия разные) строит цепочку максимальной длины.
Решение g6_1011:
Типично рекурсивная задача (что такое рекурсия, можно узнать в разделе "Алгоритмы").
Заводим массив, в котором хранятся все названия городов, массив, который хранит максимальную на данный момент цепочку, массив, который хранит цепочку, составляемую сейчас, и булевский массив, хранящий флаги, использован город или нет.
В основной программе вызываем рекурсивную процедуру со всеми возможными начальными городами. При запуске рекурсивной процедуры помечаем город как использованный и заносим его в цепочку, запускаем цикл, в котором проверяем, если город еще не использован и его первая буква такая же как последняя буква нынешнего города, то запускаем рекурсивную процедуры для нового города. Если ни один город не удовлетворяет этим условиям, то сравниваем нынешнюю и максимальную цепочку по длине и, если нынешняя цепочка длиннее, то меняем их местами. Помечаем город как неиспользованный, выходим из рекурсивной процедуры.
Все просто!

Скачать тесты к задаче