洗牌——114514

  • Post author:
  • Post category:其他


你是,你是一个一个一个洗牌问题啊啊啊;

24岁,洗起了扑克牌;

题目来自mooc:


题目内容:

假设我们有 2n 张牌,它们以 1, 2, …, n, n+1, …, 2n 编号并在开始时保持着这种顺序。一次洗牌就是将牌原来的次序变为 n+1, 1, n+2, 2, …, 2n, n,也就是将原来的前 n 张牌放到位置 2, 4, …, 2n,并且将余下的 n 张牌按照他们原来的次序放到奇数位置 1, 3, …, 2n-1。已经证明对于任何一个自然数 n,这 2n 张牌经过一定次数的洗牌就回到原来的次序。但我们不知道对于一个特定的 n,需要几次洗牌才能将牌洗回原来的次序。


输入格式:

牌张数的一半n,即初始情况下一共有2n张牌,n为int型整数


输出格式:

将牌洗回原来的次序所需要的洗牌次数


输入样例:

10


输出样例:

6[回车]

一开始我还想着看能不能找到什么递推公式的,没想到这道题的阴间程度已经不止于此了,于是,我还是选择了暴力算法;

主要思路:

分别存放这个数组的奇数位和偶数位,随后填充入总的数组中,进行比较,未归位的洗牌次数加一,归位的跳出循环。

本题雷点:最后两组数据我估摸着超过了500,因为把数据改到10000后就全部AC了,算法简单而且暴力,如下

	int a[20000];    // 初始化总的数组,并赋值
	for(i=0;i<2*n;i++)
	{
		a[i]=i+1;
	}
    int count=0;   // 循环体内参数设置
	int i=0;
	int j=0;
	int flag=1;
	while(flag)
	{
		count++;        // 由于是进入循环,优先对洗牌次数加一
		int b[10000]={0}; // 分别存放奇数和偶数位的数组
		int c[10000]={0};
		for(i=0;i<n;i++)
		{
			b[i]=a[i];
		}
		for(i;i<2*n;i++)   // 以上两个for对这两个数组进行赋值
		{
			c[i-n]=a[i];
		}
		for(i=0;i<2*n;i+=2)  // 这个for对原数组a进行填充
		{
			a[i]=c[i/2];
			a[i+1]=b[i/2];
		}
    }

注记:

(1)这里的语句中的flag是对循环体循环条件的判断,当比较符合条件时用作跳出循环;

(2)算法中省略了判断洗牌后是否符合条件的语句;

这里两个问题留给读者思考,此处仅给出主要的算法思路以及主要步骤。

总结:

本题此处给出的解法是暴力解法,存在更优的算法和优化方法,这里不作展开;

本题最大难点就在于对模型整体的构造和阐释,代码部分偏向中规中矩;



版权声明:本文为June_sixth原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。