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

Таким образом, имеем бесконечно много решений уравнения J(n) = , и первые такие:

m	k	N= 2m + k	J(n) =2k+1=	n (двоичное)
1	0	2	1	10
3	2	10	5	1010
5	10	42	21	101010
7	42	170	85	10101010

Правый крайний столбец содержит двоичные числа, циклический сдвиг которых на одно позицию влево дает тот же самый результат, что и обычный сдвиг на одну позицию вправо (деление пополам).

Далее обобщим J - функцию, т.е. рассмотрим рекуррентность схожую с (7), но с другими константами: α, β и γ; найдем решение в замкнутой форме.

                           f(1) = α,

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

                        f(2n + 1) = 2f(n) + γ           при n ≥ 1.

Составим таблицу для малых значений n:

Анализируя таблицу можно сделать предположение, что коэффициенты при α равны наибольшим степеням 2, не превосходящим n; между последовательностями 2 коэффициенты при β уменьшаются на 1 вплоть до 0, а при γ увеличиваются на 1, начиная с 0. Если выразить f(n) в виде:

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

то, по-видимому,

A(n) = 2m ,

B(n) = 2m −1−k,                         (12)

                                       С(n) = k.

Здесь n = 2m + k       и      0 ≤ k < 2m            при n ≥ 1.

Докажем соотношения (11) и (12).

Докажем (11) методом математической индукции по числу n и при этом будем полагать, что (12) выполняется.

1) База:   n=1=20+0 (m=k=0),   f(1)=A(1)∙α+B(1)∙β+C(1)∙γ= =20∙α+(20−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(2m+2t) = =f(2(2m-1 + t)) 2∙f(2m-1 + t)+β 2∙(A(2m-1 + t)∙α + B(2m-1 + t)∙β + C(2m-1 + +t)∙γ) + β  2(2m-1∙α + (2m-1−1−t)∙β + t∙γ) + β = 2m∙α + (2m−1−2t)∙β + 2t∙γ = 2m∙α+ + (2m−1−k)∙β + k∙γ = A(n)∙α + B(n)∙β + C(n)∙γ;

b) если n - нечетное, тогда k тоже нечетно, т.е. k=2t+1, и f(n) = =f(2m+2t+1) = f(2(2m-1 + t)+1) 2∙f(2m-1 + t)+ γ 2∙(A(2m-1 + t)∙α + B(2m-1 + +t)∙β + C(2m-1 + t)∙γ) + γ  2(2m-1∙α + (2m-1−1−t)∙β + t∙γ) + γ = 2m∙α + +(2m−1−(2t+1))∙β + (2t+1)∙γ = 2m∙α+ + (2m−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 = 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((bm bm-1 … b1 b0)2) = (bm-1 … b1 b0 bm)2,   где bm = 1. Можно показать, что и обобщенная рекуррентность (10) имеет похожее решение.

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

(15)

               f(1) = α,

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

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

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

C

B

A

Решение.

 

Пусть 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.

Страницы: 1, 2, 3, 4, 5, 6