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

Сейчас покажем, что необходимо 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 дисков на трех колышках.

2

1

Решение. ?????????? ?????