样例中给出了n==4的情况，先考虑n==5的情况
OOOOO*****__
第一次移动->OOOO__****O*
第二次移动->OOOO****__O*
注意到前面的部分，转换到了n==4的情况，所以想到一个分治算法。
以下是我的代码：
#include<stdio.h>
#include<string.h>
long count=0;
int n;
void swap(char *a,char *b)
{
char t;
t=*a;*a=*b;*b=t;
}
void div(char a[],int len)
{
char t;
if(len>10)
{
printf("step %ld:%s\n",count,a);
swap(&a[len-1],&a[len/2-1]);
swap(&a[len-2],&a[len/2-2]);
count++;
printf("step %ld:%s\n",count,a);
swap(&a[len-3],&a[len/2-1]);
swap(&a[len-4],&a[len/2-2]);
count++;
div(a,len-2);
}
else if(len==10)
{
printf("step %ld:%s\n",count,a);
swap(&a[9],&a[4]); swap(&a[8],&a[3]);
count++;
printf("step %ld:%s\n",count,a);
swap(&a[7],&a[3]); swap(&a[8],&a[4]);
count++;
printf("step %ld:%s\n",count,a);
swap(&a[7],&a[1]); swap(&a[8],&a[2]);
count++;
printf("step %ld:%s\n",count,a);
swap(&a[6],&a[1]); swap(&a[7],&a[2]);
count++;
printf("step %ld:%s\n",count,a);
swap(&a[6],&a[0]); swap(&a[7],&a[1]);
count++;
printf("step %ld:%s\n",count,a);
}
}
int main()
{
int i,len;
char a[205]={0};
scanf("%d",&n);
len=2*n+2;
for(i=0;i<len;i++)
{
if(i<n)
a[i]='O';
else if(i>=n && i<len-2)
a[i]='*';
else
a[i]='_';
}
div(a,len);
// getchar();getchar();
return 0;
}
posted on 2010-01-06 19:35
lee1r 阅读(226)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：递推/递归