Ханойская башня с использованием рекурсии

Question

Понятия не имею о Ханойская башня . Я хочу написать программу для этого с использованием рекурсии.

Answer 1

Еще одно домашнее задание. Передай мне свой учитель А;)

Источник: http://www.soc.napier.ac.uk/~andrew/hanoi/rechelp.html
Бонус: пошаговое видео на YouTube .

---

Немного о Ханойской башне

Анализ этого и обсуждение (изобретенной) мифологии и версии с четырьмя колышками можно найти в rec.puzzles FAQ ищите индукция / hanoi.s

У проблемы Ханойской башни есть хорошее рекурсивное решение.

Разработка рекурсивных решений

Чтобы решить такие проблемы, спросите себя: «Если бы я раскрыл дело n-1 , мог бы я решить дело n ?»

Если ответ на этот вопрос положительный, вы исходите из возмутительного предположения, что дело n-1 было раскрыто. Как ни странно, это работает, если есть некоторый базовый случай (часто, когда n равен нулю или единице), который можно рассматривать как особый случай.

Как переместить n колец с полюса A на полюс C?

Если вы знаете, как переместить n-1 колец с одного полюса на другой, просто переместите n-1 колец на запасной полюс - остается только одно кольцо на полюс источника теперь просто переместите его в пункт назначения, а затем сложите остальные из запасного полюса в столб назначения.

Например, когда n равно 4 ...

Сначала переместите три на запасной столб (подумайте, как это сделать позже).

Теперь переместите одно кольцо от полюса источника к полюсу назначения.

Теперь переместите три кольца от запасного полюса к полюсу назначения
(опять же, мы можем беспокоиться о том, как сделать это позже).

Мы закончили!

Более кратко ...

Для перемещения n колец из А в С, используя В в качестве запасного:

• , если n равно 1
  • просто сделай это,
• в противном случае ...
  • переместить n-1 колец от A до B, используя C как запасной
  • переместить одно кольцо от А до С
  • переместить n-1 кольца от B до C, используя A в качестве запасного

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

Как это сделать в C

/* Tower of Hanoi - the answer */
/* How to move four rings from pin 1 to pin 3 using pin 2 as spare */
#include <stdio.h>

void move(n, A, C, B)
  /* number to move, source pole, destination pole and
     spare pole respectively */
  int n, A, B, C; {
    if (n == 1) {
      printf("Move from %d to %d.\n", A, C);
    } else {
      move(n - 1, A, B, C);
      move(1, A, C, B);
      move(n - 1, B, C, A);
    }
  }

  main() {
    move(4, 1, 3, 2);
  }

Answer 2

Вот компактная реализация на Лиспе: http://www.kernelthread.com/projects/hanoi/html/gcl.html. Это, конечно, рекурсивно, но я не проверял, что это правильно.

Answer 3

#!/usr/bin/env python
discs = 3
T = [range(discs, 0, -1), [], []]

def show_towers():
    """Render a picture of the current state of the towers"""
    def render_disc(t, y):
        return ("-"*(t[y]*2-1) if y < len(t) else "|").center(discs*2)

    for y in range(discs):  
        print " ".join(render_disc(t, discs-y-1) for t in T)
    print "="*(discs*6+3)


def move(n, source, destination):
    """Recursively move n discs from source to destination"""
    while n > 0:
        temp = 3 - source - destination 
        move(n-1, source, temp)
        T[destination].append(T[source].pop())
        show_towers() 
        n, source = n-1, temp    # Simulate tail recursion


show_towers()
move(discs, 0, 2)

выход для дисков = 3

  -      |      |   
 ---     |      |   
-----    |      |   
=====================
  |      |      |   
 ---     |      |   
-----    |      -   
=====================
  |      |      |   
  |      |      |   
-----   ---     -   
=====================
  |      |      |   
  |      -      |   
-----   ---     |   
=====================
  |      |      |   
  |      -      |   
  |     ---   ----- 
=====================
  |      |      |   
  |      |      |   
  -     ---   ----- 
=====================
  |      |      |   
  |      |     ---  
  -      |    ----- 
=====================
  |      |      -   
  |      |     ---  
  |      |    ----- 
=====================

Answer 4

Из Википедия :

Ханойская башня или Ханойские башни (также известный как Башни Брахмы) это математическая игра или головоломка Это состоит из трех стержней и ряда дисков разных размеров, которые могут скользить на любой стержень. Головоломка начинается с дисками аккуратно сложены в порядке размером на один стержень, самый маленький в вершина, таким образом, делая коническую форму.

Ознакомьтесь с рекурсивным решением .

Answer 5

См. статью из Википедии Ханоя статью для описания рекурсивного алгоритма.

Это выглядит примерно так:

#include <iostream>   // ostream
#include <algorithm>  // for_each
#include <deque> // I can iterate over towers & print state,<stack> works as well
#include <boost/array.hpp>   // just a wrapper for array
#include <boost/lambda/lambda.hpp>  // easy one line for_each iterating

using namespace std;

typedef std::deque< int > tower_t;  // stack works as well, deque for printing
typedef boost::array< tower_t ,3 > towers_t;  // 3 towers

enum peg { A = 0, B = 1, C = 2 };

---

Печать:

ostream & show(ostream & os, const tower_t & t)
{
    os << "[";
    for_each (t.begin(), t.end(), os << boost::lambda::_1 );
    return os << "]";
}

ostream & show(ostream & os, const towers_t & t)
{
    show(os, t[0]); show(os, t[1]); show(os, t[2]);
    return os;
}

---

Решите:

void move(peg from, peg to, towers_t & t)
{
    // show move and state before move
    cout << "mv: " << t[from].back() << " " << from << " --> " << to << "\t\t";
    show(cout, t); cout << " --> ";

    // the actual move: move top peg `from` stick `to` stick (and `pop` old top)
    t[to].push_back(t[from].back());
    t[from].pop_back();

    // show state after move
    show(cout, t); cout << endl;
}

// move n discs from A to B via C
void move(int n, peg from, peg to, peg via, towers_t & t)
{
    if (n == 1) { move(from, to, t); return; }

    move(n-1, from, via, to, t);
    move(from, to, t);
    move(n-1, via, to, from, t);

    return;
}

---

Использование, решить башню с 4 колышками:

int main()
{
    towers_t ttt;
    tower_t & first_tower(ttt[0]);
    first_tower.push_back(4);
    first_tower.push_back(3);
    first_tower.push_back(2);
    first_tower.push_back(1);

    move(first_tower.size(), A, C, B, ttt); // move n from A to C via B
}

Решено 3 башни с 4 колышками на первой башне, самый большой колышек имеет наибольшее число, самый маленький - 1.

Вывод (mv: PegX FromTower ---> ToTower), за которым следует состояние до и после перемещения, каждая башня слева направо показывает колышки снизу вверх - сверху справа:

mv: 1 0 --> 1       [4321][][] --> [432][1][]
mv: 2 0 --> 2       [432][1][] --> [43][1][2]
mv: 1 1 --> 2       [43][1][2] --> [43][][21]
mv: 3 0 --> 1       [43][][21] --> [4][3][21]
mv: 1 2 --> 0       [4][3][21] --> [41][3][2]
mv: 2 2 --> 1       [41][3][2] --> [41][32][]
mv: 1 0 --> 1       [41][32][] --> [4][321][]
mv: 4 0 --> 2       [4][321][] --> [][321][4]
mv: 1 1 --> 2       [][321][4] --> [][32][41]
mv: 2 1 --> 0       [][32][41] --> [2][3][41]
mv: 1 2 --> 0       [2][3][41] --> [21][3][4]
mv: 3 1 --> 2       [21][3][4] --> [21][][43]
mv: 1 0 --> 1       [21][][43] --> [2][1][43]
mv: 2 0 --> 2       [2][1][43] --> [][1][432]
mv: 1 1 --> 2       [][1][432] --> [][][4321]

Answer 6

Видео-лекции Структура и интерпретация компьютерных программ содержат полезные советы по решению этой проблемы, а также множество знаний.