Xreferat.com » Рефераты по математике » Возвратные задачи

Возвратные задачи

башни с В обратно на А при том же ограничении. Докажите, что

(1)

 

если  n = 0

 

если  n > 0

 
                               

(2)

 

если  n > 0

 

если  n = 0

 
                           

Решение.

 

Рассмотрим частные случаи: 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 > 0

 

если  n = 0

 

Эксперимент с тремя дисками дает ключ и к общему правилу перемещения 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 на колышек А можно переместить за  перекладываний. Получили соотношение:        

если  n > 0

 

если  n = 0

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

Таким образом, получили, что системы (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) можно переместить за  перекладываний.

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

при 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) можно переместить с одного колышка на другой в исходном порядке всех одинаковых дисков сверху донизу за  перекладываний.

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

при 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.

 при n > 0,

 
Еще можно заметить следующее: т.к. , следовательно , то, подставляя данное равенство в соотношение (*) получим рекуррентное соотношение:           

имеющее то же самое решение

Задача 12. Давайте еще обобщим задачу 11а, предполагая, что имеется n различных размеров дисков и ровно mk дисков размера k. Определите наименьшее число A(m1, m2, …,mn) перекладываний дисков, необходимых для перемещения такой башни, если считать диски одинаковых размеров неразличимыми.

Решение. Для того, что переложить башню, состоящую из n различных размеров дисков, среди которых ровно mk дисков размера k, потребуется следующее число перекладываний:

при n > 0,

 
              

где mn – это количество самых больших нижних дисков.

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

A(m1)=2A(0)+m1=m1;

A(m1,m2)=2A(m1)+m2=21∙m1+m2;

A(m1,m2,m3)=2A(m1,m2)+m3=22∙m1+21∙m2+m3;

A(m1,m2,m3,m4)=2A(m1,m2,m3)+m4=23∙m1+22∙m2+21∙m3+m4.

Отсюда можно выдвинуть гипотезу, что

при n > 0

 
           A(m1,m2,…,mn)= 

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

1) База:   n=1   A(m1)=20∙m1=m1  (верно);

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

=

Из 1 и 2 следует, что A(m1,m2,…,mn)= 

при n > 0.

Задача 13. На какое максимально возможное число областей плоскость делится n зигзагообразными линиями, каждая из которых состоит из двух параллельных полубесконечных прямых, соединенных прямолинейным отрезком?

Решение. Пусть - это максимальное число областей, на которые плоскость делится n зигзагообразными линиями. Рассмотрим частные случаи:

                                                  

           

                                                

(Здесь Ln =  + 1 - максимальное число областей, на которые плоскость делится n прямыми)

Из этих частных случаев можно видеть, что зигзагообразная линия подобна трем прямым с тем лишь отличием, что области сливаются, если «три» прямые не продолжать после их пересечения:

Области 1, 2, 6 и 3, 4, 5, которые были бы разделены при наличии трех прямых, превращаются в единую область в случае одной зигзагообразной линии, т.е. мы теряем четыре области. Так же у нас имеется две параллельные прямые, следовательно, мы теряем еще одну область. Таким образом, если привести все

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: