文档章节

扑克牌的完美洗牌算法

borey
 borey
发布于 2014/09/11 00:25
字数 617
阅读 4257
收藏 53

思路:

    递归思想。我们有n张牌,不妨先假设有一个洗牌函数shuffle(....),能完美的洗出n-1张牌 。拿第n张牌来打乱前面n-1的洗牌顺序,从而得到n张牌的最终结果。

代码如下:

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

//随机指定区域内的数
int MyRand(int low, int high)
{
	return low + rand() % (high - low + 1);
}

int* shuffle(int* cards, int n)
{
	if (n <= 0)
		return cards;

	shuffle(cards, n - 1);
	int rand = MyRand(0, n);

	int temp = cards[rand];
	cards[rand] = cards[n];
	cards[n] = temp;

	return cards;
}

int main()
{
	for (int k = 1; k <= 10; k++)
	{
		int cards[52] = {
			1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
			14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
			25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
			36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46,
			47, 48, 49, 50, 51, 52,
		};
		cout << endl;
		shuffle(cards, 52);//  洗牌
		for (int i = 1; i <= 52; i++)
		{
			cout << cards[i - 1] << " ";
			if (i % 13 == 0)
				cout << endl;
		}
	}
	cout << endl;
	system("PAUSE");
	return 0;
}

输出结果:

4 18 17 14 36 6 41 20 26 29 1 39 12
51 48 49 13 27 10 34 31 47 8 52 45 35
40 4 38 25 3 24 19 22 21 44 32 30 15
50 16 2 33 11 5 7 23 46 42 37 43 9

11 36 41 28 48 35 29 30 10 15 40 44 31
26 33 8 7 12 32 23 14 46 45 6 21 24
3 25 1 13 18 20 39 52 5 4 47 17 42
50 16 2 37 38 9 19 43 27 34 28 22 51

2 17 33 13 19 32 44 8 12 23 52 51 45
4 26 1 14 38 3 43 21 39 11 9 42 46
35 34 31 47 29 41 18 25 40 48 6 10 30
36 15 24 49 37 5 27 28 50 49 16 20 22

31 12 5 39 35 47 9 23 16 41 20 24 48
21 11 30 13 7 43 38 49 40 46 19 50 52
44 14 6 45 18 1 17 32 4 28 27 8 2
36 33 15 42 34 29 25 37 10 26 51 22 7

47 23 11 36 18 40 25 32 39 7 42 4 22
48 49 33 3 30 43 41 12 6 15 24 37 28
27 50 51 19 16 29 3 5 2 26 10 35 52
1 38 45 34 21 13 31 17 14 46 9 8 44

........

从结果来看上去很完美,剩下就是要在随机函数上做文章了,如果有一个完美的随机数发生器,那么这就是一个完美的洗牌算法。

通常递归的方法都能最换成迭代法,代码如下:

void shuffle2(int* cards, int n)
{
	// 随机i-1中的任意一个数与i交换
	for (int i = 0; i < n; i++)
	{
		int rand = MyRand(0, i);
		int temp = cards[rand];
		cards[rand] = cards[i];
		cards[i] = temp;
	}
}

Done!还不赖~~~

© 著作权归作者所有

borey
粉丝 28
博文 55
码字总数 31182
作品 0
深圳
程序员
私信 提问
加载中

评论(10)

LuckyWiky
LuckyWiky
这样洗不容易出炸弹
fate-testarossa
fate-testarossa
不要用java的逻辑写啊,不是函数越多越好
borey
borey 博主

引用来自“因火成烟_70565”的评论

怎么感觉你把问题搞复杂了
如何更简单~~~
因火成烟_70565
因火成烟_70565
怎么感觉你把问题搞复杂了
CheneyWong
CheneyWong
你想多了
边城孤独
边城孤独
随机数的问题是你没有设置随机种子的缘故吧
borey
borey 博主

引用来自“子达如何”的评论

洗牌不是一个完全随机过程
不理解什么意思?
子达如何
子达如何
洗牌不是一个完全随机过程
borey
borey 博主

引用来自“陈博1”的评论

random_shuffle
直接搞定啦

5有道理,哭瞎了~~~
陈博1
random_shuffle
直接搞定啦
扑克洗牌算法

扑克牌洗牌是我们生活中比较喜欢玩的一个游戏。那么我们有没有什么办法自己设计一个扑克牌洗牌的方法呢?在c运行库当中有一个随机函数rand,它可以生成0~32767之间的任意数。那么有没有可能利...

可达鸭眉头一皱
2016/07/31
79
0
通过n次循环获得n个自然数随机排序

刚才在51js看到有网友问,"1到100一百个数,怎么用JS来随机打乱它们的顺序呢?"。他说的这个不就是洗牌问题嘛,想起原来自己在做一个扑克游戏的时候设计过一个高效的洗牌算法,n个自然数通过...

唐玄奘
2017/12/13
0
0
打造属于自己的underscore系列(六)- 洗牌算法

javascript如何将一个无序的数组变成一个有序的数组,我们有很多的排序算法可以实现,例如冒泡算法,快速排序,插入排序等。然而我们是否想过,如何将一个有序的数组乱序输出呢?本文将从经典...

不做祖国的韭菜
02/17
0
0
Python 随机数标准库(2) -- shuffle()

Python random包可以用来生成随机数。随机数不仅可以用于数学用途,还经常被嵌入到算法中,用以提高算法效率,并提高程序的安全性。如果想要更加高级的数学功能,可以考虑选择标准库之外的n...

达闻西
2016/08/18
0
0
编写一个方法,洗一副牌。要求做到完美洗牌,换言之,这幅牌52!种排列组合出现的概率相同。假设给定一个完美的随机发生器

解法:假定有个数组,含有n个元素,类似如下: [1][2][3][4][5] 利用简单构造法,我们不妨先问自己,假定有个方法shuffle(...)对n-1个元素有效,我们可以用它来打乱n个元素的次序吗?当然可以...

一贱书生
2016/11/28
80
0

没有更多内容

加载失败,请刷新页面

加载更多

PostgreSQL 11.3 locking

rudi
今天
5
0
Mybatis Plus sql注入器

一、继承AbstractMethod /** * @author beth * @data 2019-10-23 20:39 */public class DeleteAllMethod extends AbstractMethod { @Override public MappedStatement injectMap......

一个yuanbeth
今天
10
1
一次写shell脚本的经历记录——特殊字符惹的祸

本文首发于微信公众号“我的小碗汤”,扫码文末二维码即可关注,欢迎一起交流! redis在容器化的过程中,涉及到纵向扩pod实例cpu、内存以及redis实例的maxmemory值,statefulset管理的pod需要...

码农实战
今天
4
0
为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接?

之前在阅读《阿里巴巴Java开发手册》时,发现有一条是关于循环体中字符串拼接的建议,具体内容如下: 那么我们首先来用例子来看看在循环体中用 + 或者用 StringBuilder 进行字符串拼接的效率...

武培轩
今天
8
0
队列-链式(c/c++实现)

队列是在线性表功能稍作修改形成的,在生活中排队是不能插队的吧,先排队先得到对待,慢来得排在最后面,这样来就形成了”先进先出“的队列。作用就是通过伟大的程序员来实现算法解决现实生活...

白客C
今天
81
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部