аргументы, связанные со спецификой алгоритмов, встретятся при их непосредственном рассмотрении; здесь же внимание уделяется только формулам самим по себе.

Формула 2.1 В рекурсивной программе, где при каждой итерации цикла количество вводов уменьшается на единицу, возникает следующее рекуррентное соотношение:

Слг= Слг-1 + Д где TV > 2 и С] = I.

Решение: Cjv порядка N/2. Для решения рекурсии ее можно раскрыть, применяя саму к себе следующим образом:

Cn= Cn-x + N

= Cn-2 + {N-\) + N

= Cn-ъ + (TV-2) + (TV- 1) + TV

Продолжая таким же образом, можно получить

Cv = С, + 2 + ... + (TV- 2) + (TV- 1) + TV

= 1 + 2 + ... + (TV- 2) + (TV- 1) + TV TV(TV-H) 2

Подсчет суммы 1 + 2 + ... + (TV - 2) + (TV - 1) + TV элементарен: прибавим к сумме ее же, но в обратном порядке. Результирующая сумма - удвоенный искомый результат - будет состоять из N слагаемых, каждое из которых равно TV + 1.

Формула 2.2 В рекурсивной программе, где на каждом шаге количество вводов уменьшается вдвое, возникает следующее рекуррентное соотношение:

Cn = Cn/2 + 1, где TV > 2 и Ci = 1.

Решение: порядка Ig TV. Из написанного следует, что это уравнение бессмысленно за исключением случая, когда N четно или же предполагается, что TV/2 - целочисленное деление. Сейчас предположим, что = 2 , чтобы рекурсия была всегда определена. (Заметьте, что л = Ig Л.) Тогда рекурсию еще проще раскрыть, чем в предьщущем случае:

= С2 -2 + 1 = С2 -з + 3

= С20 +П

= п + \.

Точное решение для любого TV зависит от интерпретации TV/2. Если N/2 представляет собой LTV/2J, тогда существует очень простое решение: Сд- - это количество бит в двоичном представлении числа TV, т.е. по определению LlgTVj + 1. Этот вы-

вод немедленно следует из того, что операция отбрасывания правого бита в двоичном представлении любого числа TV > О превращает его в LA72J (см. рис. 2.6).

Формула 2.3 В рекурсивной программе, где количество вводов уменьшается вдвое, но необходимо проверить каждый элемент, возникает следующее рекуррентное соотношение:

Cn = Cfn + Л, где > 2 и С, = 0.

Решение: Cjv порядка 2N. Рекурсия раскрывается в сумму N+ N/2 + N/4 + N/S + ... (Как и формуле 2.2, рекуррентное соотношение определено точно только в том случае, если является степенью числа 2). Если данная последовательность бесконечна, то сумма простой геометрической прогрессии равна 2N. Поскольку мы используем целочисленное деление и останавливаемся на 1, данное значение является приближением к точному ответу. В точном решении используются свойства двоичного представления числа Л.

Формула 2.4 В рекурсивной профамме, которая должна выполнить линейный проход по вводам до, в течение или после разбиения их на две половины, возникает следующее рекуррентное соотношение:

= 2Сщ + N, тде N > 2 н С, = 0.

Решение: С порядка N IgTV. На это решение ссылаются намного шире, чем на остальные из приведенных здесь, поскольку эта рекурсия используется в целом семействе алгоритмов разделяй и властвуй .

N {N)i [IgiVJ +1

РИСУНОК 2.6 ЦЕЛОЧИСЛЕННЫЕ ФУНКЦИИ И ДВОИЧНЫЕ ПРЕДСТАВЛЕНИЯ.

Рассматривая двоичное представление числа N (в центре), получим LA72J путем отбрасывания правого бита. То есть, количество бит в двоичном представлении числа N на единицу больше, чем в представлении числа L72J. Поэтому ugNJ + I, количество бит в двоичном представлении числа N, является решением формулы 2.2 в случае, если N/1 интерпретируется, как

С2 2С2 - -1- 2

= --+1 + 1

= п.

Мы находим решение почти так же, как это было сделано в формуле 2.2, но с дополнительным приемом на втором шаге - делением обеих частей равенства на 2 , который позволяет раскрыть рекурсию.

Формула 2.5 В рекурсивной программе, которая разбивает ввод надвое, а затем производит постоянное количество других операций (см. главу 5) возникает следующая рекурсия.

Cf=lCf,i + 1, где TV > 2 и С, = 1.

Решение: Сдг порядка IN. Это решение можно получить так же, как и решение формулы 2.4.

С помощью приведенных методов можно решить различные варианты подобных формул, имеющих другие начальные условия или небольшие отличия в добавочном члене, но необходимо помнить, что некоторые рекурсии, кажущиеся похожими, могут иметь гораздо более сложные решения. Существует множество специальных общих методов для математически строгого решения таких уравнений {см. раздел ссылок). Несколько сложных рекуррентных соотношений встретится в последующих главах, где и будут обсуждаться их решения.

Упражнения

> 2.33 Составьте таблицу значений С, заданных формулой 2.2 для 1 < N < 32, считая, что N/2 означает LTV/2J.

> 2.34 Выполните упражнение 2.33, но считая, что N/2 означает \N/2 .

> 2.35 Выполните упражнение 2.34 для формулы 2.3.

о 2.36 Предположим, что /д пропорционально постоянной величине и Cn = С fill +fN,raQN>tH О < C;v < с при N< t, где с и / - постоянные. Покажите, что Сдг пропорционально IgA.

2.37 Сформулируйте и докажите обобщенные версии формул 2.3-2.5, аналогичные обобщенной версии формулы 2.2 в упражнении 2.36.

2.38 Составьте таблицу значений Сд, заданных формулой 2.4 при 1 < N < 32 для трех следующих случаев: (i) N/2 означает LA72J, (ii) yV/2 означает Глу21, (iii) 2Сду2 равно С[лг/2] + Сглг/21.

2.39 Решите формулу 2.4 для случая, когда TV/2 означает [.N/2J, используя соответствие двоичному представлению числа Л, как это было сделано в доказательстве формулы 2.2. Подсказка: Рассмотрите все числа, меньшие N.

2.40 Решите рекурсию

Cn = Cn/2 + N при TV > 2 и d = О, когда TV является степенью числа 2.

2.41 Решите рекурсию

Cn = Сд,/а +1 при > 2 и С, = О, когда TV является степенью числа а. о 2.42 Решите рекурсию

Слг= осСд72 при TV > 2 и С] = 1, когда Л является степенью.числа 2.