Алгоритмы на камушках. Постигаем отдыхая
Продолжая неисчерпаемую тему камешков, вспомним, что их можно не только подкидывать разными способами, но и занимательно-познавательных развлечений найдется немало. Напр, Ханойская башня:
- это известная головоломка на перемещения: Имеется пирамида с кольцами разного диаметра. И два пустых основания. Нужно переместить все кольца на одно из свободных оснований. Переносить - по одному кольцу. Так чтоб исходный порядок в результате получился прежним - от самого большого внизу к самому маленьком в верху. При любом промежуточном раскладе ни одно большее кольцо должно оказаться сверху меньшего
- не по порядку временно можно, но не большое на маленьком.
Не пробовали раньше? Хотите порешать с детьми или с внуками?
Не подглядывайте тогда )
Покрутить задачу, так и сяк к ней примериться, чтобы малыш видел процесс обдумывания - полезней, чем готовое объяснение. Иначе откуда будущий школьник узнает, как это, решение без готового образца, что нужно делать, когда не знаешь с какой стороны подступиться?
Булыжники друг на друга громоздить - не только у ребятишек любимое пляжное развлечение -
камешки, они же увесистые - даже самые кособокие годятся на башенку, не любые предметы так выстроишь.
Ханойскую головоломку проще показать как раз на камешках. Потому как большой камень на маленьком просто не удержится. Место для вспомогательных пирамид можно большими камнями обозначить или просто очертить.
Но если с пляжной погодой не повезло, то и на кухне найдется из чего организовать развлечение не без пользы -
картошины уравновесить труднее, больше трех-четырех вряд ли, но больше и не надо - чтоб перекладывания слишком не затягивать.
С помидоринками управиться проще, форма способствует )
Игрушечная пирамидка-башенка тоже годится - большая чашка на маленькую не встанет, просто проглотит ее.
"Придуманная профессором Люка легенда гласит, что в Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
Количество перекладываний в зависимости от количества колец вычисляется по формуле 2n-1 .
Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет."
Для трех дисков понадобится 23 -1 = 7 телодвижений.
А для 6 уже 25 -1 = 63 - не у всякого юного исследователя терпения хватит.
Можно и он-лайн позаморачиваться: http://hanoi.maramygin.ru/
Пройти не сложно, но как малышу объяснить последовательность действий?
Начнем с минимально возможного - пусть на основании пирамидки лежат два кольца:
Снимаем верхнее-маленькое, чтоб иметь возможность добраться до большого:
Сделано, перемещаем его :
И завершаем сбор двухэтажной пирамидки:
Еще раз:
- Освободили самое большое кольцо, убрав то, что было на нем сверху.
- Перенесли большое кольцо на новую площадку.
- Вернули положенную ему "надстройку".
Представим теперь, что зеленое основание пирамидки - это третье кольцо. Самое большое. Ничто не мешает перенести его на свободное место -
А потом - снова решить задачу двух колец! для возвращения "надстройки" зеленому основанию.
Но. А что если под обрезом картинки скрывается еще одно - самое-самое нижнее кольцо пирамиды? Мы его не видим, но оно есть. Серое, например. Лежит одно-одинешенько. А рядом пустой стержень.
Т.е, лыко-мочало:
- Самое нижнее кольцо освободили от всего что было сверху.
- Перенесем его на соседнюю позицию - в центр.
- Теперь осталось "решить задачу трех колец", для возвращении четырехступенчатой башенке
должного вида на основе серого основания в центре.
И так далее.
Мы познакомились с рекурсией.
Не обязательно пугать детей такими страшными словами.
Главное руками процесс пощупать )
- Значит, чтобы получить решение для семи колец, нужно найди его для 6, 5 и тд. и запомнить последовательность действий? А в случае 120 - для предыдущих 118-ти?
- Мы неизбежно каждый раз начинаем с "задачи для двух колец", и действуем так, будто под ними больше ничего нет. Решили - переходим к "задаче для трех".
Допустим, впервые взялись за семиэтажную пирамиду - на картинке стадия "задача решена четырех колец";
пятый диск высвобожден - и перенесен на свободное основание. Запоминать ничего не требуется. А дальше - осталось переместить пирамиду из четырех дисков на крайнее правое основание. Все тем же порядком. То, что там уже лежит один диск - дела не меняет.
Пирамидка - для малышей, это просто; если большим внукам и любомудрствующим бабушкам не встречалась "Задача о голубоглазых островитянах", предлагаю попробовать свои силы:
[Spoiler (click to open)]На острове живёт племя из 1000 человек. Их религия особым образом относится к цвету глаз человека - человек не должен жить, если знает цвет своих глаз. Поэтому они никогда не говорят об этом, не смотрятся в зеркало и так далее. И если кто-нибудь всё же узнает цвет своих глаз, он должен ритуально покончить с собой на центральной поляне в ближайший полдень.
Все островитяне абсолютно логичны и догадливы и знают об этом. То есть, если можно сделать логический вывод из информации, они его делают.
Среди этих 1000 человек у 900 карие глаза, а у 100 голубые.
Естественно, каждый видит цвет глаз всех остальных, и не знает только своего цвета глаз.
Однажды на остров прибыл путешественник. Он сразу сдружился с островитянами и завоевал полное их доверие.
Отплывая, он обратился ко всему племени с благодарностью и заметил, что ему было чудно видеть здесь голубоглазых, как и он сам. Ему объяснили что говорить такого нельзя, и он в расстроенных чувствах отплыл.
Какое из решений верно: "Ничего не произойдет", "на сотый день голубоглазые островитяне покончат с собой" ?
Формулировка приписывается математику Теренсу Тао
(Добавим для пущей корректности, что в языке, на котором попрощался путешественник, нет различия между единственным и множественным числом: допустим он сказал "видел голубые глаза" - возможно имея ввиду два глаза одного человека)
