Ханойские башни без рекурсии.

[alexu007]

В сети много реализаций задачи "Ханойские башни", все они с использованием рекурсии. И так же много вопросов об алгоритме без рекурсии - все большинство без ответов. Решил восполнить этот пробел для счастливых студентов, изучающих Qt:

Код:

#ifndef WIDGET_H
#define WIDGET_H

#include <QWidget>
//#include <QMessageBox>


QT_BEGIN_NAMESPACE
namespace Ui { class Widget; }
QT_END_NAMESPACE

class Widget : public QWidget
{
    Q_OBJECT

public:
    Widget(QWidget *parent = nullptr);
    ~Widget();

    int vin;
    int cx_move;
    int schet[3];

    QList<int> sticst;

    void print_table();

private:
    Ui::Widget *ui;

public slots:
    void onPress_pbtn_01();
    void onPress_pbtn_02();

};
#endif // WIDGET_H

Код:

#include "widget.h"
#include "ui_widget.h"

// http://algolist.manual.ru/maths/combinat/hanoi.php

Widget::Widget(QWidget *parent)
    : QWidget(parent)
    , ui(new Ui::Widget)
{
    ui->setupUi(this);

    // подготовка таблицы
    ui->tableWidget->setSelectionMode(QAbstractItemView::NoSelection);

    ui->tableWidget->setColumnWidth(0, 60);
    ui->tableWidget->setColumnWidth(1, 10);
    ui->tableWidget->setColumnWidth(2, 60);
    ui->tableWidget->setColumnWidth(3, 10);
    ui->tableWidget->setColumnWidth(4, 60);

    // инициализация таблицы
    for(int row = 0; row < 7; row++)
        for(int col = 0; col < 5; col++)
        {
            QTableWidgetItem *item = new QTableWidgetItem;
            item->setTextAlignment(Qt::AlignCenter);
            ui->tableWidget->setItem(row, col, item);
        }


    QObject::connect(ui->pbtn_01,SIGNAL(clicked()),this,SLOT(onPress_pbtn_01()));
    QObject::connect(ui->pbtn_02,SIGNAL(clicked()),this,SLOT(onPress_pbtn_02()));
}





Widget::~Widget()
{
    delete ui;
}




// set
void Widget::onPress_pbtn_01()
{

    QString str = ui->lineEdit->text();
    int cx_disks = str.toInt();

    if(cx_disks < 0 || cx_disks > 7)
    {
        ui->label->setText("error");
        return;
    }

    ui->label->setText("0");

    cx_move = 0;

    schet[0] = 1;
    schet[1] = 0;
    schet[2] = 2;

    if(cx_disks % 2)
    {
        schet[0] = 2;
        schet[2] = 1;
    }

    int k = 0;

    for(int i = cx_disks; i > 0; i--)
    {
        k *= 10;
        k += i;
    }

    vin = k;

    sticst.clear();
    sticst << k << 0 << 0;

    print_table();
}





// move
void Widget::onPress_pbtn_02()
{
    int x1, x2;
    int k = 0;

    // конец игры
    if(sticst.at(2) == vin) return;

    // нечётные ходы делает только диск №1
    // по алгоритму в schet[]
    if(!(cx_move % 2))
    {
        // поиск диска №1
        for(int i = 0; i < 3; i++)
        {
            if(sticst.at(i) % 10 == 1)
            {
                k = i;
                break;
            }
        }

        x1 = schet[cx_move % 3];
        sticst[x1] *= 10;
        sticst[x1] += sticst.at(k) % 10;
        sticst[k] /= 10;
    }

    // чётные ходы делает наименьший диск не считая 1-го
    // в единственное доступное место
    else
    {
        // поиск наименьшего диска
        x1 = 10;
        for(int i = 0; i < 3; i++)
        {
            x2 = sticst.at(i) % 10;
            if(x2 == 0 || x2 == 1) continue;

            if(sticst.at(i) % 10 < x1)
            {
                x1 = sticst.at(i) % 10;
                k = i;
            }
        }

        // поиск доступного хода
        x1 = sticst.at(k) % 10;

        for(int i = 0; i < 3; i++)
        {
            x2 = sticst.at(i) % 10;
            if(x2 == 0 || x1 < x2 )
            {
                sticst[i] *= 10;
                sticst[i] += x1;
                sticst[k] /= 10;
                break;
            }
        }
    }

    cx_move++;

    ui->label->setNum(cx_move);
    print_table();
}





void Widget::print_table()
{

    int pos;

    // очистка таблицы
    for(int row = 0; row < 7; row++)
        for(int col = 0; col < 5; col++)
        {
            ui->tableWidget->item(row, col)->setText("");
            ui->tableWidget->item(row, col)->setBackgroundColor(Qt::white);
        }

    // вывод на экран по столбикам
    for(int i = 0; i < 3; i++)
    {
        pos = sticst.at(i);
        QString str  = QString::number(sticst.at(i));
        int ln = str.length();

        for(int row = 0; row < ln; row++)
        {
            int x = pos % 10 - 1;
            if(pos > 0)
            {
                ui->tableWidget->item(row+7-ln, i*2)->setText(QString::number(x+1));
                ui->tableWidget->item(row+7-ln, i*2)->setBackgroundColor(Qt::GlobalColor(x+7));
            }

        pos /= 10;
        }
    }
}