你是,你是一个一个一个洗牌问题啊啊啊;
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)算法中省略了判断洗牌后是否符合条件的语句;
这里两个问题留给读者思考,此处仅给出主要的算法思路以及主要步骤。
总结:
本题此处给出的解法是暴力解法,存在更优的算法和优化方法,这里不作展开;
本题最大难点就在于对模型整体的构造和阐释,代码部分偏向中规中矩;