樣例中給出了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 閱讀(253)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：遞推/遞歸