设2n张牌分别标记为1, 2, ..., n, n+1, ..., 2n，初始时这2n张牌按其标号从小到大排列。经一次洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ..., 2n, n。即前n张牌被放到偶数位置2, 4, ..., 2n，而后n张牌被放到奇数位置1, 3, ..., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的n的值(n≤10^5)，最少需要经过多少次洗牌可恢复到初始状态。
输入输出格式
输入数据由多组数据组成。每组数据仅有一个整数，表示n的值。
对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。
样例输入
10
样例输出
6
程序代码如下：
#include <iostream>
void main()
{
int i,j,k=0,p1,p2,n,*s1,*s2;
printf("输入n:");
scanf("%d",&n);
p1=1;p2=n+1; //p1指向第一张牌，p2指向第n+1张牌
s1=(int *)malloc(2*(sizeof(int)*(n+1))); //为数组s1动态申请2*(n+1)个空间
s2=(int *)malloc(2*(sizeof(int)*(n+1))); //为数组s2动态申请2*(n+1)个空间
//s1=new int[2*n+1];
//s2=new int[2*n+1];
for(i=1;i<=2*n;i++)
s1[i]=i; //牌的初始化,将其按编号存储到S1数组国
while(1)
{
for(i=1;i<=2*n;i++) //根据洗牌规则将s1中的数搬到s2中
{
if(i%2!=0)
s2[i]=s1[p2++];
else
s2[i]=s1[p1++];
}
p1=1;p2=n+1;k++; //洗完一次牌后,p1,p2复位,洗牌的次数加1
for(j=1;j<=2*n-1;j++) //判断牌是否已经按顺序存放
{ if(s2[j]<s2[j+1]) continue;
else break;
}
if(j==2*n) {printf("经过了 %d 次洗牌/n",k); break;} //如果牌已经洗好
for(i=1;i<=2*n;i++) //根据洗牌规则将s2中的数搬到s1中
{ if(i%2!=0)
s1[i]=s2[p2++];
else
s1[i]=s2[p1++];
}
p1=1;p2=n+1;k++; //洗完一次牌后,p1,p2复位,洗牌的次数加1
for(j=1;j<=2*n-1;j++) //判断牌是否已经按顺序存放
{ if(s1[j]<s1[j+1]) continue;
else break;
}
if(j==2*n) {printf("经过了 %d 次洗牌/n",k); break;} //如果牌已经洗好
}
}