Задача о Ханойских башнях... (с первого взгляда простая...)

[creative]

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

Задачка такова: имеются три шеста - первый(начальный) второй(дополнительный) и третий(конечный).
На начальном шесте имеется n-ое количество(на практике не больше 10:)) колец, причём размер каждого следующего кольца к верху башни убывает. Необходимо переместить всю башню из колец с первого шеста на третий, используя второй как дополнительный шест. Условие: кольца с большим размером не должны перемещаться на кольца с меньшим размером.

Решение на языке Си:

Код: Выделить всё

/*  ханойские башни  */
   #include <stdio.h>
   main()                               /* вызывающая */
   {   void tn(int, int, int, int);     /* функция*/
       int n;
       scanf(" %d",&n);
       tn(n,2,3,1);
    }

    void tn(int n, int i, int j, int w) /* рекурсивная */
    {  if (n>1)                         /* функция */
        {  tn (n-1,i,w,j);
           tn (1,i,j,w);
           tn (n-1,w,j,i);
         }
        else printf(" \n %d -> %d",i,j);
        return;
    }

P.S. задачку подкинули в универе, решение я нашёл, но тока никак понять не могу

[nonstop]

а почему с двойки начинается?
вот так, наверное, правильнее будет:

Код: Выделить всё

tn(n,1,3,2);

алгоритм простой, собственно три подряд вызова tn его и реализуют
1 - с i на w (для переноса возможна рекурсия)
2 - с i на j (всегда)
3 - с w на i (для переноса возможна рекурсия)

Код: Выделить всё

#include <stdio.h>

/**
 *  пример: на первом шесте 2 диска (2 диска перекладываются за 3 действия)
 *  1 - переносим диск с шеста 1 на шест 2
 *  2 - переносим диск с шеста 1 на шест 3
 *  3 - переносим диск с шеста 2 на шест 3
 * */
void tn(int n, int i, int j, int w)
{
    if (n > 1)
    {
        tn(n - 1, i, w, j);
        printf(" %d -> %d\n", i, j);
        tn(n - 1, w, j, i);
    }
    else
        printf(" %d -> %d\n", i, j);
    return;
}

int main()
{
    int n;
    scanf(" %d", &n);
    tn(n, 1, 3, 2);
}

[creative]

Спасибо
буду разбираться =)

[/dev/random]

Или нерекурсивный способ:

Чередуются два типа ходов: перемещаем самый маленикий диск (в раз и навсегда выбранном направлении, напр. 1->2->3->1), затем делаем единственно возможный ход, при котором маленький диск не затрагивается, затем опять двигаем маленький в том же направлении и т.д.

Направление для маленького диска: если всего дисков четное количество, то 1->2->3->1, иначе 1->3->2->1.

[creative]

спасибо, интересненько