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

Часть I. Практическая разработка алгоритмов 
мы можем допустить, что после первых 
n – 
1 итераций сортировки вставками пер-
вые 
n – 
1 элементов массива 
A
будут полностью отсортированы; 
чтобы определить, куда следует вставить последний элемент 
х
, нам нужно найти 
уникальную ячейку между наибольшим элементом, не превышающим 
х
, и наи-
меньшим элементом, большим чем 
х
.
Для этого мы сдвигаем все бо´льшие элементы 
назад на одну позицию, создавая место для элемента 
х
в требуемой позиции. ■ 
Но к индуктивным доказательствам нужно относиться с большой осторожностью, т. к. 
в цепь рассуждений могут вкрасться трудно распознаваемые ошибки. Прежде всего, 
это 
граничные ошибки
.
Например, в приведенном выше доказательстве правильности 
алгоритма сортировки вставками мы самоуверенно заявили, что между двумя элемен-
тами массива 
А
имеется однозначно определяемая ячейка, в которую можно вставить 
наш элемент 
х
, когда массив в нашем базовом экземпляре содержит только одну ячей-
ку. Поэтому для правильной обработки частных случаев вставки минимальных или 
максимальных элементов необходимо соблюдать бо´льшую осторожность. 
Другой, более распространенный, тип ошибок в индуктивных доказательствах связан с 
небрежным подходом к расширению экземпляра задачи. Добавление всего лишь одно-
го элемента к экземпляру задачи может полностью изменить оптимальное решение. 
Соответствующий пример для задачи календарного планирования показан на рис. 1.7. 
Рис. 1.7. 
Оптимальное решение (прямоугольники)
до и после внесения изменений (пунктирная линия) в экземпляр задачи 
После добавления нового временного интервала в экземпляр задачи новое оптималь-
ное расписание может не содержать ни одного из временных интервалов любого опти-
мального решения, предшествующего изменению. Бесцеремонное игнорирование 
таких аспектов может вылиться в очень убедительное доказательство полностью не-
правильного алгоритма. 
П
ОДВЕДЕНИЕ ИТОГОВ
Математическая индукция обычно является верным способом проверки правильности
рекурсивного алгоритма. 
Остановка для размышлений:
Правильность инкрементных алгоритмов 
ЗАДАЧА.
Доказать правильность рекурсивного алгоритма для инкрементации нату-
ральных чисел, т. е. 
y→y
+ 1, представленного в листинге 1.10. 
Листинг 1.10. Алгоритм для инкрементации натуральных чисел 
Increment (y) 
if y = 0 then return(1) else 
if (y mod 2) = 1 then 
return(2·Increment([
⎣
y/2
⎦
)) 
else return(y + 1) 

---