Ханойская башня на С++

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

Решите эту задачу рекурсивным методом. Напишите функцию SolveHanoi, которая принимает ссылку на вектор из трёх стержней-башен. На первой башне надето определённое количество дисков — не обязательно восемь, как в классической задаче. Количество можно узнать, воспользовавшись методом GetDisksNum. Класс Tower уже имеет некоторые методы или части методов. Другие методы вы можете дописывать так, как вам нужно для решения. В результате работы функции SolveHanoi все диски в правильном порядке должны оказаться на третьей башне.

Чтобы решить задачу, вспомните, что во все методы класса неявно передаётся указатель на объект this. А если применить оператор *, можно получить доступ к самому элементу.

Пример использования

int main() {

int towers_num = 3;

int disks_num = 3;

vector towers;

// добавим в вектор три пустые башни

for (int i = 0; i < towers_num; ++i) {

towers.push_back(0);

}

// добавим на первую башню три кольца

towers[0].SetDisks(disks_num);

SolveHanoi(towers);

}

Пример результата работы

Ниже не пример вывода на экран — в задаче он не требуется. Это пример того, что должно произойти с вектором башен после вызова SolveHanoi:

Вектор башен до перемещения:

Башня 1: 3 2 1

Башня 2: 0 0 0

Башня 3: 0 0 0

Вектор башен после перемещения:

Башня 1: 0 0 0

Башня 2: 0 0 0

Башня 3: 3 2 1

Заготовка программы

#include

#include

#include

using namespace std;

class Tower {

public:

// конструктор и метод SetDisks нужны, чтобы правильно создать башни

Tower(int disks_num) {

FillTower(disks_num);

}

int GetDisksNum() const {

return disks_.size();

}

void SetDisks(int disks_num) {

FillTower(disks_num);

}

// добавляем диск на верх собственной башни

// обратите внимание на исключение, которое выбрасывается этим методом

void AddToTop(int disk) {

int top_disk_num = disks_.size() - 1;

if (0 != disks_.size() && disk >= disks_[top_disk_num]) {

throw invalid_argument("Невозможно поместить большой диск на маленький");

} else {

// допишите этот метод и используйте его в вашем решении

}

}

// вы можете дописывать необходимые для вашего решения методы

private:

vector disks_;

// используем приватный метод FillTower, чтобы избежать дубликации кода

void FillTower(int disks_num) {

for (int i = disks_num; i > 0; i--) {

disks_.push_back(i);

}

}

};

void SolveHanoi(vector& towers) {

int disks_num = towers[0].GetDisksNum();

// допишите функцию, чтобы на towers[0] было 0 дисков,

// на towers[1] 0 дисков,

// и на towers[2] было disks_num дисков

}