Привет, решение данной задачи на Java. (файл-список городов в аттаче)Широко известна игра "Города". Называется какой-нибудь город, допустим, "Саратов". Кончается на "в", значит требуется назвать другой город, у которого в названии первая буква "в". Это может быть "Воронеж". Следующий город должен начинаться на "ж" и т.д. Запрещено повторять название городов. Надо написать программу, которая из набора названий городов (все названия разные) строит цепочку максимальной длины.
Задача: Города. Покритикуйте.
Модератор: Absurd
У вас нет необходимых прав для просмотра вложений в этом сообщении.
Код: Выделить всё
package olympicexercises;
import java.util.*;
import java.io.*;
public class CitiesSolver
{
/**
* Получение первой буквы для сравнения
*
* @param city - город для выбора первой буквы
* @return первая буква
*/
public static Character getFirstChar(String city)
{
return city.charAt(0);
}
/**
* Получение последней буквы для сравнения, с пропуском "неправильных" букв
*
* @param city - город для выбора последней буквы
* @return последняя буква
*/
public static Character getLastChar(String city)
{
int pos = city.length() - 1;
char lastChar = city.toUpperCase().charAt(pos);
if (city.toUpperCase().charAt(pos) == 'Й') {
return 'И';
}
else if (lastChar == 'Ь' || lastChar == 'Ы' || lastChar == 'Ъ') {
pos--;
}
return city.toUpperCase().charAt(pos);
}
/**
* Рекурсия обхода дерева
*
* @param cities - набор городов для инициализации коллекции
* @return наиболее длинная цепочка из всех цепочек городов
*/
public static List<String> findLongestChain(Set<String> cities)
{
Map<Character, Set<String>> citiesIndex = createIndex(cities);
return findLongestChain(citiesIndex);
}
/**
* Рекурсия обхода дерева
*
* @param citiesIndex - коллекция городов для поиска
* @return наиболее длинная цепочка из всех цепочек городов
*/
private static List<String> findLongestChain(Map<Character, Set<String>> citiesIndex)
{
List<String> chain = new ArrayList<String>(0);
for (Character firstChar : citiesIndex.keySet()) {
List<String> newChain = findLongestChain(citiesIndex, firstChar);
System.out.println("Цепочка максимальной длины (" + newChain.size() + "): " + newChain + "\n==");
if (chain.size() < newChain.size()) {
chain = newChain;
}
}
System.out.println("Самая длинная из цепочек (" + chain.size() + "): " + chain);
return chain;
}
/**
* Рекурсия обхода дерева
*
* @param citiesIndex - коллекция городов для поиска
* @param firstChar - первая буква для поиска города
* @return цепочки городов
*/
private static List<String> findLongestChain(Map<Character, Set<String>> citiesIndex, Character firstChar)
{
List<String> chain = new ArrayList<String>(0);
try {
for (String city : citiesIndex.get(firstChar)) {
Map<Character, Set<String>> index = cloneIndex(citiesIndex); // работаем с копией коллекции городов
index.get(firstChar).remove(city); // удаляем использованный город
List<String> newChain = new ArrayList<String>(); // инициализация массива цепочки городов
newChain.add(city); // добавление города в цепочку
newChain
.addAll(findLongestChain(index, getLastChar(city))); // добавление наиболее перспективных городов в цепочку
System.out.println("Прорабатывается цепочка (" + newChain.size() + "): " + newChain);
if (chain.size() < newChain.size()) { // выход из рекурсии
chain = newChain;
}
}
}
catch (NullPointerException e) {
}
return chain;
}
/**
* Создание копии коллекции городов
*
* @param citiesIndex - коллекция городов для копии
* @return копия коллекции городов
*/
private static Map<Character, Set<String>> cloneIndex(Map<Character, Set<String>> citiesIndex)
{
Map<Character, Set<String>> newIndex = new HashMap<Character, Set<String>>();
for (Character key : citiesIndex.keySet()) {
newIndex.put(key, new HashSet<String>(citiesIndex.get(key)));
}
return newIndex;
}
/**
* Инициализация коллекции городов для поиска
*
* @param cities - города для инициализации
* @return коллекция городов
*
* key - первая буква города, value - имена городов начинающихся на эту букву
*/
private static Map<Character, Set<String>> createIndex(Set<String> cities)
{
Map<Character, Set<String>> index = new HashMap<Character, Set<String>>();
for (String city : cities) {
Set<String> cs = index.get(getFirstChar(city));
if (cs == null) index.put(getFirstChar(city), cs = new HashSet<String>());
cs.add(city);
}
return index;
}
public static void main(String[] args) throws IOException
{
final Set<String> cities = new HashSet<String>();
// Загрузим города из файла
final BufferedReader in = new BufferedReader(new FileReader("src/olympicexercises/cities2.txt"));
for (String city; (city = in.readLine()) != null ;) {
cities.add(city); // и сложим все имена в этот массив
}
in.close();
Set<String> sortedCities = new TreeSet<String>(cities);
System.out.println("Список городов (" + sortedCities.size() + "): " + sortedCities);
System.out.println("----------------------------");
findLongestChain(cities);
}
}
Допустим, существует набор городов "Абв", "Акв", "Вба": для данного набора городов возможны два варианта решения и в моем алгоритме будут вычеслены обе цепочки (хотя это не нужно), как оптимизировать алгоритм так чтобы при таком раскладе вычислялась только одна цепочка (не важно какая)?
Как оптимизировать решения для городов с одинаковыми первой и последней буквой ("Анапа")?
Как оптимизировать решения для городов с одинаковыми первой и последней буквой ("Анапа")?