现在的位置: 首页 > 综合 > 正文

洗牌算法的研究

2013年01月01日 ⁄ 综合 ⁄ 共 872字 ⁄ 字号 评论关闭
         在纸牌游戏中,有个发牌过程,发牌就是把纸牌序列打乱发给游戏者。要保证发牌是随机的,这也符合现实中玩牌的过程,“洗牌”。
        洗牌:即产生指定数据的随机序列,将牌序打乱。
方法一:
思路:将n个数依次放到随机的位置。关键是每次找一个随机的位置。
1、设置目标数组为空(置0)
1、每次产生一个0~n-1的随机数,看这个位置是否已经放置了数,如果已经放置了,则继续用同样的方法找一个随机位置判断;如果这个位置还未放置,则设置此位置
3、反复执行(2)直到所有的位置都放置了数为止。(只要设置成功n次数就说明所有位置已经设置了数)
注:另外的理解就是,牌一张一张的发,从N张牌中随便选一张,发第一张,第二张。。。。。。一直到 第n张。
代码:
void shuffle(int dest[],int n)             //n为牌的个数
  {
	int pos, card;
	memset(dest, 0, n * sizeof(int));
	for(card = 1;card <= n; ++card)
	{
		do{
			pos = rand()%(n+1); //寻找位置

		}while(dest[pos]!=0);       //如果已经放置牌,随机产生下一个位置,继续放置"牌"
		dest[pos]=card;
	}    
  }
上面方法的问题:随着未设置的数渐渐变少,寻找未设置的位置会越来越难。如果牌数很多算法效率越来越低。
优点:算法过程思路比较简单,符合正常思维。
方法二:
    思路:目标数组,是牌的顺序是有序的,打乱它的次序,我们可以通过交换数组中任意两个位置的牌,一定次数的交换可使牌序打乱。
void shuffle ( int a[], int n )      //洗牌算法
{
    int tmp p1,p2;
   int M = n >> 2;              //这里M可以实际情况选择,即使实际中洗牌你也不会洗太多次,M = n >> 2(n的一半等,均可)
    int cnt = rand() % M;       
    while (cnt--)                 //随机交换两个位置的数,共交换cnt次
    {
           p1 = rand() % n;
           p2 = rand() % n;
          
           tmp = a[p1];
           a[p1] = a[p2];
           a[p2] = tmp;
    }
}
此方法较第一次效率较高,不需遍历所以牌。

抱歉!评论已关闭.