算法分析：

我们先从n=4开始试试看，初始时：

○○○○●●●●

第1步：○○○——●●●○● {—表示空位}

第2步：○○○●○●●——●

第3步：○——●○●●○○●

第4步：○●○●○●——○●

第5步：——○●○●○●○●

如果n=5呢？我们继续尝试，希望看出一些规律，初始时：
  
       ○○○○○●●●●●

第1步： ○○○○——●●●●○●

第2步： ○○○○●●●●——○●

这样，n=5的问题又分解成了n=4的情况，下面只要再做一下n=4的5个步骤就行了。同理，n=6的情况又可以分解成n=5的情况，……，所以，对于一个规模为n的问题，我们很容易地就把他分治成了规模为n-1的相同类型子问题。

戴马：

#include<iostream>
using namespace std;
int n,st,sp;
char c[101];
void print()                                  //打印
{
int i;
if(st < 10) cout<<"step "<<st<<':';
else cout<<"step"<<st<<':';
for (i=1;i<=2*n+2;i++) cout<<c[i];
cout<<endl;
st++;
}
void init(int n)                             //初始化
{
int i;
st=0;
sp=2*n+1;
for (i=1;i<=n;i++) c[i]='o';
for (i=n+1;i<=2*n;i++) c[i]='*';
c[2*n+1]='-';c[2*n+2]='-';
print();
}
void move(int k)                            //移动一步
{
int j;
for (j=0;j<=1;j++)
{
c[sp+j]=c[k+j];c[k+j]='-';
}
sp=k;
print();
}
void mv(int n)                                       //主要过程
{
int i,k;
if (n==4)                //n等于4的情况要特殊处理
{
move(4); move(8); move(2); move(7); move(1);
}
else
{
move(n); move(2*n-1); mv(n-1);
}
}
int main()
{
cin>>n;
init(n);
mv(n);
}