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

256
Глава 9.
Другие задачи
Рис. 9.3.
Кратчайший путь для коммивояжера, позволяющий посетить
все пять городов в штате Вермонт
Для.решения.задачи.коммивояжера.на.больших.наборах.данных.были.задейство-
ваны.два.метода,.уже.описанные.в.этой.книге..Первый.—.динамическое.програм-
мирование,.которое.мы.применили.в.этой.главе,.рассматривая.задачу.о.рюкзаке..
Второй.—.генетические.алгоритмы,.описанные.в.главе.5..Было.опубликовано.
множество.журнальных.статей,.в.которых.генетические.алгоритмы.называют.почти.
оптимальным.решением.задачи.коммивояжера.с.большим.количеством.городов.

---

9.3. Мнемоника для телефонных номеров
257
9.3. МНЕМОНИКА ДЛЯ ТЕЛЕФОННЫХ НОМЕРОВ
До.того.как.появились.смартфоны.со.встроенной.адресной.книгой,.на.каждой.
кнопке.телефона.кроме.цифры.были.еще.несколько.букв..Причиной.этого.было.
обеспечение.возможности.выработать.простые.мнемонические.правила.для.запо-
минания.телефонных.номеров..В.Соединенных.Штатах,.как.правило,.на.клавише.1.
букв.не.было,.на.клавише.2.стояло.ABC,.на.клавише.3.—.DEF,.на.клавише.4.—.GHI,.
на.клавише.5.—.JKL,.на.клавише.6.—.MNO,.на.клавише.7.—.PQRS,.на.клавише.8.—.
TUV,.на.клавише.9.—.WXYZ,.на.клавише.0.букв.также.не.было..Таким.образом,.
номер.1-800-MY-APPLE.соответствует.номеру.телефона.1-800-69-27753..Такие.
сочетания.все.еще.встречаются.в.рекламных.объявлениях,.поэтому.цифры.с.кла-
виатуры.попали.в.современные.приложения.для.смартфонов.(рис..9.4).
. .
Рис. 9.4.
В приложении Phone для iOS 
сохранены буквы на клавишах, которые 
были на старых телефонах
Как.придумать.новое.мнемоническое.правило.для.номера.телефона?.В.1990-х.го-
дах.было.популярно.условно-бесплатное.приложение,.позволяющее.это.сделать..
Разные.части.данной.программы.генерировали.все.перестановки.букв.телефонного.
номера.и.затем.просматривали.словарь,.чтобы.найти.слова,.которые.содержали.
эти.перестановки..Затем.программа.показывала.пользователю.перестановки.
с.наиболее.полными.словами..Мы.решим.первую.половину.этой.задачи..Поиск.
в.словаре.останется.в.качестве.самостоятельного.упражнения.

---