题目:设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)，最少需要经过多少次洗牌可恢复到初始状态。

比如:输入10,则输出 6;

下面是同学写的一个代码,但是超时,谁帮忙看一下怎么才能提高效率.谢了!!

#include<iostream>
using namespace std;

#define max 100001

int Isack(int a[])
{
int k = 1;
for(int i = 1; i <a[0]; i++)
if(a[i] > a[i+1]) k = 0;
return k;
}

int main()
{
int n, m=0,k;
int a[max],b[max];
for(k = 1; k<max ; k++) a[k] = k;
while(cin >> n)
{
m = 0;
a[0] = 2*n;
do
{
for(int i = 0; i < n; i++)
b[2*i+1] = a[n+i+1];
for(int j = 1; j <= n; j++)
b[2*j] =a[j];
m++;
for(k = 1; k <=2*n; k++)
a[k] = b[k];
}while(Isack(a) == 0);
cout<< m << endl;
}

return 0;
}

[此贴子已经被HJin于2007-7-29 5:44:49编辑过]

这题涉及到置换、群论、数论的一些内容，当然让你为了这一道题目全部看完不太现实。

你去看一下什么是循环群，什么是置换群，以及什么是循环群的阶，多个正整数的最小公倍数的相关定义
由题目表述的置换生成的群是一个2n元置换群，对于循环群，生成元的阶也就是群的阶，这题就是求这个阶是多少。

将这个2n元置换表示成若干不交的轮换之积的形式，然后求所有轮换中元素个数的最小公倍数，这个数就是这个置换群的阶

讲得比较抽象，有什么问题你再问吧

for(k = 1; k <=2*n; k++)
a[k] = b[k];

可以多用一个变量, 把 2*n 放到循环外... 这样不用每次循环都计算一次..

int tmp=2*n;
for(k = 1; k <=tmp; k++)
a[k] = b[k];

二楼讲的是那是．．．．．．．．．．．相当的抽象，读都读不懂！！　该问的问题很多，我看一时也问不完．．呵呵！！
三楼的方法我试过了．比以前节约了不少时间，但是还是超时．应该还可以改进．

谢谢两位了啊！！

既然要求只计算洗牌次数，何苦模拟整个过程呢？
我这样想：

在某一位置p的牌，经过m次洗牌后首次回到p，可得整组牌回到初始位置。
这是可以证明的，数学归纳法。

所以只需要跟踪一张牌的位置。
当此牌位置小于n，被后面的插，前面有牌，就都要被插上一张，加上自己，即经1次洗牌后，p前进 P+1（P为该位置前的牌数）
若位置大于n，那就是插别人，前面的插的多，后面的插的少， p后退 2n-P；

[CODE]
#include <iostream>
using namespace std;

#define N 5
int main(){
int pos = 0,times = 0;
do{
if (pos < N)
pos += (pos+1);
else
pos -= (2*N-pos);

++times;
}
while (pos);

cout << times << endl;
return 0;
}

[/CODE]

你说还是超时，意思是有online judge？地址贴一下，我去做做看

南开大学的1144，我自己找到了。

[此贴子已经被作者于2007-7-27 22:40:22编辑过]

用我的算法可以过的，时间0秒。

完全可以不需要嘛，就在a，b之间来回变换不就可以了，你这样每次都多作了2n次操作,当n为50000时肯定会很浪费时间。
这只是对你本身程序的改进而已，虽然那样程序会不那么简洁。

leeco 你讲的我都不懂啊，能不能在具体点。。。。。。你做出来了但是我就更加了！！