洗牌问题设 2n 张牌分别标记为
Description设2n张牌分别标记为1,2,…,n,n+l,…,2n,初始时这2n张牌按其标号从小到大排列。
经一次洗牌后,原来的排列顺序变成n+l,l,n+2,2,··,,2n,n。
即前n张牌被放到偶数位置2,4,·,·,2n,而后n张牌被放到奇数位置1,3,…,2n-l。
可以证明对于任何一个自然数n,经过若干次洗牌后可恢复初始状态。
编程任务:对于给定的n的值(n<=24000),编程计算最少经过多少次洗牌可恢复到初始状态。
Input
由键盘输入n的值。
输入包含多组数据,每行一个整数N。
Output
程序运行结束时,将计算出的最少洗牌次数在屏幕上输出。
对于输入的N,输出最少需要的洗牌次数。
Sample Input
10
Sample Output
6
程序代码:#include <stdio.h>
#include <stdlib.h>
#define NO 0
#define YES 1
void xipai(int *p,int n);
int pd(int *p,int n);
int main(void)
{
int n,*pai,i,flag=NO,count=0; //flag标记是否回到初始状态
scanf("%d",&n);
pai=(int *)malloc(2*n*sizeof(int));
for(i=0;i<2*n;i++) //初始化动态数组
pai[i]=i;
while(!flag)
{
count++; //洗牌次数累计
xipai(pai,n);
flag=pd(pai,n);
}
printf("%-5d",count); //输出共洗牌几次
return 0;
}
void xipai(int *p,int n) //洗牌
{
int *tmp=(int *)malloc(2*n*sizeof(int)); //创建临时动态数组
int i;
for(i=0;i<2*n;i++)
{
tmp[i]=p[i%2?(i/2):(n+i/2)]; //洗牌之后的排序
}
for(i=0;i<2*n;i++) //复制洗牌之后的数进原来数组
p[i]=tmp[i];
free(tmp); //释放临时动态数组
}
int pd(int *p,int n) //判断是否回到原点
{
int i;
for(i=0;i<2*n-1;i++)
{
if(p[i+1]!=p[i]+1)break; //如果不满足后面一个数是前一个数+1就退出
}
return i==2*n-1?YES:NO; //根据跳出循环时i的大小来判断是否回到原点
}









