ГДЗ по информатике 9 класс Босова, номер §1.1 ПМ 8

§. ПМ Рекурсия и ханойская башня

В сети Интернет размещено много разных онлайн-вариантов игры «Ханойская башня». Подберите какой-нибудь из них по своему вкусу и попытайтесь решить головоломку для восьми колец за минимально возможное количество ходов. При возникновении трудностей загляните в главу 3: подсказка содержится в задании 6 для практических работ.

Решение

Обозначим стержни А, Б и В. Нужно перенести всю башню с А на В, используя Б как вспомогательный. Большее кольцо нельзя класть на меньшее.

Чтобы перенести башню из колец, сначала переносим верхние колец на Б. Затем переносим самое большое кольцо на В. Наконец, переносим колец с Б на В. Для каждой меньшей башни повторяем те же три действия, меняя роли стержней.

Для одного кольца нужен один ход: . Для остальных по описанному разбиению .

; ; .

; ; ; .

Меньше ходов быть не может: прежде чем сдвинуть нижнее кольцо, обязательно надо убрать все семь верхних, а после этого снова уложить их на нижнее. Поэтому описанный способ достигает минимума.

Ответ

Для восьми колец требуется не менее ходов; рекурсивный перенос выполняет их за ходов.

Помогло?

Номер §1.1 ПМ 8