#include<iostream>
#include<vector>
using namespace std;
int Jhpx(vector<int>*,int,int*);
int main()
{
vector<int>n;
int x=0,pd=0; //x統計下次所須的循環數，pd判斷第壹個是存還是丟棄
//如果pd=0，則第壹張丟棄，反之保存
cout<<"請輸入牌的張數：";
cin>>x;
for (int a=1;a<=x;a++)
{
n.push_back(a); //順序賦值：1至x;
}
while (true)
{
x=Jhpx(&n,x,&pd);
if (x==1)
{
cout<<"最後留下的那壹張牌為原來的 "<<n[0]<<" 號牌"<<endl;
break;
}
}
return 0;
}
int Jhpx(vector<int> *P,int x,int *pd)
{
int temp=0,save=0,del=0; //save存的次數，del刪的次數
vector<int>tmp; //臨時交換用
if (*pd==0) //第壹張丟棄
{
for (int a=1;a<=x;a++)
{
temp=a-1;
if (a%2>0) //如果為單數則丟棄
{
(*P)[temp]=0;
del++;
}
else //反之臨時存儲
{
tmp.push_back((*P)[temp]);
(*P)[temp]=0;
save++;
}
}
for (int b=0;b<save;b++) //臨時存儲中取出到原容器
{
(*P)[b]=tmp[b];
}
if (del>save) //這裏判斷接下來壹圈的第壹張是否丟棄
{
*pd=1;
}
else
{
*pd=0;
}
}
else //第壹張保存
{
for (int a=1;a<=x;a++)
{
temp=a-1;
if (a%2==0)
{
(*P)[temp]=0;
del++;
}
else
{
tmp.push_back((*P)[temp]);
(*P)[temp]=0;
save++;
}
}
for (int b=0;b<save;b++)
{
(*P)[b]=tmp[b];
}
if (del>save)
{
*pd=1;
}
else
{
*pd=0;
}
}
return save;
}