Привет всем, снова. Простите меня за появление с глупыми вопросами, но хочу обучиться и обратиться не к кому :)
P.S. Спасибо всем за помощь, которую предоставили и предоставят.
Я учу сейчас рекурсию и дошел до задачи ханойские башни. К моему сожалению, я не умею еще писать рекурсию быстро и правильно. Я разобрал эту задачу и прошу вас сказать, правильное ли это решение. Ответы смотреть не хочу, т.к. считаю, что самостоятельный разбор — более эффективен, нежели просмотра ЛКШ лекций и тому подобного.
Я придумал примерно такое решение задачи: Будем перекладывать на диск 3 или 1 ( зависит от того, с какого диска мы перекладываем ) пирамиду высотой n-1, при этом используя второй стержень как вспомогательный, для формирования башни на другом стержне.
У меня возникли такие вопросы:
1) Будет ли этот метод решать задачу за минимальное кол-во перекладывания?
2) Как хранить в каком месте находится как пирамида? ( Я лишь предположил создать массив из трех элементов, но дальше ничего не придумал :( )
3) Да и вообще, будет ли работать мое решение?
4) Если этот алгоритм решения верный, то он будет работать за O(n^2-1)?
P.P.S. Знаю, самый толковый совет: "Напиши и проверь", но вернусь к началу — я не умею писать такую сложную, для меня, рекурсию.
Рекурсивный подход к перекладыванию пирамидки из N блинов:
В качестве базы рекурсии можно взять случай 0 блинов, при котором можно просто ничего не делать. Фактические номера стартового, вспомогательного и конечного стержней будут параметрами рекурсии.
Выбранная вами задача немного осложняется необходимостью выводить номер перекладываемого блина. Для решения этой проблемы можно, например, сделать массив из трёх стеков, чтобы в шаге 2 извлекать диаметр из стека[номерСтартовогоСтержня] и перекладывать в стек[номерКонечногоСтержня].
Разумеется, этот алгоритм работает за 2N - 1, однако можно показать, что меньшим количеством действий обойтись не удастся.
Действительно, пусть M(N) — минимальное количество действий для переноса N блинов. Самый большой блин перенести можно будет только тогда, когда все меньшие блины окажутся на промежуточном стержне, т. е. будет выполнено как минимум M(N - 1) ходов. Ещё за один ход перекладывается самый большой блин. Теперь нужно положить на него меньшие блины, для чего потребуется ещё как минимум M(N - 1) ходов. Итого M(N) ≥ 2 * M(N - 1) + 1, M(0) = 0. Нетрудно убедиться, что данное рекурсивное соотношение раскрывается как раз как 2N - 1.