洗牌算法转 随机洗牌算法

63810393.html
洗牌算法(转) 随机洗牌算法
这个算法的要求是这样的:将N个数乱序后输出.由于和扑克牌的洗牌过程比较相似所以我也就称为洗牌算法了.很多地方都不自觉的需要这个算法的支持.也可以将这个算法扩展为从N个数中取出M个不重复的数(0<M<=N).

在大四的时候曾经在做某XX系统的时候遇到过这个问题,当时是要从N道题中选出M道然后出题.当时想到的是最简单也是最低效的一种方法:从N个数中随机取出一个放入一个新的集合中,看集合中是否已经存在这个数,如果没有就继续,否则重新生成随机数.由于当时需要的题目量比较少,因此也就蒙混过关了.后来一想如果每次生成的随机数都一样岂不是很慢?当时采用的还是”高科技”:HashSet.Java的HashSet有这个一个好处,就是添加的数如果已经存在就不进行操作,省得再判断是否存在了.唉,用了java就是容易偷懒啊!

算法(Java):

public HashSet getRamdomNumber(int total,intnumber){

//在0到total-1中随机生成number个不重复的随机数

HashSeth=new HashSet();

while(h.size()<number){

Random r=new Random();

int n=r.nextInt(total);

//n++;

h.add((Integer)n);//不用考虑重复的情况

}

returnh;

}

第二种方法是从网上看到的,思路是:将数组的元素进行随机的交换.这个算法我不太好说,因为它的效果和效率都依赖于交换的次数N.次数越多则乱序的程度越高但是相应的效率也会降低.个人不太推荐这个算法,因为N的次数不好确定.

算法:

void shuffle ( int a[], int n)//洗牌算法

{

int tmp =0,p1,p2;

int cnt =rand() % 1023;

while(cnt--)//随机交换两个位置的数,共交换cnt次

{

p1 = rand() % n;

p2 = rand() % n;

tmp= a[p1];

a[p1] = a[p2];

a[p2] = tmp;

}

}

后来在看Core Java2的时候看到了一个计算彩票的问题,实际上就是洗牌算法.思路是这样的:从数组中随机取出一个放到一个新的集合中,然后重复这个工作.这样最后原数组为空而新的集合则为乱序.这个算法比第一种算法的效率高多了,而且计算次数是固定的.当时就以为找到了最佳算法.后来蒙朋友提醒,对这个算法进行了改进.其实没有必要开辟一个新的集合的,用原来的存储空间就行.具体思路是:从数组的数中随机取出一个和最后一个元素交换,再从前面N-1个数中随机取一个和倒数第二个交换…这样可以达到和前面算法相同的效果而且存储空间也得到了节省,很不错的算法了.

算法:

void shuffle()

{

int *prev=new int[54];

for(inti=0;i<54;i++)//数组的初始化,表示54张牌

{

prev[i]=i;

}

srand(time(0));

int times=53;

while(times!=0)

{

int one=rand()%times;

swap(prev[one],prev[times]);//交换元素

times--;

}

//这个时候prev数组处于乱序状态,用完后回收空间

delete prev;

}

本来到这里就接近尾声了,但是后来看到stl中还提供了random_shuffle()方法.这个方法的效果就是实现洗牌算法.具体的效率方面我还没有测试过,不知道我的算法和它的哪个更快.以后有机会试一下.也许它用的就是我的思路也说不定,哈哈.

  

爱华网本文地址 » http://www.aihuau.com/a/25101016/314982.html

更多阅读

扑克牌洗牌的攻略 普通扑克牌怎么认牌

扑克牌洗牌的攻略——简介扑克牌洗牌技术是一种最基本的扑克牌技巧方法,很多的牌技都是通过洗牌来实现的。那么扑克牌洗牌基本手法有哪些?在此,我将为您一一介绍。扑克牌洗牌的攻略——工具/原料扑克牌

C++洗牌算法 随机洗牌算法

洗牌即产生指定数据的随机序列。  在网上找了半天大体有两种做法  1、  思路:将54个数依次放到随机的位置。关键是每次找一个随机的位置。  下面是找这个随机位置的算法:  1、用一个Bool型数组记录各个位置是否已经放置了数

金鸿评论:大洗牌时代之一

大洗牌时代(之一)不能不承认,国家与国家的实力是有差距的。过去的半年里,美国轻轻松松就把日本、欧盟和俄罗斯打倒在地,日元暴贬,欧元暴跌,卢布危机,不过,大家几乎没看到美国是怎么出手的,美国就成功了。

扑克牌洗牌的算法 常用的扑克牌洗牌方法

这段时间正在做一款扑克牌的游戏,关于洗牌的随机性做了一下研究.也发布上来给大家看看通常有几种方法来实现扑克的随机性: 1、需要时计算随机的扑克牌。(这种算法需要排除已经出过的牌然后再计算随机因子或者直接取出扑克牌比较,再和

声明:《洗牌算法转 随机洗牌算法》为网友疯少分享!如侵犯到您的合法权益请联系我们删除