牌洗牌(SPOJ /见面会街)
这个问题以前曾被问过，但没有一个得到明确的回答，我试着汇编了我在这里找到的所有信息。如果需要，可以自由地合并/移动到另一个stackexchange站点。
以下是我发现的与此相关的问题：
这个问题最初是作为访问代码Sprint发布的，但现在它被列为实践问题。它也是移植到SPOJ。
以下是问题陈述：
下面是一种洗牌算法： 1)将卡片分成K个等号堆。 ( 2)底部N/K卡按相同的顺序属于桩1(因此初始桩的底卡是桩1的底卡)。 ( 3)下部N/K卡属于第2组，以此类推。 4)现在洗牌桩的顶卡是桩1的顶卡，下一张是桩2的顶卡，.洗牌桩的Kth卡是K桩的顶卡，其次(K + 1 )卡是目前位于第1桩顶的卡，(K +2)牌是目前位于第2桩顶的卡等。 例如，如果N=6和K= 3，那么一副牌的顺序"ABCDEF“(从上到下)一旦洗牌一次就会变成"ECAFDB”。 给定N和K，需要多少次洗牌才能使堆恢复到原来的顺序？ 输入:第一行包含测试用例T的数量。接下来的T行包含两个整数，每个整数N和K。 输出:输出T行，每个测试用例各一行，包含所需最少数量的洗牌。如果甲板再也没有恢复到原来的秩序，输出-1。 制约因素：
- K是N的一个因子。
- T <= 10000
- 2 <= K <= N <= 10^9
破坏者警报-如果你想自己解决它，不要阅读下面的内容。
这个问题可以翻译为：
查找K路(完美) 洗牌 需要执行的次数，以恢复N张牌的初始顺序。
我用两种方法来解决这个问题。想到的第一个办法是：
- 找到一个公式，在给定初始顺序的位置后，将生成卡片的下一个位置
- 使用公式确定从第一堆(n /k大小)取每一张卡返回其初始位置的洗牌次数。
- 返回之前确定的洗牌次数的最小公共倍数。
该解的复杂度为O(n /k+ max_number_of_suhffles)。这是实际的实现。问题是，它超过了最大时间，所以我开始寻找一个公式，可以让我在几乎恒定的时间内得到这个数字。
我可以在这里进行的优化(例如，使用一些映射来缓存相同排列周期中的计算值，等等)。就是让它通过面试街的3/10测试。
我找到了这一实现，它假设返回到初始状态所需的洗牌次数是相对于N+ 1的K的乘序。
As a consequence of Lagrange's theorem, ordn(a) always divides φ(n). 欧拉函数 (N)是群序，群序是我们要找的东西。我发现本论文使用φ计算洗牌次数，但它只适用于双向洗牌，而不是k路。
以下是此实现的步骤：
- 预计算素数列表< 100 000
- 根据它的素因子计算
φ(N+1)。 - 通过以各种可能的方式组合其主要因素来确定
φ(N + 1)的所有因素。 - 依次尝试每一个因素，得到最小的一个，
x，它验证k ^ x % N + 1 = 1
这个实现也是张贴在GitHub上。
这个测试运行得非常快，但是自动评分器给了我一个“错误的答案”，在SPOJ和Interviewstreet上的10次测试中，有9次是这样的。
我尝试比较这两个实现的输出，但是对于我输入的测试用例(已知的结果和随机的)，这两个实现总是输出相同的东西。这很奇怪，因为我非常肯定第一个算法是正确的，我假设第二个算法也应该是正确的。
“错误答案”分类可能来自于代码中的运行时错误，但没有什么可能是导致这种情况的原因。
我没有考虑到没有数字洗牌可以使甲板恢复到最初状态的情况--我的理解是，这是不可能的。有限数量的完美洗牌最终会恢复最初的顺序，尽管洗牌的数量可能真的很高。
如果你花时间读这篇文章，谢谢。)我对这个问题很好奇，我想把它解决。
回答 3
Stack Overflow用户
发布于 2012-08-22 13:20:03
这是我在纸上做了一些观察后想出来的。
class CardShuffle {
private long k;
private long n;
private long kn;
private long kn2;
public CardShuffle(long k, long n) {
//I omitted some checks done here
this.k = k;
this.n = n;
this.kn = k / n;
this.kn2 = k - kn;
}
public long shuffle() {
long count = 0L;
long next = 0L;
do {
//this can be further optimized
next = kn2 - kn * (next % n) + (next / n);
++count;
} while((next != 0L) && (count < k));
if(count > k)
return -1;
return count;
}
}结果是..。
Testing 1000000 : 2
#ms: 3.121905
#ms: 1424.487191
#1: 9900 #2: 9900
Testing 1000000 : 5
#ms: 1.409955
#ms: 556.329366
#1: 2475 #2: 2475
Testing 1000000 : 10
#ms: 0.007823
#ms: 186.797204
#1: 12 #2: 12
Testing 1000000 : 20
#ms: 0.590298
#ms: 275.751527
#1: 4950 #2: 4950
Testing 1000000 : 25
#ms: 0.298642
#ms: 260.559372
#1: 2475 #2: 2475
Testing 1000000 : 40
#ms: 1.187581
#ms: 241.956729
#1: 9900 #2: 9900
Testing 1000000 : 50
#ms: 1.187581
#ms: 241.015548
#1: 9900 #2: 9900
Testing 9999999 : 41841
#ms: 14.499887
#ms: 1829.868042
#1: 125000 #2: 125000
Testing 9999999 : 3333333
#ms: 58.119398
#ms: 311.005728
#1: 500000 #2: 500000
Testing 9999999 : 13947
#ms: 52.704185
#ms: 2095.336418
#1: 500000 #2: 500000根据这个输入测试..。
10
1000000 2
1000000 5
1000000 10
1000000 20
1000000 25
1000000 40
1000000 50
9999999 41841
9999999 3333333
9999999 13947首先，#ms是以毫秒为单位的时间--它采用了我的方法，第二个是您的。#1和#2分别是结果。
在哪里-至于这个输入.
15
1000000000 2
1000000000 5
1000000000 10
1000000000 20
1000000000 25
1000000000 40
1000000000 50
1000000000 1000
1000000000 200000000
1000000000 250000000
1000000000 500000000
1000000000 50000000
999999999 1001001
999999999 37037037
999999999 333333333我的方法在
Testing 1000000000 : 2
#ms: 71.360466
#1: 525780
Testing 1000000000 : 5
#ms: 68.987259
#1: 525780
Testing 1000000000 : 10
#ms: 0.008381
#1: 18
Testing 1000000000 : 20
#ms: 75.608492
#1: 525780
Testing 1000000000 : 25
#ms: 31.843154
#1: 262890
Testing 1000000000 : 40
#ms: 33.014531
#1: 262890
Testing 1000000000 : 50
#ms: 84.27384
#1: 525780
Testing 1000000000 : 1000
#ms: 0.006705
#1: 6
Testing 1000000000 : 200000000
#ms: 53.991778
#1: 525780
Testing 1000000000 : 250000000
#ms: 43.765898
#1: 262890
Testing 1000000000 : 500000000
#ms: 54.457201
#1: 525780
Testing 1000000000 : 50000000
#ms: 68.080999
#1: 525780
Testing 999999999 : 1001001
#ms: 115.060154
#1: 1000000
Testing 999999999 : 37037037
#ms: 5783.539528
#1: 50000000
Testing 999999999 : 333333333
#ms: 5391.880532
#1: 50000000虽然你的记忆在第一台的时候就没有了，但是在我的旧的和慢速的笔记本电脑上。
我还没有验证这种方法，但在我看来，它是有效的。您可能会尝试查看它是否在某些输入上失败。我会感激的。
如果您对我如何开发公式更感兴趣，请留下评论。
我也已经将解决方案提交给了面试官，但由于时间限制，在第4次测试中失败了。
我很快就会尝试一个c程序，然后在这里报告。
Stack Overflow用户
发布于 2012-08-21 04:35:23
给定N和K，计算出产生什么置换，并计算出它在符号表示法中的样子。在循环表示法中，置换是不相交循环的乘积，例如ABCDEF => ECAFDB是(AEDFBC)，因为A->E->D->F->B->C->A。如果你的置换是这样的单个循环，那么周期的长度就是你需要重复它的次数才能回到同一个地方。如果电势是多个不相交循环(如(ABC)(DE)(F)的乘积，则需要重复的次数是单个周期长度的多个。
Stack Overflow用户
发布于 2012-09-20 14:22:48
#include <iostream>
using namespace std;
int main()
{
int t, m , n, c, p, k, pos, cases;
cin>>cases;
while(cases--)
{
cin>>t;
cin>>k;
p = t/k;
pos = 1;
c = 0;
do
{
c++;
m = (pos - 1)%p + 1;
n = k - (pos - m)/p;
pos = k*(m-1) + n;
}while(pos!=1);
cout<<c<<endl;
}
return 0;
}https://stackoverflow.com/questions/12046138
复制相似问题
腾讯云开发者
