Мне удалось придумать алгоритм (логический) для решения k-peg-решения проблемы Ханойской башни, но когда я реализовал свой код, у меня возникла ошибка сегментации.
void move(int number_of_disks, int source, int dest, vector <int> free_peg, int pointer)
{
int p;
if (1 == number_of_disks)
{
moves++;
move_top_disk (source, dest);
}
if(free_peg.size() > 2)
p = number_of_disks/2;
else
p = number_of_disks - 1;
moves++;
//Move top "p" disks from peg 1 to peg i
move(p, source, free_peg.back(),free_peg, pointer);
//Move "n - p - 1" disks from peg 1 to another peg
move(number_of_disks - p - 1, source, free_peg[pointer--], free_peg, pointer++);
//Move the "last disk" from the source peg to the destination
move_top_disk(source, dest);
//Move "n - p - 1" disks from peg (i - 1) to the final peg
move(number_of_disks - p - 1, free_peg[pointer--], dest, free_peg, pointer++);
//Move "p" disks from peg i to the destination
move(p, free_peg.back(), dest, free_peg, pointer);
}
Идея довольно проста: я держу вектор свободных колышков (или башен) и обновляю их, когда перемещаю свои диски. Так что для случая 6 колышков и n дисков у меня есть один источник, один пункт назначения и 4 свободных колышка. Идея состоит в том, чтобы переместиться (n — p), где p ~ n / 2, от источника к free_peg [3] (четвертый свободный колышек). Теперь у меня есть только 3 свободных колышка в моем векторе, я использую эти 3 свободных колышка для перемещения (n — p — 1) дисков в free_peg [2], а затем перемещаю последний диск из источника в место назначения. Так что теперь у меня есть 2 бесплатных колышка и 1 источник = 3 бесплатных колышка. Затем мне нужно переместить (n — p — 1) дисков из peg [2] в место назначения, используя 3 свободных колышка (включая исходный, который теперь свободен). Наконец, переместите p дисков из free_peg [3] в место назначения, используя 4 свободных колышка. Однако, когда я реализую это в своем коде, я получаю ошибку сегментации, может кто-нибудь помочь мне с этим?
Мне удалось решить общее решение k-peg, спасибо за помощь. Вот как работает алгоритм:
void move(int number_of_disks, int source, int dest, vector <int> free_peg)
{
int p, middle, g;
if (1 == number_of_disks)
{
moves++;
move_top_disk (source, dest);
}
else
{
moves++;
if(free_peg.size() >= 2)
p = number_of_disks/2;
else
p = number_of_disks - 1;
//Move top "p" disks from peg 1 to peg i
middle = free_peg.back();
free_peg.pop_back();
free_peg.push_back(dest);
move(p, source, middle,free_peg);
//Move "n - p " disks from peg 1 to another peg
free_peg.pop_back();
move(number_of_disks - p, source, dest, free_peg);
//Move p from current peg to the final peg
free_peg.push_back(source);
move(p, middle, dest, free_peg);
}
}
Других решений пока нет …