Дипломная работа: Возвратные задачи

Объединение уравнений (5) и (6) с уравнением J(1)=1 дает рекуррентное соотношение, которое определяет J во всех случаях:

J(1) = 1

J(2n) = 2∙J(n) − 1 при n ≥ 1 (7)

J(2n+1) = 2∙J(n) + 1 при n ≥ 1

Решим данное рекуррентное соотношение. Составим таблицу первых значений J(n):

n	1	2 3	4 5 6 7	8 9 10 11 12 13 14 15	16
J(n)	1	1 3	1 3 5 7	1 3 5 7 9 11 13 15	1

Если сгруппировать значения n по степеням двойки (в таблице эти группы отделены вертикальными линиями), то в каждой группе J(n) всегда будет начинаться с 1, а затем увеличиваться на 2. Итак, если записать n в виде n = 2^m +k, где 2^m – наибольшая степень 2, не превосходящая n, а k – то, что остается, то решение рекуррентного соотношения должно иметь вид:

J(2^m +k) = 2k+1 при m≥ 0 и 0 ≤ k< 2^m (8)

(Если 2^m ≤ n< 2^{m +1} , то остаток k= n−2^m удовлетворяет неравенству 2^m ≤k+2^m <2^{m +1} , т.е. 0 ≤ k < 2^m )

Докажем (8) методом математической индукции по m.

1) База: m = 0 => k = 0

J(2⁰ +0) = J (1) = 2∙0 + 1 = 1 (верно);

2) Индуктивный переход: пусть верно для всех чисел t≤ (m − 1). Докажем для t=m:

a) если m> 0 и 2^m +k=2n, то k – четно и J (2 ^m + k ) = J(2(2^{m -1} +)) = 2∙J(2^{m -1} +) − 1 2(2∙ + 1) −1 = 2 k + 1

b) если m > 0 и 2^m +k=2n+1, то k – нечетно (т.е. k=2t+1) и J (2 ^m + k ) = = J(2^m +(2t+1)) = J(2(2^{m -1} +t) +1) 2∙J(2^{m -1} + t) + 1 2(2t+1) + 1 = 2 k + 1

Другой способ доказательства, когда k – нечетно:

Можно заметить, что J(2n+1) − J(2n) = 2, тогда J(2^m +k) = 2 + J(2^m + (k− −1))J(2^m +k) = 2 + 2(k −1) + 1 => J(2^m +k) = 2k+1.

Из пунктов 1 и 2 следует: при m ≥ 0 и 0 ≤ k < 2^m J(2^m +k) = 2k+1.

Решение всякой задачи может быть обобщено так, что его можно применить к более широкому кругу задач. Поэтому изучим решение (8) и исследуем некоторые обобщения рекуррентного соотношения (7).

Обратимся к двоичным представлениям величин nи J(n) (т.к. степени 2 играли важную роль в нашем поиске решения).

n = (b_m b_m-1 … b₁ b₀ )₂ ;

т.е. n = b_m 2^m + b_{m -1} 2^{m -1} + … + b₁ 2 + b₀

где каждое b_i равно 0 или 1, причем старший бит b_m равен 1. Вспоминая, что n=2^m +k, последовательно получаем:

n = (1 b_m-1 … b₁ b₀ )₂

k = (0 b_m-1 … b₁ b₀ )₂

(т.к. k= n−2^m = 2^m + b_m-1 2^m-1 + … + b₁ 2 + b₀ − 2^m = 0∙2^m + b_m-1 2^m-1 + …+ b₁ 2 + b₀ )

2k = (b_m-1 … b₁ b₀ 0)₂

(т.к. 2 k=2(b_{m -1} 2^{m -1} +b_{m -2} 2^{m -2} …+ b₁ 2 + b₀ )=b_{m -1} 2^m + b_{m -2} 2^{m -1} + … + b₁ 2² + b₀ 2+0)

2k+1 = (b_m-1 … b₁ b₀ 1)₂

J(n) = (b_m-1 … b₁ b₀ b_m )₂