Проблема проста, закажите 2n (3 ≤ n ≤ 100) пар букв BABABABA, переместив блоки букв (вам всегда нужно переместить пару непрерывных букв в два непрерывных пустых пространства), чтобы получить ожидаемый результат AAAA .... ABBBBB ... BBBB показывает наименьшее количество движений для выполнения
начальная конфигурация бункеров и пустых пространств для n = 4
Мне удалось идентифицировать образец для n ≤ 7
1 - Отметить позицию первого пустого блока (-1 и 0)
2- Отметьте последнюю пару AB как пустую позицию и переместите ее к предыдущему пустому блоку (при условии, что B не образует пару с другим B)
3 - Отметьте первый блок BA, найденный после позиции 1, и переместите его в предыдущий пустой блок.
Повторяйте 2 и 3, пока условие 2 не будет выполнено
Пример моего алгоритма для n = 7:
.. БАБАБАБАБАБАБАБАБА переместить последнюю АБ (с позиции 12 на -1):
ABBABABABABAB..A переместить первый BA (позиции с 3 по 12):
ABBA..BABABABBAA переместить последнюю пару AB, прежде чем пара уже готова (позиции с 8 по 3)
ABBAABBAB..ABBAA переместить первый BA после позиции 1 (позиции с 5 по 8) и упорядочить пары AABB, сформированные
Я включаю свой алгоритм для первой части заказа:
public void emparejarAAyBB(int pos){ // pos = posicion a remplazar
System.out.println("PAREJA AB");
int bloqueAux = tomarUltimoAB();
moverBloque(bloqueAux,pos); // el bloque que fue movido se elimina por lo que se guarda en una variable auxiliar
System.out.println("PAREJA BA");
int bloqueAux2 = tomarPrimerBA();
moverBloque(bloqueAux2,bloqueAux);
if(tomarUltimoAB()!=-1){ // si hay otro bloque AB que cumpla los requisitos se repite el ciclo
emparejarAAyBB(aux2);
}
ordenarParejas(aux2);
}
Этот шаблон действителен только для n ≤ 7, он недействителен для других значений, больших n, поэтому он не решает мою проблему. Я думал о том, чтобы сделать это грубой силой или рекурсивно звучать n> 7 из n несовершеннолетнего, но правда в том, что я застрял в этом.