Ханойская башня на C++. Итеративный метод

Question

Я изучаю язык С++ по книге, дошла до рекурсии в C++. После главы было задание "Ханойская башня". Проблема заключается в следующем: как решить данную задачу методом рекурсии, я поняла сама, но в книге было предложено решить ту же задачу итеративным методом, и вот с этим возникли проблемы. В целом я поняла, как нужно перекладывать диски в зависимости от четности или нечетности их количества: если четное, то первый диск перекладывается на промежуточный колышек, иначе - на финишный. В процессе решения я пыталась перекладывать, начиная с 1 диска, постепенно увеличивая количество переложенных дисков, так, если нужно переложить 5 дисков с 1-ого на 3-ий колышек, то 1 диск я клала на 3, далее нужно переложить следующий диск из начальной стопки на 2-ой колышек и на него 1 диск, 2 диска переложено, затем кладем 3-ий диск на 3-ий колышек, на него нужно положить те 2 диска, чтобы их переложить, нужно также начинать с одного, и я никак не могла продумать эту идею, никак не выходило в цикле отслеживать сколько мне еще переложить и при этом менять статус колышков(стартовый, промежуточный, финишный). Пыталась найти решение и натыкалась на способы с использованием векторов и массивов, этого в моей книге еще не было, следовательно, мне нужно решить это как-то иначе.

Answer 1

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

Когда решал, то пол дня даже подойти к задаче не мог, но ближе к вечеру понял, что ханойская башня очень сильно похоже на бинарное дерево. Тогда я сменил ракурс направления с Башни на Дерево. Так я провёл два дня в поисках наилучшего обхода бинарного дерева без рекурсии. Но в конце получилось как всегда - за мудрёно и не понятно: Я нашёл такие правила при которых я получаю бинарное дерево на уровень выше и описал это в функции getMove();

Правила просты:

1. проход в левое поддерево
2. подъём с левого поддерева
3. проход в правое поддерево
4. подъём с правого поддерева

Тут надо отметить, что 1 и 2 - это swap(in, tmp), а 3 и 4 - это swap(from, tmp)

Тогда мы получаем, что дерево из 2 уровней будет иметь такое решение 1234, а так как дерево с 3 уровнями два 2-ух уровневых дерева сцепленных узлом, то что бы получить дерево 3 уровня нам надо:

1. Скопировать нынешнее дерево, что бы получить два.
2. Добавить в начало и конец по 1 и 4 соответственно.
3. Добавить в середину 23

Таким образом: 1234 -> 1 1234 23 1234 4; И если сейчас пройтись по правилам, то мы обойдём бинарное дерево. Что бы же напечатать вывод мы должны учесть, что печать будет производиться только на последнем уровне при 1 и 3 , а так же на любом при 2. Теперь у нас есть всё, что бы решить эту задачу.

Теперь, когда мы можем обойти бинарное дерево, то мы можем написать решение задачи:

getMove - возвращает массив действий; count - нужен для хранения длины массивы

int* getMove(int n, int &count) {
int* mas = (int*)malloc(sizeof(int)*count);
mas[0] = 1;mas[1] = 2;mas[2] = 3;mas[3] = 4;
for (int i = 1; i <= n - 2; i++) {
    count = 2;
    count += 4;
    //Изменённый массив
    int tmp = (int)malloc(sizeof(int)  count);
    //Добавляем в начало 1
    tmp[0] = 1;
    for (int i = 1; i <= (count - 4) / 2; i++) {
        tmp[i] = mas[i-1];
    }
    //Добавляем в середину 23
    tmp[count / 2 - 1] = 2;
    tmp[count / 2] = 3;
for (int i = count / 2 + 1; i &lt; count; i++) {
    tmp[i] = mas[i-(count / 2 + 1)];
} 
//Добавляем в конец 4
tmp[count - 1] = 4;

free(mas);
mas = tmp;

}
return mas;
}

Теперь реализуем функции на каждое действие от 1 до 4

void _1(int &level, int &from, int &in, int &tmp) {
swap(in, tmp);
level--;
if (level == 1) print(from, in);
}
void _2(int &level, int &from, int &in, int &tmp) {
swap(in, tmp);
level++;
print(from, in);
}
void _3(int& level, int& from, int& in, int& tmp) {
swap(from, tmp);
level--;
if (level == 1) print(from, in);
}
void _4(int& level, int& from, int& in, int& tmp) {
swap(from, tmp);
level++;
}

И вот мы подобрались к функции, которая производит работу:

void work(int n, int from, int in, int tmp) {
if (n == 1) {
    print(from, in);
    return;
}
int count = 4;
int* arr = getMove(n, count);
int level = n;
for (int i = 0; i < count; i++) {
    switch (arr[i]) {
    case 1: _1(level, from, in, tmp); break;
    case 2: _2(level, from, in, tmp); break;
    case 3: _3(level, from, in, tmp); break;
    case 4: _4(level, from, in, tmp); break;
    default: 
        break;
    }
}
}

Вот main:

int main() { 
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int from = 1;
int in = 3;
int tmp = 2;
int count = 4;
printf("from = %d; in = %d; tmp = %d; count = %d.\n",from, in, tmp, count);
printf("Recursion method.\n");
hanoi(from, in, tmp, count);
printf("------------------\n");
printf("Iterative method.\n");
work(count, from, in, tmp);
system("pause");
return 0;
}

Конечно же можно много чего убрать или добавить, но как говориться - "Работает не трогай".

Answer 2

Вот Вам в помощь отрывок из книги А. Шень. Программирование: теоремы и задачи 2-е изд., М.: МЦНМО, 2004, 296 с. (pdf, 2.1M):

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

Решение.

Вспомним рекурсивную программу, перекладывающую i верхних колец с m на n:

procedure move(i,m,n: integer);
  var s: integer;
begin
  if i = 1 then begin
    writeln (’сделать ход ’, m, ’->’, n);
  end else begin
    s:=6-m-n; {s - третий стержень: сумма номеров равна 6}
    move (i-1, m, s);
    writeln (’сделать ход ’, m, ’->’, n);
    move (i-1, s, n);
  end;
end;

Видно, что задача "переложить i верхних дисков с m-го стержня на n-ый" сводится к трём задачам того же типа: двум задачам с i-1 дисками и к одной задаче с единственным диском. Занимаясь этими задачами, важно не позабыть, что ещё осталось сделать.

Для этой цели заведём стек отложенных заданий, элементами которого будут тройки (i,m,n). Каждая такая тройка интерпретируется как заказ "переложить i верхних дисков с m-го стержня на n-ый". Заказы упорядочены в соответствии с требуемым порядком их выполнения: самый срочный - вершина стека. Получаем такую программу:

procedure move(i,m,n: integer);
begin
  сделать стек заказов пустым
  положить в стек тройку <i,m,n>
  {инвариант: осталось выполнить заказы в стеке}
  while стек непуст do begin
    удалить верхний элемент, переложив его в <j,p,q>
    if j = 1 then begin
      writeln (’сделать ход’, p, ’->’, q);
    end else begin
      s:=6-p-q;
        {s - третий стержень: сумма номеров равна 6}
      положить в стек тройки <j-1,s,q>, <1,p,q>, <j-1,p,s>
    end;
  end;
end;

(Заметим, что первой в стек кладётся тройка, которую надо выполнять последней.) Стек троек может быть реализован как три отдельных стека. (Кроме того, в паскале есть специальный тип, называемый "запись" (record), который может быть применён.)

Answer 3

Если кому интересно с++ версия без стека без массива без рекурсии. Чистая итерация и больше ничего.В книге П.Дейтела еще не изучались массивы для написания итеративной версии. Там надо написать только с помощью итерации.

#include<iostream>
#include<cmath>   
using namespace std;    
int max(int a)            /*возвращает максимальный показатель степени числа 2*/
{                         /*который показывает уровень надстройки*/
    int p = 1,temp, p1;
    while (pow(2, p) <= a)
    {
        temp = pow(2, p);
        if (a % temp == 0 && temp <= a)
                   p1 = p;
        p++;
    }   
    return p1;
}
 int step(int a)  /*возвращает номер позиции для четных номеров*/
{       
    return a / pow(2,max(a));
}
int count_step_define(int a, bool rev_along)/*возвращает номер колышка с которого будет очередной шаг*/
{       
    if (rev_along)
    {   
        int temp = ((step(a) - 1) / 2) % 3;
        if (max(a) % 2 == 0)
            return 1 + temp;
        else
        {
            if(1 - temp == 0)
                    return 3;
            else
                    return 1 - temp > 0? 1 - temp: 2;
        }
    }        
    else
            return 1 + ((a - 1) / 2) % 3;
}
int main()
    {
    unsigned long long n, loop, a = 1;      
    cin >> n;   /*количество дисков*/
    loop = pow(2, n) - 1;   /*количество требуемых перемещений*/    
    while (a <= loop)
    {   
        int temp, over;
        if (a % 2 == 1)
        {               
              temp = count_step_define(a,0);
             (temp + 1 > 3)? over = 1: over = temp + 1;         
        }
        else
        {                
             temp = count_step_define(a,1);
             if (max(a) % 2 == 0)                
                 (temp + 1 > 3)? over = 1: over = temp + 1;              
             else                
                 (temp - 1 < 1)? over = 3: over = temp - 1;             
        }
        cout << temp << " - >" << over << endl;/*с какого и на какой колышек переместить*/
        a++;            
    }       
     system("pause");
    return 0;
    }

Можно сократить код, но он будет вообще трудно понимаемый. Всем терпения...

Answer 4

решил задачу с помощью бинарного дерева, после просмотра этого видео https://www.youtube.com/watch?v=2SUvWfNJSsM&ab_channel=3Blue1Brown Но не смог решить без структур, и массивов. Вот код

    /* hanoi tower itterative */
    #include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
void hanoi(int, int, int);


typedef struct
{
    int index;
    int currentColumnIndex;
} Disc;

int main()
{
    hanoi(3, 3, 1);

    return 0;
}


/* itterative hanoi tower solution */
void hanoi(int discCount, int start, int end)
{
    Disc *discs;  /* Массив который состоит из дисков */

    if( (discs = (Disc *) malloc(discCount * sizeof(Disc)) ) != NULL){

        int fastPow(int, int);
        int getMovedDiscIndex(int);
        int determinant(int, int, int);

        int counter = 1, movedDiscIndex, column, d;

        /* Порядок выполнения программы завсит от четности числа дисков, начального столба и конечного столба */
        /* Функция determinant возвращает 0 или 1, в зависимости которого меняется порядок выполнения программы */
        d = determinant(discCount, start, end);

        for(counter = 0; counter &lt;= discCount - 1; counter++)
        {
            discs[counter].index = counter;
            discs[counter].currentColumnIndex = start;
        }

        counter = 1;

        /* Алгоритм выполнения */
        while(counter != fastPow(2, discCount))     
        {
            /* Рекурсивные вызовы ханойской башни представлют деревоб которое в свою очередь оченб напоминает комбинации
            вссевозможных двоичных чисел. Количество цифр равно количеству дисков, а индекс перемещаемого диска равен индексу
            первой единицы считая с права. Например если число равен 100101100000, то индекс диска который нужно переместить равен 5,
            поскольку начиная с права, первой единицей является пятая цифра․ Когда число достигает значения 2^n - 1,
            выполнение программы завершается */

            movedDiscIndex = getMovedDiscIndex(counter);   /* Находит индекс диска, который нужно переместить */
            column = discs[movedDiscIndex].currentColumnIndex;

            /* В зависимости от количесива дисков, начальных и конечных полржений, диски могут двигаться по разному */
            /* Если индекс перемещаемого диска четное (не четное в другой конфигурации начальных условий), то диск может
               двигаться только на следующий стержень, при достижении последнего стержня, счетчик стержня &quot;cбрасывается&quot;,
               таким образом предотвращается возможность перейти на несуществующий стержень*/

            if(movedDiscIndex % 2 == d)
            {

                column = discs[movedDiscIndex].currentColumnIndex;
                printf(&quot;Move disc %d from %d to %d\n&quot;, movedDiscIndex + 1, column, column + 1 &gt; 3 ? column - 2 : column + 1);
                column += 1;
            }
            else 
            {
                column = discs[movedDiscIndex].currentColumnIndex;
                printf(&quot;Move disc %d from %d to %d\n&quot;, movedDiscIndex + 1, column, column + 2 &gt; 3 ? column - 1 : column + 2);
                column += 2;
            }

            column -= column &gt; 3 ? 3 : 0;
            discs[movedDiscIndex].currentColumnIndex = column;

            ++counter;
        }
    }
    else
        printf(&quot;Can't solve hanoi tower. No memory available\n&quot;);
}


/* Возводит base в степень exponent за Օ(logN) */
int fastPow(int base, int exponent)
{
    if(exponent == 0) return 1;

    return exponent % 2 ? base * fastPow(base, exponent - 1) : fastPow(base * base, exponent / 2);
}

/* Находит индекс первой единицы, в двоичном числе*/
int getMovedDiscIndex(int number)
{
    int movedDiscIndex = 0;

    while(number % 2 != 1)
    {
        number /= 2;
        movedDiscIndex++;
    }

    return movedDiscIndex;
}


/* determinant */
/* В зависимости от конфигурации начальных условий, выбирает вид перемещения - &quot;шагами&quot;, либо &quot;прыжками&quot; */
int determinant(int n, int start, int end)
{
    if(n % 2 == 0)
    {
        if(start == 1 &amp;&amp; end == 2)
            return 1;
        else if(start == 1 &amp;&amp; end == 3)
            return 0;
        else if(start == 2 &amp;&amp; end == 1)
            return 0;
        else if(start == 2 &amp;&amp; end == 3)
            return 1;
        else if(start == 3 &amp;&amp; end == 1)
            return 1;
        else
            return 0;
    }else 
    {
        if(start == 1 &amp;&amp; end == 2)
            return 0;
        else if(start == 1 &amp;&amp; end == 3)
            return 1;
        else if(start == 2 &amp;&amp; end == 1)
            return 1;
        else if(start == 2 &amp;&amp; end == 3)
            return 0;
        else if(start == 3 &amp;&amp; end == 2)
            return 1;
        else
            return 0;
    }
}