Смекни!
smekni.com

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

Например, P(9) следует из P(8), а P(8) следует из P(2) и P(4), P(4) следует из P(2) и P(2), а P(2) выполняется.

Задача 10.Пусть Qn - минимальное число перекладываний, необходимых для перемещения башни из n дисков с колышка А на колышек B, если все перекладывания осуществляются по часовой стрелке – т.е. с А на B, или с B на другой колышек, и с другого колышка на А. Кроме того, пусть Rn– минимальное число перекладываний, необходимых для перемещения башни с В обратно на А при том же ограничении. Докажите, что

Решение.

Рассмотрим частные случаи: Q0=0, R0=0; Q1=1, R1=2; Q2=5, R2=7; Q3=15= =R2+1+R2, R3=21= Q3+1+Q2.

Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков cколышка А на колышек B по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка А на C, через колышек B(для этого потребуется

перекладываний, т.к. это тоже самое если бы мы перекладывали диски с колышка Bна колышек А через колышек С), затем перекладываем самый большой диск cколышка A на колышек B (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка C на B(что требует
перекладываний, по тем же соображениям). Таким образом, n дисков (при n>0) cколышка A на колышек B можно переместить за
перекладываний. Получили соотношение:

Эксперимент с тремя дисками дает ключ и к общему правилу перемещения n дисков cколышка Bна колышек A по часовой стрелке: сначала мы перемещаем (n−1) меньших дисков с колышка B на А (что требует Rn-1 перекладываний), затем перекладываем самый большой диск cколышка B на колышек С (одно перекладывание), потом помещаем (n−1) меньших дисков с колышка А на B(что требует Qn-1 перекладываний), затем перекладываем самый большой диск c колышек С на колышек А (одно перекладывание), и, наконец, помещаем (n−1) меньших дисков с колышка B на колышек А (еще Rn-1 перекладываний). Таким образом, n дисков (при n>0) cколышка B на колышек А можно переместить за

перекладываний. Получили соотношение:
И если мы вместо
подставим
(т.к.
, показали выше), то получим нужную нам систему:

Таким образом, получили, что системы (1) и (2) справедливы.

Задача 11.Двойная ханойская башня состоит из 2nдисков nразличных размеров – по два диска каждого размера. Как и в случае обычной башни, за один раз разрешается перекладывать только один диск и нельзя класть больший диск на меньший.

a) Сколько перекладываний необходимо для перемещения двойной башни с одного колышка на другой, если диски одинаковых размеров неотличимы друг от друга?

b) Что если в окончательном расположении дисков требуется воспроизвести исходный порядок всех одинаковых дисков сверху донизу?

Решение. a) Пусть

- минимальное число перекладываний башни 2n дисков с одного колышка на другой. Рассмотрим частные случаи: P0=0, P2=2, P4=6, P6=14. Эксперимент с шестью дисками дает ключ к общему правилу перемещения 2n дисков: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует
перекладываний), затем перекладываем 2 самых больших диска (одно перекладывание), потом помещаем (2n−2) меньших дисков на большие диски (что требует
перекладываний). Таким образом, 2n дисков (при n>0) можно переместить за
перекладываний.

Получили рекуррентное соотношение:

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

, P2 =2=
, P4 =6 =
, P6== 14=
(Здесь Tn = 2n−1 - минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка)
гипотеза:
при n≥ 0

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

при n≥ 0.

1) База: n=1

(верно);

2) Индуктивный переход: пусть верно для всех чисел t≤(2n−2). Докажем для 2n дисков:

Из пунктов 1 и 2 следует, что

при n ≥ 0.

b) Пусть

- минимальное число перекладываний башни из 2n дисков с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу.

Рассмотрим частные случаи: R0=0, R2=3, R4=11. Эксперимент с четырьмя дисками дает ключ к общему правилу перемещения 2n дисков в исходном порядке: сначала переместить (2n−2) меньших дисков с одного колышка на другой (что требует

перекладываний), затем перекладываем два самых больших диска на свободный колышек (два перекладывания; эти диски будут положены неправильно), потом перекладываем (2n−2) меньших дисков на свободный колышек (что требует
перекладываний), затем снова перекладываем два самых больших диска (два перекладывания; эти диски будут положены правильно), и, наконец, перекладываем (2n−2) меньших дисков на большие диски в исходном порядке (потребуется
перекладываний). Таким образом, 2n дисков (при n>0) можно переместить с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу за
перекладываний.

Получили рекуррентное соотношение:

(*)

Решим данное соотношение. R2 = 3 = 2P2−1, R4 = 11 = 2P4−1, R6 = 27 = 2P6−1

гипотеза:
при n > 0.

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

при n> 0.

1) База: n=1

(верно);

2) Индуктивный переход: пусть верно для всех чисел t≤(2n−2). Докажем для 2n дисков:

Из пунктов 1 и 2 следует, что

при n> 0.