Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Листинг 9.10. 
PhoneNumberMnemonics.java (продолжение)
public 
String[] getMnemonics() {
String[] mnemonics = { "" };
for 
(Character digit : phoneNumber.toCharArray()) {
String[] combo = phoneMapping.get(digit);
if 
(combo != 
null
) {
mnemonics = 
cartesianProduct
(mnemonics, combo);
}
}
return 
mnemonics;
}
public static void 
main(String[] args) {
System.
out
.println("Enter a phone number:");
Scanner scanner = 
new 
Scanner(System.
in
);
String phoneNumber = scanner.nextLine();
scanner.close();
System.
out
.println("The possible mnemonics are:");
PhoneNumberMnemonics pnm = 
new 
PhoneNumberMnemonics(phoneNumber);
System.
out
.println(Arrays.
toString
(pnm.getMnemonics()));
}
}

---

260
Глава 9.
Другие задачи
Оказывается,.номер.телефона.144-07-87.можно.записать.как.1GH0STS,.что.легче.
запомнить.
9.4. РЕАЛЬНЫЕ ПРИЛОЖЕНИЯ
Динамическое.программирование,.с.помощью.которого.решалась.задача.о.рюк-
заке,.—.это.широко.используемый.метод,.который.позволяет.решить.задачи,.на.
первый.взгляд.кажущиеся.нерешаемыми,.путем.разбиения.их.на.более.мелкие.
задачи.и.составления.решения.из.этих.частей..Сама.задача.о.рюкзаке.связана.
с.другими.оптимизационными.задачами,.где.конечное.количество.ресурсов.
(вместимость.рюкзака).должно.быть.распределено.среди.конечного,.но.исчер-
пывающего.набора.вариантов.(предметов,.которые.можно.украсть)..Представьте.
колледж,.который.должен.освоить.свой.спортивный.бюджет..У.него.недостаточ-
но.денег.для.финансирования.всех.команд.и.есть.ожидания.относительно.того,.
сколько.пожертвований.для.выпускников.внесет.каждая.команда..Это.может.
привести.к.возникновению.похожей.на.задачу.о.рюкзаке.проблемы.оптимизации.
распределения.бюджета..Подобные.задачи.часто.встречаются.в.реальном.мире.
Задача.коммивояжера.—.типичное.явление.для.таких.компаний,.как.UPS.и.FedEx..
Компании.по.доставке.посылок.хотят,.чтобы.их.машины.двигались.по.наикрат-
чайшим.маршрутам..Это.не.только.делает.работу.водителей.более.приятной,.но.
и.экономит.топливо.и.уменьшает.расходы.на.техническое.обслуживание..Мы.
все.путешествуем.во.время.работы.или.для.удовольствия,.и.поиск.оптимальных.
маршрутов.при.посещении.нескольких.мест.помогает.экономить.ресурсы..Но.
задача.коммивояжера.не.сводится.к.одной.лишь.маршрутизации.путешествий,.
она.встречается.практически.в.любом.сценарии.маршрутизации,.который.тре-
бует.единичных.посещений.узлов..Несмотря.на.то.что.минимальное.связующее.
дерево.(см..главу.4).может.свести.к.минимуму.длину.кабелей,.необходимых.для.
соединения.соседних.узлов,.оно.не.сообщает.нам.оптимальную.длину.проводов,.
если.каждый.дом.должен.быть.напрямую.подключен.только.к.одному.другому.
дому.как.части.гигантской.сети,.которая.замыкается.на.свою.начальную.точку..
Эту.проблему.решает.задача.коммивояжера.
Методы.генерации.перестановок,.подобные.используемым.при.наивном.подходе.
к.решению.задачи.коммивояжера.и.задачи.мнемоники.телефонных.номеров,.по-
лезны.для.тестирования.всевозможных.алгоритмов.перебора..Например,.если.вы.
пытаетесь.взломать.короткий.пароль,.то.можете.сгенерировать.все.возможные.
перестановки.символов,.которые.потенциально.в.нем.присутствуют..Специали-
стам,.выполняющим.масштабные.задачи.генерации.перестановок,.стоит.применять.
очень.эффективный.алгоритм.генерации.перестановок,.такой.как.алгоритм.Хипа
1
.
1
.
Sedgewick R. 
Permutation.Generation.Methods..—.Princeton.University..http://mng.bz/87Te.

---

9.5. Упражнения