题目链接:
http://www.acdream.net/problem.php?cid=1011&pid=4
题目大意:n个人围一圈坐着,每次每隔一个人有一个人离开圆圈,求最后一个留下人的编号。
解题思路:找规律。
如果n是2^i,则每一圈开始的位置都为1,最后留下的肯定是1,
如果n=2^i+1,则以后每次开始的位置均为3,最后留下的肯定是3,1已经离开圈了
如果n=2^i+2,则以后每次开始的位置均为5,最后留下的肯定是5,此时1,3,已经离开圈了
……
如果n=2^i+a(a<2^i),则最后每次开始的位置均为2*a+1,最后留下的肯定是2*a+1
具体过程详见代码:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int temp=1;
while(n-temp>=temp)
temp*=2; //找到最大的2^i
if(n-temp==0)
printf("1\n"); //如果n=2^i;
else
printf("%d\n",(n-temp)*2+1); //n-temp即为a,剩下的
}
return 0;
}