Рекурсивная стратегия

Итак, нам необходимо перенести n дисков со стержня (н) на стержень (к). Допустим у нас есть процедура перенесения n-1 диска, обозначим ее Х(n-1,(Ст1),(Ст2)), тогда задача легко разрешима для этого вначале перенесем n-1 диск со стержня (н) на стержень (д), применяя процедуру Х, затем перенесем n-ый диск со стержня (н) на стержень (к) (обозначим эту процедуру П((Ст1),(Ст2)) и наконец перенесем n-1 диск со стержня (д) на стержень (к). Работа выполнена. Алгоритм в этом случае можно записать следующим образом:

1. Х(n-1, (н), (д))

2. П((н),(к))

3. Х(n-1, (д), (к))

Теперь необходим частный случай, не являющийся рекурсивным. Если диск всего один, то можно сразу перенести его со стержня (н) на стержень (к), таким образом, выполняется тождество Х(1, (Ст1), (Ст2))=П((Ст1), (Ст2)). Таким образом, процедура Х представляется в виде блок-схемы:

Просто? Да, несомненно, просто, но все равно некоторым такое решение внушает опасение. Почему? Скорее всего, сказывается недостаток владения рекурсивными методами, но не только. Рекурсивные решения отличаются от обычных именно своей не очевидностью. Что же сделать, чтобы "поверить" в то, что предъявленная стратегия верна? На мой взгляд, лучший способ проверить стратегию "практически" для малых n.

Вернемся к вопросу вычисления функции f(n). Для предъявленной рекурсивной процедуры, представление f(n) достаточно тривиально:

f(1)=1

f(n)=2* f(n-1)+1

Явный вид функции f(n) нетрудно найти из приведенных выше соотношений, пользуясь принципом математической индукции: f(n)=2ⁿ -1.

Дополнительно к тому, что уже имеется, заметим еще одно свойство перемещаемых дисков. Пусть наши диски пронумерованы от 1 до n, таким образом, что диск с наименьшим диаметром имеет номер 1, второй по величине диаметра диск номер 2, и т.д., наконец диск с наибольшим диаметром имеет номер n. Тогда можно заметить, два диска с номерами одинаковой четности никогда не будут лежать друг на друге (т.е. диск с номером 2 не ляжет на диск с номером 4, 6 или 8). Докажем что это свойство выполнено. Доказательство будем проводить по индукции, допустим, что свойство выполнено для процедуры Х(p,(Ст1),(Ст2)), где p < n (для p=1 и Х(1,(Ст1),(Ст2)) свойство выполнено автоматически), далее докажем, что тогда свойство выполняется и для Х(n,(Ст1),(Ст2)). Начнем с переноса (n-1) дисков на стержень (д). Пока не передвинут (n-1)-ый диск, ни один диск не кладется непосредственно на диск с номером n и значит требуемое свойство выполнено. Рассмотрим момент, когда n-2 дисков находятся на одном стержне, диски с номерами n-1 и n - на другом стержне, а третий стержень пуст. Мы перемещаем диск с номером n-1. Теперь нужно переместить первые n-2 дисков на диск с номером n-1, поэтому диски будут оказываться на диске с номером n. Если мы помещаем диск с номером k на диск с номером n, то для того, чтобы образовать пирамиду дисков с номерами от k до 1 и иметь возможность, переместить диск с номером k+1 на диск с номером n-1. Но поскольку требуемое свойство выполняется для n-1 дисков, то честность k+1 диска не может совпадать с четностью n-1. А значит, она совпадает с четностью n, и отсюда следует, что четность n и k различна.

Дата добавления: 2015-05-06