85541 (589841), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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) = 2^m ,

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

С(n) = k.

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

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

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

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

Р

A

C

B

ешение.

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

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

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

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

F₀=0

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

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

Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна). Вычислим: F₁=2=3¹ −1, F₂=3² −1, F₃=3³ −1. Из этого можно сделать предположение, что

F_n = 3ⁿ −1 при n≥0.

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

1. База: n=0, F₀=3⁰–1=1–1=0 (верно);

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

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

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

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

F₀+1 = 1,

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

Обозначим U_n = F_n+1, тогда получим: U₀ = 1, U_n = 3U_n-1 при n>0.

Решением этой рекурсии есть U_n= ; следовательно, F_n = −1.

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

Задача 3. Покажите, что в процессе перемещения башни при ограничениях из предыдущего упражнения нам встретятся все допустимые варианты размещения n дисков на трех колышках.

Р

1

2

ешение. Занумеруем диски

n-2

n-1

Существует (в соответствии с условиями задачи) только три возможных расположения каждого диска на одном из колышков: либо на первом колышке (А), либо на втором колышке (B), либо на третьем колышке (С). Это будут перестановки длины n из трех элементов. Например, .

Число перестановок длины k из n элементов: . Следовательно, для нашего случая , т.е. – это все возможные различные расположения n дисков на трех колышках.

В предыдущей задаче было показано, что наименьшее число перекладываний с колышка А на колышек B через колышек С равно −1. Таким образом, каждый раз перекладывая диск с одного колышка на другой, мы получаем все допустимые расположения n дисков на трех колышках (т.к. мы не перекладываем один диск с одного колышка на другой по несколько раз)

Характеристики

Список файлов ВКР