Смекни!
smekni.com

Возвратные задачи (стр. 4 из 9)

Из пунктов 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 = 2m+ k=> 2n = 2m+1+2k, тогда A(2n) = 2m+1, B(2n)=2m+1−1−2k, С(n)=2k. Подставляем: (2m+1 −2∙2m)∙α + +(2m+1−1−2k−2(2m−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 = 2m+ k=> 2n+1 = 2m+1+2k+1, тогда A(2n+1) = 2m+1, B(2n+1) = 2m+1 −1−(2k+1), С(n+1) = 2k+1. Подставляем : (2m+1 −2∙2m)∙α + +(2m+1−2−2k−2(2m−1−k))∙β + (2k+1 −2k−1)∙γ=0

0∙α + 0∙β + 0∙γ = 0, получили 0=0 (верно).

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

Выше было показано, что J – рекуррентность имеет решение в двоичной записи: J((bmbm-1 … b1b0)2) = (bm-1 … b1b0bm)2, где bm = 1. Можно показать, что и обобщенная рекуррентность (10) имеет похожее решение.

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

f(1) = α,

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

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

f((bmbm-1 … b1b0)2) = 2f((bmbm-1 … b1)2) + βb

= 4f((bmbm-1…b2)2)+2βb
b
= =…=2mf((bm)2)+2m-1βb
+ … + 2βb
b
= 2mα + 2m-1βb
+ … + 2βb
b
.

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

f((bmbm-1 … b1b0)2) = (α βb

βb
… βb
βb
)2 (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 запрещен. (Каждое перекладывание должно производиться через средний колышек. Как обычно, больший диск нельзя класть на меньший.)

Решение.

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

Рассмотрим крайние случаи: F0=0, F1=2, F2=8, F3=26. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n−1) меньших дисков на колышек B (что требует Fn-1 перекладываний), затем перекладываем самый большой диск на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков на колышек А (еще Fn-1 перекладываний), затем перекладываем самый большой диск на колышек B (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков на колышек B (еще Fn-1 перекладываний). Таким образом, n дисков (при n>0) можно переместить самое большое за 3Fn-1+2 перекладываний (т.е. достаточно перекладываний): Fn≤ 3Fn-1+2.

Сейчас покажем, что необходимо 3Fn-1+2 перекладываний. На двух этапах мы обязаны переместить самый большой диск. Когда мы это делаем, (n−1) меньших дисков должны находиться на одном колышке (А или B), а для того чтобы собрать их вместе, потребуется, по меньшей мере, Fn-1 перекладываний. Самый большой диск можно перекладывать и более одного раза. Следовательно, Fn≥ 3Fn-1+2.

Эти два неравенства вместе с тривиальным решением при n=0 дают рекуррентное соотношение:

F0=0

Fn= 3Fn-1+2 при n>0

Решим данное соотношение.

Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим: F1=2=31 −1, F2=32 −1, F3=33 −1. Из этого можно сделать предположение, что

Fn= 3n−1 при n≥0.

Докажем методом математической индукции по числу n:

1) База: n=0, F0=30–1=1–1=0 (верно);

2) Индуктивный переход: пусть доказано для всех чисел t≤ (n–1). Докажем для t=n: Fn= 3Fn-1+2

3(3n-1−1)+2 = 3n − 1.

Из пунктов 1 и 2 следует: при n≥0 Fn= 3n − 1.

Второй способ решения.

К обеим частям соотношения (1) прибавим 1:

F0+1 = 1,

Fn+1 = 3Fn-1+3 при n>0.

Обозначим Un= Fn+1, тогда получим: U0 = 1, Un= 3Un-1 при n>0.

Решением этой рекурсии есть Un=

; следовательно, Fn=
−1.

В дальнейшем мы не будем показывать достаточное и необходимое условие в решении подобных задач, а сразу будем описывать получение нужного равенства. Это связано, во-первых, с тем, что достаточное и необходимое условие показывается аналогично тому, как это сделано в данной задаче, а во-вторых, в виду ограниченности объема дипломной работы.