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

104
Глава 3.
Задачи с ограничениями
Попробуем.это.запустить.(листинг.3.17).
Листинг 3.17. 
SendMoreMoneyConstraint.java (продолжение)
public static void 
main(String[] args) {
List letters = List.
of
('S', 'E', 'N', 'D', 'M', 'O', 'R', 
'Y');
Map> possibleDigits = 
new 
HashMap<>();
for 
(Character letter : letters) {
possibleDigits.put(letter, List.
of
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
}
// мы не принимаем ответы, начинающиеся с 0 
possibleDigits.replace('M', List.
of
(1));
CSP csp = 
new 
CSP<>(letters, possibleDigits);
csp.addConstraint(
new 
SendMoreMoneyConstraint(letters));
Map solution = csp.backtrackingSearch();
if 
(solution == 
null
) {
System.
out
.println("No solution found!");
} 
else 
{
System.
out
.println(solution);
}
}
}
Вы,.вероятно,.заметили,.что.мы.предварительно.задали.значение.для.буквы.M..
Это.сделано.для.того,.чтобы.исключить.ответ,.в.котором.M.соответствует.0,.
потому.что,.если.подумать,.ограничение.не.учитывает,.что.число.не.может.
начинаться.с.нуля..Но.попробуйте.выполнить.программу.без.этого.заранее.
назначенного.ответа.
Решение.должно.выглядеть.примерно.так:
{R=8, S=9, D=7, E=5, Y=2, M=1, N=6, O=0}
3.6. РАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ НА ПЕЧАТНОЙ ПЛАТЕ
Производитель.должен.установить.прямоугольные.микросхемы.на.прямоуголь-
ную.плату..По.сути,.эта.задача.сводится.к.вопросу:.«Как.разместить.все.прямо-
угольники.разных.размеров.внутри.другого.прямоугольника.таким.образом,.чтобы.
они.плотно.прилегали.друг.к.другу?».Решить.эту.задачу.можно,.применив.схему.
решения.задач.с.ограничениями.(рис..3.5).
Задача.размещения.элементов.на.печатной.плате.похожа.на.задачу.поиска.слов..
Только.вместо.1.
×
.
N
.прямоугольников.(слов).в.ней.представлены.
M 
×
 N 
прямо-
угольников..Как.и.в.задаче.поиска.слов,.они.не.могут.перекрываться..Прямо-
угольники.нельзя.размещать.по.диагонали,.так.что.в.этом.смысле.задача.даже.
проще,.чем.поиск.слов.

---

3.7. Реальные приложения