注册 登录
编程论坛 → C++教室

NKOJ 1144: 洗牌问题

crystaljing 发布于 2007-07-27 17:10， 2601 次点击

题目:设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编辑过]

23 回复
#2
leeco2007-07-27 18:01
这题涉及到置换、群论、数论的一些内容，当然让你为了这一道题目全部看完不太现实。

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

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

讲得比较抽象，有什么问题你再问吧
#3
野比2007-07-27 18:50

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];
#4
crystaljing2007-07-27 20:10

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

谢谢两位了啊！！
#6
aipb20072007-07-27 21:48

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

在某一位置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]
#7
leeco2007-07-27 22:38
回复：（crystaljing）二楼讲的是那是．．．．．．．．...
你说还是超时，意思是有online judge？地址贴一下，我去做做看

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

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

用我的算法可以过的，时间0秒。
#9
medicihophy2007-07-28 20:26

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

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

leeco 你讲的我都不懂啊，能不能在具体点。。。。。。你做出来了但是我就更加了！！
#11
leeco2007-07-28 21:19
回复：（crystaljing）leeco 你讲的我都不懂啊，能不能...
你去看一下置换群啊
#12
aipb20072007-07-28 22:29

我那个这么好明白怎么不采纳下，一样的通过了。
#13
野比2007-07-28 22:46
以下是引用aipb2007在2007-7-28 22:29:05的发言：

我那个这么好明白怎么不采纳下，一样的通过了。
#14
leeco2007-07-29 00:56
回复：（aipb2007）我那个这么好明白怎么不采纳下，一...

我觉得你上面的思路有错啊，p位置的牌经过k次洗牌后回到p位置，不能证明所有的牌都回到了原来的位置。
#15
HJin2007-07-29 05:42
回复：（leeco）回复：（aipb2007）我那个这么好明白怎...

Yes, that is true. You need to prove it --- a math problem.

Thus for this problem, you only need to consider the nuber 1 --- see how it goes.
#16
HJin2007-07-29 05:47
回复：（crystaljing）NKOJ 1144: 洗牌问题

My submitted C code. I think it should be ranked #1 there.

=================================

main()
{
int n, a, c;

while(scanf("%d", &n)!=-1)
{
a = 2;
c = 1;

while(a!=1)
{
if(a<=n)
a<<=1;
else
a=2*(a-n)-1;
++c;
}

printf("%d\n", c);
}
}
#17
HJin2007-07-29 05:49
回复：（crystaljing）NKOJ 1144: 洗牌问题

My accepted C++ code --- completely simulates the shuffling process.

=================================================
#include <iostream>
using namespace std;

int a[200001], b[200001];

void shuffle(int*a, int *b, int n)
{
int i, i2;
for(i=1; i<=n; ++i)
{
i2=(i<<1);
b[i2] = a[i];
b[i2-1] = a[n+i];
}
}

int count(int n)
{
int i, c=0, n2=(n<<1);
bool bOrig = false;

for(i=1; i<=n2; ++i)
a[i] = i;

while(!bOrig)
{
shuffle(a, b, n);
++c;
bOrig = true;
for(i=1; i<=n2; ++i)
{
if(b[i] != i)
{
bOrig = false;
break;
}
}
if(bOrig)
break;

shuffle(b, a, n);
++c;
bOrig = true;
for(i=1; i<=n2; ++i)
{
if(a[i] != i)
{
bOrig = false;
break;
}
}
}

return c;
}

int main()
{
int n;

while(cin>>n)
cout<<count(n)<<endl;

return 0;
}
#18
野比2007-07-29 09:19
以下是引用HJin在2007-7-29 5:47:59的发言：

My submitted C code. I think it should be ranked #1 there.

=================================

main()
{
int n, a, c;

while(scanf("%d", &n)!=-1)
{
a = 2;
c = 1;

while(a!=1)
{
if(a<=n)
a<<=1;
else
a=2*(a-n)-1;
++c;
}

printf("%d\n", c);
}
}

NICE...
#19
aipb20072007-07-29 11:03
以下是引用HJin在2007-7-29 5:47:59的发言：

My submitted C code. I think it should be ranked #1 there.

=================================

main()
{
int n, a, c;

while(scanf("%d", &n)!=-1)
{
a = 2;
c = 1;

while(a!=1)
{
if(a<=n)
a<<=1;
else
a=2*(a-n)-1;
++c;
}

printf("%d\n", c);
}
}
#20
medicihophy2007-07-29 11:12
这个问题的置换群不好写啊，关键是所有置换都是定向的，怎么编谁教教，谢谢了！！！！
#21
leeco2007-07-29 11:42
回复：（HJin）回复：（leeco）回复：（aipb2007）我那...

我认为只跟踪一个位置的牌的算法，被接受只是巧合，可能他测试数据设计的不好，或者这题的置换是置换的一个特例恰好跟踪1号位的牌都是正确的。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2369
这题是一个更普遍的情况。我们可以看到对于它列举的一个情况
1 2 3 4 5
2 4 5 1 3

经过0次置换得到 1 2 3 4 5
经过1次置换得到 2 4 5 1 3
经过2次置换得到 4 1 3 2 5
经过3次置换得到 1 2 5 4 3 //这时1号位的已经回来了，但是 3 5号位的却没有。
#22
HJin2007-07-29 13:28
回复：（leeco）回复：（HJin）回复：（leeco）回复：...

The permutation group can be represented by matrix A
of size 2n by 2n with

A(2,1)=A(4,2)=...=A(2n,n)=1;
A(1,n+1)=A(3,n+2)=...=A(2n-1,2n)=1;
A(i,j) = 0 if (i,j) does not belong to above cases.

I believe you can show that it is a cyclic group. You may need to study
the theory of groups.

Although leeco gave a counter-example for odd number (here we have 2n),
I believe that we can move the first number back to position 1 with all
other numbers simultaneously back to their original positions.


Following C++ code verifies that this observation holds for 1<=n<=10^3.

==========================================================
#include <iostream>
#include <iomanip>
#define N 1000
using namespace std;

int a[2*N+1], b[2*N+1];

void shuffle(int*a, int *b, int n)
{
int i, i2;
for(i=1; i<=n; ++i)
{
i2=(i<<1);
b[i2] = a[i];
b[i2-1] = a[n+i];
}
}

int count(int n)
{
int i, c=0, n2=(n<<1);
bool bOrig = false;

for(i=1; i<=n2; ++i)
a[i] = i;

while(!bOrig)
{
shuffle(a, b, n);
++c;
bOrig = true;
for(i=1; i<=n2; ++i)
{
if(b[i] != i)
{
bOrig = false;
break;
}
}
if(bOrig)
break;

shuffle(b, a, n);
++c;
bOrig = true;
for(i=1; i<=n2; ++i)
{
if(a[i] != i)
{
bOrig = false;
break;
}
}
}

return c;
}

int permute1(int n)
{
int a=2, c=1;

while(a!=1)
{
if(a<=n)
a<<=1;
else
a=2*(a-n)-1;
++c;
}

return c;
}

int main()
{
int n;

for(n=1; n<=N; ++n)
{
// If you have access to nice computing service, change N to a big
// number and run it.
//
// If you are a math graduate, show it mathematically that there eixsts
// k s.t. A^k = I.

if( count(n) != permute1(n) )
cout<<setw(6)<<n<<setw(10)<<count(n)<<setw(10)<<permute1(n)<<endl;
}

return 0;
}
#23
leeco2007-07-29 16:56
回复：（HJin）回复：（leeco）回复：（HJin）回复：（...

偶数仍然有反例，只不过对于位置1恰好是对的，可能是由于题目说的这种置换比较特殊。
对于20个元素的情况，我们看到经过6次置换1号位的元素第一次回答1号位，而恰好其他的元素也第一次回到了原来的位置
但是对于3号位，6号位，9号位,12号位，15号位，18号位已经是第2次回到原来的位置了。
而对于7号位，14号位已经是第3次回到原来的位置了。
如果换一种洗牌方式，就不能盲目的选择1号位作为考察的位置了，对于这题选择1号位正确，只是巧合

事实上是3,12,6独自成循环，9,15,18独自成循环，7,14独自成循环，1，11，16，8，4，2，独自成循环。
而1恰好在一个最大的循环里，并且这个循环是其他循环的最小公倍数。这是很特殊的。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
11 1 12 2 13 3 14 4 15 5 16 6 17 7 18 8 19 9 20 10
16 11 6 1 17 12 7 2 18 13 8 3 19 14 9 4 20 15 10 5
8 16 3 11 19 6 14 1 9 17 4 12 20 7 15 2 10 18 5 13
4 8 12 16 20 3 7 11 15 19 2 6 10 14 18 1 5 9 13 17
2 4 6 8 10 12 14 16 18 20 1 3 5 7 9 11 13 15 17 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

[此贴子已经被作者于2007-7-29 17:03:03编辑过]
#24
crystaljing2007-07-31 16:04

各位怎么就这么厉害呢？！光把你们写的程序读懂都很不简单...........
真心谢谢你们！！
1
©2025, BC-CN.NET
电脑版