Question

C约瑟夫环问题，OJ超时

这是题目
卡片
Time Limit:1000MSMemory Limit:65536KB
Total Submit:141Accepted:93Description
有一叠n张卡片，从上到下依次编号为1～n，从最上面的一张开始按如下的顺序进行操作：把最上面的第一张卡片拿掉，把下一张卡片放在这一叠卡片的最下面；再把最上面的依次重复这样做，直到手中剩下一张卡片。要求：输入不同的n，能输出剩下的这张卡片是原来n张卡片的第几张。

Input

第1行：一个整数T（1≤T≤10）为问题数。
每组测试数据一行：包含一个正整数n(5≤n≤200)。

Output

对于每个问题，输出一行问题的编号（0开始编号，格式：case #0: 等）。
然后在一行中输出一个整数，即最后剩下的卡片的编号。

这是我写的代码，提交后超时，不知道为什么，求助各位
#include<stdio.h>
int main()
{
int t,ii;
int n,i,m,count;
int a[200];
scanf("%d",&t);
for(ii=0;ii<t;ii++)
{
scanf("%d",&n);
m=1;
count=n;
for(i=0;i<=n;i++)
a[i]=1;
i=1;
printf("case #%d:\n",ii);
while(count>1)
{
if(a[i]==1)
{
if(m==1)
{
a[i]=0;
count--;
m=0;
}
else
m=1;
}
i++;
if(i>n)
i=1;
}
for(i=1;i<=n;i++)
{
if(a[i]!=0)
printf("%d\n",i);
}
}
return 0;
}

Answer 1

这种问题，一般模拟法的话超时概率比较大。因为循环太多了。其实这个问题有规律的，用你自己的程序打出来看一下就明白了，给你几幅图你就了解了。

可以发现，当n增大1时，编号增大2,，然后还有号码重置的临界点：

可以发现，当n=剩下的编号时，下一个数编号会从2重新开始，而重置时的编号，一个是64，一个是128。

玩计算机的话，应该对64和128很敏感才是，64是2的6次方，128是2的7次方。

也就是说，当2^k<n<=2^(k+1)时，答案就是(n-2^k)*2。