首页 > 代码库 > 洗牌算法
洗牌算法
1. 编写一个方法，洗一副牌。要求做到完美洗牌，换言之，这副牌52！中排列组合出现的概率相同。假设给定一个完美的随机数发生器。
假设有个方法shuffle对n-1个元素有效，我们可以用它来打乱n个元素的次序。我们会先打乱前n-1个元素的次序，然后，取第n个元素，将它与数组中的元素随机交换。这是递归的思想。
这里我们使用的迭代方法，我们要做的就是遍历整个数组，对每个元素i，将array[i]与0和i(含)之间的随机元素交换。
//随机数产生器int random(int lower, int higher){ return lower + (rand() % (higher - lower + 1));}//递归void shuffleArrayRecursively(int cards[], int i){ if(i == 0) return; shuffleArrayRecursively(cards, i - 1); //打乱先前部分的次数 int k = random(0, i); //随机挑选索引进行交换 swap(cards[k], cards[i]);}//迭代void shuffleArrayInteratively(int cards[], int n){ for(int i = 0; i < n; i++) { int k = random(0, i); swap(cards[k],cards[i]); }}
2. 编写一个方法，从大小为n的数组中随机选出m个整数。要求每个元素被选中的概率相同。
关于这个问题的证明解释可以参见概率问题
这种问题和随机洗牌算法相似，所以我放在一起说。我们可以先取出源数组中的前m个元素，然后从元素m开始，迭代访问原数组，只要k<m,就将array[i]插入到目的数组中（随机选出）位置k。
//随机数产生器int random(int lower, int higher){ return lower + (rand() % (higher - lower + 1));}void pickMIteratively(int original[], int data[], int n, int m){ for(int i = 0; i < m; i++) { data[i] = original[i]; } for(int i = m; i < n; i++) { int k = random(0, i); if(k < m) data[k] = original[i]; }}
洗牌算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。