Расширенная Ханойская башня
Определение проблемы
Я пытаюсь написать программу на C ++, чтобы решить Extended Hanoi Tower проблема.
Расширенная Ханойская башня похожа на стандартную проблему Ханоя. Разница в том, что нечетные кольца в (1, 3, 5, …) и четные кольца находятся в В (2, 4, 6, …). Вопрос состоит в том, как мы можем перевести все кольца в С в рекурсивный путь?
Я написал то, что я сделал до сих пор.
Буду признателен за любую помощь, позволяющую мне реализовать мой подход, или за любые идеи по реализации программы!
Спасибо !
правила
1. Одновременно можно перемещать только один диск.
2. Запрещается размещать диск поверх меньшего диска.
3. Выходные данные должны содержать необходимые шаги, а не минимальный необходимые ходы
4. Общее количество дисков может быть четным или нечетным.
5. Реализация должна быть рекурсивной.
Подход 1
мы предполагаем, что проблема была решена для n-1 колец, которые в настоящее время находятся в A и B. Это означает, что они все перемещены в C и C имеют 2n-2 упорядоченных колец. После этого мы должны обработать оставшиеся кольца в & B. Это означает, что мы должны взять меньшее кольцо и поместить его на большее кольцо (от B до A). После этого мы должны объединить кольца в C (2n-2) и кольца в A (2). Наконец, мы должны использовать стандартное решение Ханоя, чтобы достичь нашей цели и переместить все кольца в C.
Реализация 1
int main()
{
long int n;
cin >> n;
// move odd & even rings to the first shaft, recursively
customHanoi(n);
// move all rings from first shaft to the destination shaft, recursively
standardHanoi(n);
return 0;
}
// the shaft holds the odd rings: A
// the shaft holds the even rings: B
// the final destination shaft: C
void customHanoi(int n, char A, char B, char C)
{
if (n == 1)
return;
else if (n == 2)
{
cout << B << " " << A << endl;
return;
}
else if (n == 3)
{
cout << A << " " << C << endl;
cout << B << " " << A << endl;
cout << C << " " << A << endl;
}
else
{
// here we have some missing code !
}
}
// a recursive function to find the solution for standard hanoi
void standardHanoi(int n, char from, char helper, char to)
{
// the base condition
if (n == 1)
{
cout << from << " " << to << endl;
return;
}
// the recursive calls
standardHanoi(n - 1, from, to, helper);
cout << from << " " << to << endl;
standardHanoi(n - 1, helper, from, to);
}
Связанные ресурсы
Ссылка на сайт
Решение
Мы можем поставить 1 от А до 2 на Б.
Мы можем поставить 1,2 от B над 3 на A по стандарту Ханоя. Все остальные диски больше и могут быть проигнорированы.
Мы можем поставить 1,2,3 от A над 4 на B по стандарту Ханоя. Все остальные диски больше и могут быть проигнорированы. ……..
Когда мы расположили все диски на одном полюсе, они либо на A (если общее количество дисков было нечетным), либо на B (четное).
Переместите их всех в C по стандартному Ханое.
Хотя это может считаться итеративным подходом, в то время как вы просили рекурсивный.
Итак, рекурсивно: предположим, что есть n Всего дисков. Переехать n-1 диски на C путем рекурсивного применения. Переехать n-1 диски от С до А (n странный) или B (n Равномерно) по стандарту Ханоя. Переместить получившийся n диски на C по стандарту Ханоя.
Это очень похоже на то, что вы предложили, кроме n обозначает общее количество дисков (колец). Это также не является чисто рекурсивным.
Другие решения
Большое спасибо @ Will-Ness !!
Это одно из возможных решений.
Надеюсь это поможет ! 🙂
#include <iostream>
using namespace std;
// function declarations
void customHanoi(long int, char = 'A', char = 'B', char = 'C');
void standardHanoi(long int, char = 'A', char = 'B', char = 'C');
int main()
{
// initialize the variable
long int n;
// getting the number of rings
cin >> n;
// move odd & even rings to the first shaft, recursively
// after that move all rings from first shaft to the destination shaft
customHanoi(n);
// our program finished successfully
return 0;
}
// A: the shaft that holds odd rings
// B: the shaft that holds even rigns
// C: the final destination shaft
void customHanoi(long int n, char A, char B, char C)
{
// initialize the variable
static long int level = 1;
// we can't handle zero/negative disk
if (n < 1)
return;
// the base condition of recursion
if (level == n)
{
// now, we moved all rings to the first shaft
// so, we have to move them to the destination shaft
standardHanoi(n);
// finish the execution of recursion
return;
}
// reordering the disks
// based on even or odd number of disks & current level
if (n % 2 == 1)
{
if (level % 2 == 1)
standardHanoi(level, A, C, B);
else
standardHanoi(level, B, C, A);
}
else
{
if (level % 2 == 1)
standardHanoi(level, B, C, A);
else
standardHanoi(level, A, C, B);
}
// go to the next level, it helps us control the flow
level++;
// the recursive calls
customHanoi(n);
}
// a recursive function to find the solution for standard hanoi
void standardHanoi(long int n, char from, char helper, char to)
{
// the base condition
if (n == 1)
{
cout << from << " " << to << endl;
return;
}
// the recursive calls
standardHanoi(n - 1, from, to, helper);
cout << from << " " << to << endl;
standardHanoi(n - 1, helper, from, to);
}