主题：这个数列如何只用一个变量转换
euc
[专家分：4310] 发布于 2006-11-07 15:44:00
给你2N张牌，编号为1,2,3..n,n+1,..2n。这也是最初的牌的顺序。
一次洗牌是把序列变为n+1,1,n+2,2,n+3,3,n+4,4..2n,n。
就是采用O(1)的空间,O(n)的时间.
回复列表 （共7个回复）
沙发
rickone [专家分：15390] 发布于 2006-11-07 22:48:00
那天做过类似的题，是给出初始序列和最终序列求洗牌次数的，我是先算出它的置换，你是要一次洗牌的变换吗？
f(x)=2x x<=n OR 2x-1 x>n
当然是在mod 2n的前提下。
板凳
euc [专家分：4310] 发布于 2006-11-08 13:31:00
不用额外数组,只借助一个辅助变量来转换,咋整?
3 楼
雨523 [专家分：200] 发布于 2006-11-08 16:42:00
交换？
1->t
n+1->1
t->n+1
?
4 楼
rickone [专家分：15390] 发布于 2006-11-08 18:56:00
开个表吧，O（1）的空间比较难想，O(n)时间。
5 楼
argentmoon [专家分：13260] 发布于 2006-11-08 20:31:00
//以下是比较早做过的，记不清楚了。。
#include <stdio.h>
int main()
{
int n, s, j;
while (scanf("%d", &n) != EOF){
s = 2, j = 1;
while(s != 1){
if (s > n) s += s - ( n + n + 1);
else s += s;
j++;
}
printf("%d\n", j);
}
return 0;
}
6 楼
rickone [专家分：15390] 发布于 2006-11-09 18:47:00
上面这个程序作什么用的？
7 楼
argentmoon [专家分：13260] 发布于 2006-11-09 18:55:00
是一个求最少次数的程序。
我来回复
您所在位置：