洗牌问题设 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的大小来判断是否回到原点 }