这道算法题的公式是什么?把由n个连续的A和n个连续的B(200≥n≥4)组成的字符串通过字符移动操作变成AB相间的字符串.移动规则为：每次移动以两个相邻字符为单位,这两个相邻字符之间的顺序

Question

这道算法题的公式是什么?
把由n个连续的A和n个连续的B(200≥n≥4)组成的字符串通过字符移动操作变成AB相间的字符串.移动规则为：每次移动以两个相邻字符为单位,这两个相邻字符之间的顺序以及其它字符之间的顺序不得改变.举例如下：
AAAABBBB →AAA##BBBAB→AAABB##BAB→A##BBAABAB→ABAB##ABAB→ABABABAB
其中,“#”代表空出的位置.
求最少的移动步数.

Answer 1

最少的移动步骤不清楚,但以下方法可以达到目的——
反过来思考,将AB相间的字符串,每次移动2个相邻字符,最后弄成n个连续的A和n个连续的B的字符串,那就很容易了.例如ABABABAB,只要每次将最后的“AB”,插入第二个“B”的前面就行：
ABABABAB→AABBABAB→AAABBBAB→AAAABBBB
总共要移动n-1对AB,所以可以n-1步达到目的