0

Добрый день. Я задавал здесь 19 января вопрос об алгоритме "Ханойские башни". Мне ответил @alexlz (спасибо) следующее:

Значение формального параметра number. Он соответствует глубине стека рекурсивных вызовов процедуры Towers. Т.е. на каждом уровне вы знаете, какое кольцо переносится в теле процедуры (вывод на cout). Вызов самого верхнего уровня (для переноса всех дисков) для вашего примера -- number==3. К этому моменту все кольца выше уже перенесены первым рекурсивным вызовом Towers на штырь free (в вызове на месте free стоит исходное to и наоборот). А второй вызов переносит все кольца с free на to с вспомогательным from. Пока лучше объяснить не получается. Рекомендуется распечать таблицу значений в процессе

Теперь понятно какое кольцо переносится на каждом уровне. При каждом новом рекурсивном вызове функции от переменной number отнимается единица, а при возврате из стека на каждом уровне переменная number становится на единицу больше. Теперь мне непонятно другое, первый рекурсивный вызов вновь вызывает сам себя пока верно условие 'if'. прикаждом новом рекурсивном вызове, в списке параметров функции изменяется переменная number(-1), но порядок расположения переменных from, free, to остается тот же. Получается при выходе из стека на каждом уровне изменяется только переменная number, а остальные переменные остаются в том же порядке?

5
  • 1
    >но порядок расположения переменных from, to, free остается тот же. Порядок как раз изменяется: void Towers(int number, int from, int to, int free) ... Towers(number-1, from, free, to); ... Towers(number-1, free, to, from);
    – insolor
    1 фев 2012 в 18:26
  • 1
    Этот вопрос подробно изложен по метке "алгоритмы" за 19 января.
    – Ключ
    1 фев 2012 в 18:26
  • 1
    insolor, ей богу не вижу этого, вижу что Towers(number-1, from, free, to) вызывает саму себя с тем же порядком, меняется только number.
    – Ключ
    1 фев 2012 в 18:43
  • 1
    вдогонку cout впервые срабатывает в теле Towers(number-1, from, free, to) Извините ошибка в вопросе, написал -- " порядок расположения from, to, free -- неправильно, имел ввиду -- from, free, to.
    – Ключ
    1 фев 2012 в 18:50
  • 1
    Ошибку в вопросе исправил.
    – Ключ
    1 фев 2012 в 19:03

2 ответа 2

6

Ок, еще раз:

но порядок расположения переменных from, to, free остается тот же.

Где же порядок остается таким же, если:

  • В формальных параметрах сначала идет from, потом to, потом free
  • В первом рекурсивном вызове: сначала from, потом free, а потом уже to
  • Во втором вызове: free, to, from

P.S. в вопросе с самого начала порядок был правильный - как в формальных параметрах

UPD. Начнем с самого начала. Задача - перенести 4 кольца с 1 стержня на 3 через 2:

Towers(4, 1, 3, 2);

Разбиваем на подзадачи:

  • Перенести 3 кольца с 1 на 2 стержень через 3 (Towers(3,1,2,3))
  • Перенести оставшееся кольцо с 1 на 3 стержень
  • Перенести 3 кольца со 2 на 3 стержень через 1 (Towers(3,2,3,1))

Точно так же рекурсивно разбиваем 1 подзадачу:

  • Перенести 2 кольца с 1 на 3 стержень через 2 (Towers(2,1,3,2))
  • Перенести оставшееся кольцо с 1 на 2 стержень
  • Перенести 2 кольца с 3 на 2 через 1 (Towers(2,3,2,1))

Аналогично разбиваем 2 подзадачу, и так до тех пор, пока все не сведется к перемещению отдельных колец.

UPD2. Ок. Заново.

I. Вызываем Towers(3,1,3,2); (команда перенести 3 кольца с 1 стержня на 3 через 2)
 II. Рекурсивный вызов Towers(2,1,2,3); (команда перенести 2 кольца с 1 стержня на 2 через 3)
  III. Рекурсивный вызов Towers(1,1,3,2); (перенести 1 кольцо с 1 стержня на 3)
    IV. Переносим 1 кольцо с 1 стержня на 3
  III. Переносим 1 кольцо с 1 стержня на 2
  III. Рекурсивный вызов Towers(1,3,2,1); (перенести 1 кольцо с 3 стрежня на 2)
    IV. Переносим 1 кольцо со 2 стержня на 3
  III. Результат: 1 кольцо осталось на 1 стержне, в других на 2 стержне
 II. Переносим 1 кольцо с 1 стержня на 3
 II. Рекурсивный вызов Towers(2,2,3,1); (перенести 2 кольца со 2 стержня на 3 через 1)
  III. Рекурсивный вызов Towers(1,2,1,3); (перенести 1 кольцо со 2 стержня на 1)
    IV. Переносим 1 кольцо со 2 стержня на 1
  III. Переносим 1 кольцо со 2 стержня на 3
  III. Рекурсивный вызов Towers(1,1,3,2); (перенести 1 кольцо с 1 стержня на 3)
    IV. Переносим 1 кольцо с 1 стержня на 3
 II. Результат: 3 кольца на 3 стержне

Для простоты вызовы с n=0 пропущены, т.к. смысловой нагрузки не несут. Римские цифры обозначают уровень рекурсивного вызова.

29
  • 1
    Да, но я вижу(аргументы в функцию(3, 1, 3, 2)) первый рекурсивный вызов: функция Towers(number-1, from, free, to)вызвана, следующ. шаг проверка условия 'if', следующ. шаг вызов Towers(number-1, from, free, to), следующ. шаг проверка условия 'if', следующ. шаг вызов Towers(number-1, from, free, to), и так до конца стека, каждый раз отнимая от number единицу. доходим до number=0, функция с нолем не срабатывает и идет возврат в вызвавшую функцию, где number=1, следующ. шаг cout<< 1 диск << c 1 стержня << на 2 стержень. НЕПРАВИЛЬНО. При формальном number=3, 1 диск с первого нужно на 3 стержень.
    – Ключ
    2 фев 2012 в 17:18
  • 1
    Кстати для формального number=2, алгоритм работает корректно. Я вот только подумал нужно проследить алгоритм при формальном number=4, то есть тоже с четным колличеством колец, может всплывет чего.
    – Ключ
    2 фев 2012 в 17:23
  • 1
    Чет я ничего не понял. Алгоритм понимаю, пробую по нему переставлять кольца - все правильно. А то что вы пишете в упор не пойму)
    – insolor
    2 фев 2012 в 17:41
  • 1
    insolor, если понимаете алгоритм, напишите пож. мне пошагово, каждую строчку, что после чего происходит.Спасибо.
    – Ключ
    2 фев 2012 в 17:55
  • 2
    В моем ответе все написано. Как еще объяснить я не знаю. Видимо, вы еще не познали рекурсию)
    – insolor
    2 фев 2012 в 18:06
0

Добрый день. Третий день на этой странице у меня нет ссылки "комментировать", поэтому пишу "ответом". Insolor, ведь то, что вы написали в последнем комментарии подчиняется соответствующим правилам, алгоритму, какому то конкретному закону рекурсии, что ли. Вот я и хочу знать эти правила, что бы применив их, ясно представлять, что происходит. Пока нигде не нашел этого правила. Если можно, объясните пожалуйста: "...по аналогии с объектно ориентированным программированием, можно сказать...", в чем эта аналогия? Спасибо.

12
  • 1
    Аналогия с ООП - в том, что как-бы создается новый "экземпляр" функции. Но это только аналогия. Вроде бы нет никаких особых правил нет. Просто если функции foo была вызвана с параметрами 10,1,2 и вызывает "сама себя" с параметрами 9,2,1, то вызванный "экземпляр" получает именно эти параметры (9,2,1) и ничего не знает о параметрах (10,1,2), с которыми была вызвана предыдущая функция. Теперь она снова вызывает сама себя, но уже с параметрами (8,1,2) и снова вызванная функция ничего не знает ни о (10,1,2), ни даже о (9,2,1). Поэтому-то все работает именно так как работает:)
    – insolor
    13 фев 2012 в 12:26
  • 1
    @Ключ, видимо Вы не до конца разобрались с вызовами функций (поэтому с рекурсией проблемы). Советую попечатать (на самом деле printf()) адреса параметров и локальных переменных функции при входе и сразу после возврата из рекурсивного вызова. Посмотрите, как меняются циферки для одного и того же имени и все сразу станет понятно.
    – avp
    13 фев 2012 в 13:17
  • 1
    @Ключ, printf() это функция печати. См. (как всегда) man 3 printf. Если проблемы с использованием man, то читайте вывод man man. Там все написано. Разобраться по другому, ну я не знаю, что именно Вам непонятно в рекурсивном вызове (почему @insolor начал говорить об аналогии с новым экземпляром объекта в ООП). Скажем так, особенность в том, что именам параметров на каждом уровне рекурсии будут соответствовать новые адреса. Т.е. меняете, скажем, параметр x, а в вызывавшей активации этот параметр x не меняется (там у него другой адрес). Или это очевидно ?
    – avp
    15 фев 2012 в 14:07
  • 1
    Вызываем foo(10,1,2) foo(n=10, a=1, b=2), вызывает foo(n-1=9, b=2, a=1) foo(n=9, a=2, b=1), вызывает foo(n-1=8, b=1, a=2) и т.д.
    – alexlz
    16 фев 2012 в 11:23
  • 3
    Переписываем foo void foo(int n, int a, int b) { int w; if(n!=0) { cout<<a<<" "<<b<<endl; w=a; a=b; b=w; foo(n-1,a,b); } } Теперь меняются? Если да, то чем эта функция отличается от оригинала? a теперь всегда 2й параметр, b-3й. Можно убрать обмен локальных a и b, но поменять их порядок в рекурсивном вызове.
    – alexlz
    16 фев 2012 в 13:21

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.