Книга является наиболее полным руководством по разработке эффективных ал

Глава 1. Введение в разработку алгоритмов 
37 
Теперь допускаем, что данное утверждение верно для всех чисел вплоть до 
n
. Для до-
казательства общего случая 
n
+ 1 видим, что если мы вынесем наибольший член из-под 
знака суммы 
1
1
1
! (
1) (
1)!
!
n
n
i
i
i i
n
n
i i
+
=
=
× = + × +
+
×
∑
∑
то получим левую часть нашего индуктивного допущения. Заменяя правую часть, по-
лучаем: 
1
1
! (
1) (
1)! (
1)! 1
n
i
i i
n
n
n
+
=
× = + × +
+ +
−
∑
(
1)! ((
1) 1) 1
n
n
= + ×
+ + −
(
2)! 1
n
= +
−
Этот общий прием выделения наибольшего члена суммы для выявления экземпляра 
индуктивного допущения лежит в основе всех таких доказательств. ■ 
1.4. Моделирование задачи 
Моделирование является искусством формулирования приложения в терминах точно 
поставленных, хорошо понимаемых задач. Правильное моделирование является клю-
чевым аспектом применения методов разработки алгоритмов решения реальных задач. 
Более того, правильное моделирование может сделать ненужным разработку или даже 
реализацию алгоритмов, соотнося ваше приложение с ранее решенной задачей. Пра-
вильное моделирование является ключом к эффективному использованию материала 
во второй части этой книги. 
В реальных приложениях применяются реальные объекты. Вам, может быть, придется 
работать над системой маршрутизации сетевого трафика, планированием использова-
ния классных комнат учебного заведения или поиском закономерностей в корпоратив-
ной базе данных. Большинство же алгоритмов спроектировано для работы со строго 
определенными абстрактными структурами, такими как перестановки, графы или мно-
жества. Чтобы извлечь пользу из литературы по алгоритмам, вам нужно научиться вы-
полнять постановку задачи абстрактным образом, в терминах процедур над фундамен-
тальными структурами. 
1.4.1. Комбинаторные объекты 
Очень велика вероятность, что над решаемой вами алгоритмической задачей уже рабо-
тали другие, хотя, возможно, и в совсем иных контекстах. Но не надейтесь узнать, что 
известно о вашей конкретной "задаче оптимизации процесса 
А
", поискав в книге сло-
восочетание "процесс 
А
".
Вам нужно сформулировать задачу оптимизации вашего 
процесса в терминах вычислительных свойств стандартных структур, таких как: 
перестановка — 
упорядоченное множество элементов. Например, {1, 4, 3, 2} и
{4, 3, 2, 1} являются двумя разными перестановками одного множества целых чи-
сел. Мы уже видели перестановки в задачах оптимизации маршрута манипулятора и 

---

38