МАЛЫЙ МЕХМАТ МГУ

Кружок 4 класса

Руководитель Александра Ефремовна Подгайц
2014/2015 учебный год

Занятие 3 (11 октября 2014 года). Алгоритмы

Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

1.: (Ханойские башни для 4 колец) Даны три стержня, на один из которых нанизаны четыре кольца, причем кольца отличаются размером и лежат меньшее на большем. Перенесите пирамиду из четырёх колец на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
2.: (Ханойские башни для 5 колец) Решите предыдущую задачу для пяти колец.
3.: На камнях сидят лягушки-девочки и лягушки-мальчики. Лягушки-мальчики хотят пересесть на камни, где сидят лягушки-девочки, а лягушки-девочки хотят пересесть на камни, где сидят лягушки-мальчики. Каждая лягушка может прыгнуть либо на соседний камень (если он свободен), либо перепрыгнуть на камень сразу за соседней лягушкой (если он свободен). Как лягушкам поменяться местами?
4.: Решите задачу 3 при дополнительном условии: лягушки не могут прыгать назад, только вперёд!
5.: Семья супергероев ночью подошла к мосту. Бабушка-Молния может перейти его за 1 минуту, Железный Малыш — за 2 минуты, Криптонитовая Мама — за 5 минут, а Папа-Енот — за 10 минут. У них есть один фонарик. Мост выдерживает только двоих. Как им перейти мост за 17 минут? (Если переходят двое, то они идут с меньшей из их скоростей. Двигаться по мосту без фонарика нельзя. Светить издали нельзя. Носить друг друга на руках нельзя. Летать нельзя.)
6*.: (Ханойские башни для 8 колец) Представьте, что рядом с вами сидит обезьянка-робот, которая умеет решать задачу для 7 колец (то есть знает, какие операции нужно проделать, чтобы переложить 7 колец с одного стержня на другой по правилам). Переложите 8 колец с одного стержня на другой (с помощью обезьянки-робота). Не нарушайте правила, а то всё взорвётся!

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!