被这道水题郁闷了好久,就像脑子转不过来一样,大致思路有,但是一直不懂得如何实现。
Last(x)表示顺时针方向x位置的上一个有效位置;
Next(x)表示顺时针方向x位置的下一个有效位置(x位置的数字允许已经被删除);
下面的代码中,即使只剩下一个元素也允许调用Last(x)、Next(x),因为此时x位置的数字已经删除,Last(x)、Next(x)将返回仅剩的一个元素的位置;但是不存在元素的时候要及时break循环,否则调用Last(x)、Next(x)会死循环。最初就是这点没有反应过来,写了许多if来判断各种情况,越写越复杂。
以下是我的代码:
#include<cstdio>
using namespace std;
const int kMaxn(27);
int n,k,m,cnt;
int r[kMaxn];
bool sign[kMaxn];
int Last(int pos)
{
int i(pos-1);
if(i<1)
i=n;
while(!r[i])
{
i--;
if(i<1)
i=n;
}
return i;
}
int Next(int pos)
{
int i(pos+1);
if(i>n)
i=1;
while(!r[i])
{
i++;
if(i>n)
i=1;
}
return i;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%d%d%d",&n,&k,&m)==3 && (n || k ||m))
{
for(int i=1;i<=n;i++)
{
r[i]=i;
sign[i]=false;
}
int i(n),j(1),ans[kMaxn];
cnt=0;
while(true)
{
for(int v=1;v<=k;v++)
i=Next(i);
for(int v=1;v<=m;v++)
j=Last(j);
if(i==j)
{
cnt++;
ans[cnt]=r[i];
if(cnt<n)
sign[cnt]=true;
if(cnt>=n)
break;
r[i]=0;
i=Last(i);
j=Next(j);
}
else
{
cnt++;
ans[cnt]=r[i];
cnt++;
ans[cnt]=r[j];
if(cnt<n)
sign[cnt]=true;
if(cnt>=n)
break;
r[i]=r[j]=0;
i=Last(i);
j=Next(j);
}
}
for(int i=1;i<=n;i++)
{
printf("%3d",ans[i]);
if(sign[i])
printf(",");
}
printf("\n");
}
return 0;
}
posted on 2011-04-13 20:46
lee1r 阅读(492)
评论(0) 编辑 收藏 引用 所属分类:
题目分类:基础/模拟 、
题目分类:数据结构