Algorithm Gossip: 洗扑克牌
我们在玩一些像斗地主这样的扑克牌游戏时,都要洗牌。在现实生活中洗牌都是由人把扑克牌随机打乱,那么,在比较火热的手机斗地主游戏中是怎样实现洗牌的呢?我们在编写程序时,首先要建模,即把现实世界中的问题抽象为计算机能够理解的模型,那么,怎么抽象洗扑克牌呀�
扑克牌共�54张,4种花色,每种花色13张,还有大王、小王,通过(花色,扑克牌的值)这个二元组就可唯一确定一张扑克牌。我们可以将扑克牌抽象为1~54的数字,分成4个区间:[1�13]、[14�26]、[27�39]、[40�52],每个区间表示一种花色,每个区间中的数字依次表示A~K,还�53�54分别表示小王、大王�
通过以上的抽象,洗扑克牌问题就被抽象为一个将1~54随机打乱顺序的问题。在将数字转换为扑克牌时,只需确定扑克牌的二元组就可以了,即只需将数字所处的区间转换为花色,将数字除�13的余数转换为牌的值就可以了,大王、小王单独处理�
至于怎么做到随机打乱1~54这些数字� 初学者通常会直接想到,随机产生1�54的随机数并将之存入阵列中,后产生的随机数存入阵列前必须先检查阵列中是否已有重复的数字,如果有这个数就不存入,再重新产生下一个数,运气不好的话,重复的次数就会很多,程序的执行速度就很慢了,这不是一个好方法�
可以将阵列先依序�1~54填入,然后遍历阵列,并产�1�54的随机数,将产生的随机数当作索引取出阵列中存的值,并与目前访问到的位置的值相交换,如此就不用担心随机数重复的问题了,阵列遍历完毕后,所有的数字也就随机打乱了�
C语言实现洗牌算法代码�
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 54
int main(void) {
int poker[N + 1];
int i, j, tmp, remain;
// 初始化阵�
for(i = 1; i <= N; i++)
poker[i] = i;
srand(time(0));
// 洗牌
for(i = 1; i <= N; i++) {
j = rand() % 54 + 1;
tmp = poker[i];
poker[i] = poker[j];
poker[j] = tmp;
}
for(i = 1; i <= N; i++) {
if(poker[i]==53)
printf("小王 ");
else if(poker[i]==54)
printf("大王 ");
else{
// 判断花色
switch((poker[i]-1) / 13) {
case 0:
printf("�"); break;
case 1:
printf("�"); break;
case 2:
printf("�"); break;