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

1) База: n=1=2⁰ +0 (m=k=0), f (1) =A(1)∙α+B(1)∙β+C(1)∙γ= =2⁰ ∙α+(2⁰ −1−0)∙β+0∙γ= α (верно);

2) Индуктивный переход: пусть верно для всех чисел t≤ (n–1) , т.е. выполняется равенство f(t) = A(t)∙α + B(t)∙β + C(t)∙γ. Докажем для t=n:

a) если n – четное, тогда kтоже четное, т.е. k = 2t, и f ( n ) = f(2^m +2t) = =f(2(2^{m -1} + t)) 2∙f(2^{m -1} + t)+β 2∙(A(2^{m -1} + t)∙α + B(2^{m -1} + t)∙β + C(2^{m -1} + +t)∙γ) + β 2(2^{m -1} ∙α + (2^{m -1} −1−t)∙β + t∙γ) + β = 2^m ∙α + (2^m −1−2t)∙β + 2t∙γ = 2^m ∙α+ + (2^m −1−k)∙β + k∙γ = A ( n )∙α + B ( n )∙β + C ( n )∙γ ;

b) еслиn - нечетное, тогдаk тоженечетно, т.е. k=2t+1, иf(n) = =f(2^m +2t+1) = f(2(2^m-1 + t)+1) 2∙f(2^m-1 + t)+ γ2∙(A(2^m-1 + t)∙α + B(2^m-1 + +t)∙β + C(2^m-1 + t)∙γ) + γ 2(2^m-1 ∙α + (2^m-1 −1−t)∙β + t∙γ) + γ = 2^m ∙α + +(2^m −1−(2t+1))∙β + (2t+1)∙γ = 2^m ∙α+ + (2^m −1−k)∙β + k∙γ = A(n)∙ α + B(n)∙ β + C(n)∙ γ .

Из пунктов 1 и 2 следует: для n ≥ 1 f(n) = A(n)∙α + B(n)∙β + C(n)∙γ.

Теперь докажем (12) в предположении, что (11) выполняется.

Если n - четное, тогда по соотношению (10) f(2n) = 2f(n) + β. Подставляя в данное равенство соотношение (11) получим:

A(2n)∙α + B(2n)∙β + C(2n)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + β

(A(2n) − 2A(n))∙α + (B(2n) − 2B(n)−1)∙β + (C(2n) − 2C(n))∙γ = 0

Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: т.к. n = 2^m + k=> 2n = 2^{m +1} +2k, тогда A(2n) = 2^{m +1} , B(2n)=2^{m +1} −1−2k, С(n)=2k. Подставляем: (2^{m +1} −2∙2^m )∙α + +(2^{m +1} −1−2k−2(2^m −1−k)−1)∙β + (2k −2k)∙γ = 0 0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно);

Если n - нечетное, тогда по соотношению (10) f(2n+1) = 2f(n) + γ. Снова подставляя в данное равенство соотношение (11) получим:

A(2n+1)∙α + B(2n+1)∙β + C(2n+1)∙γ = 2(A(n)∙α + B(n)∙β + C(n)∙γ) + γ

(A(2n+1) − 2A(n))∙α + (B(2n+1) − 2B(n))∙β + (C(2n+1) − 2C(n)−1)∙γ = 0

Теперь подставим соотношение (12) в данное равенство и посмотрим, будет ли оно выполнятся: n = 2^m + k=> 2n+1 = 2^{m +1} +2k+1, тогда A(2n+1) = 2^{m +1} , B(2n+1) = 2^{m +1} −1−(2k+1), С(n+1) = 2k+1. Подставляем : (2^{m +1} −2∙2^m )∙α + +(2^{m +1} −2−2k−2(2^m −1−k))∙β + (2k+1 −2k−1)∙γ=0 0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно).

Таким образом, мы показали, что соотношения (11) и (12) верные.

Выше было показано, что J – рекуррентность имеет решение в двоичной записи: J((b_m b_{m -1} … b₁ b₀ )₂ ) = (b_{m -1} … b₁ b₀ b_m )₂ , где b_m = 1. Можно показать, что и обобщенная рекуррентность (10) имеет похожее решение.

Запишем соотношение (10) следующим образом:

(15)

f(1) = α,

f(2n + j) = 2f(n) + β_j при j = 0, 1 и n ≥ 1,

если положить β₀ = β и β₁ = γ. Тогда:

f((b_m b_{m -1} … b₁ b₀ )₂ ) = 2f((b_m b_{m -1} … b₁ )₂ ) + β_b = 4f((b_m b_{m -1} …b₂ )₂ )+2β_b +β_b = =…=2^m f((b_m )₂ )+2^{m -1} β_b + … + 2β_b +β_b = 2^m α + 2^{m -1} β_b + … + 2β_b +β_{b .}

Если мы расширим систему счисления с основанием 2 таким образом, что в ней допустимы произвольные числа, а не только 0 и 1, тогда предыдущий вывод означает, что

f((b_m b_{m -1} … b₁ b₀ )₂ ) = (α β_b β_b … β_b β_b )₂ (16)

Итак, изменение системы счисления привело нас к компактному решению (16) обобщенной рекуррентности (15).

Глава 2

Решение задач

Задача 1. То, что все лошади одной масти, можно доказать индукцией по числу лошадей в определенном табуне. Вот так:

«Если существует только одна лошадь, то она своей масти, так что база индукции тривиальна. Для индуктивного перехода предположим, что существует n лошадей (с номерами от 1 до n ). По индуктивному предположению лошади с номерами от 1 до n −1 одинаковой масти, и, аналогично, лошади с номерами от 2 до n имеют одинаковую масть. Но лошади посередине с номерами от 2 до n −1 не могут изменять масть в зависимости от того, как они сгруппированы, - это лошади, а не хамелеоны. Поэтому в силу транзитивности лошади с номерами от 1 до n также должны быть одинаковой масти. Таким образом, все n лошадей одинаковой масти. Что и требовалось доказать».

Есть ли ошибка в приведенном рассуждении и, какая именно?

Решение. Ошибка в данном рассуждении есть, и она заключается в доказательстве по индуктивному предположению. Для доказательства того, что n лошадей имеют одинаковою масть, используется пересечение двух множеств от 1 до n−1 и от 2 до n, но для n = 2 этого пересечения нет. Поэтому, если есть две лошади, имеющие разную масть, то утверждение неверно. Если же любые две лошади имеют одинаковую масть, то доказательство будет верным для любого n.

Задача 2. Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков с левого колышка А на правый колышек B , если прямой обмен между А и B запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя класть на меньший.)

C

B

A

Решение.

Пусть F_n - минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой через колышек С.