如何测试洗牌程序

如何测试洗牌程序

我希望本文有助于你了解测试软件是一件很重要也是一件不简单的事。

我们有一个程序,叫ShuffleArray(),是用来洗牌的,我见过N多千变万化的ShuffleArray(),但是似乎从来没人去想过怎么去测试这个算法。所以,我在面试中我经常会问应聘者如何测试ShuffleArray(),没想到这个问题居然难倒了很多有多年编程经验的人。对于这类的问题,其实,测试程序可能比算法更难写,代码更多。而这个问题正好可以加强一下我在《我们需要专职的QA吗?》中我所推崇的——开发人员更适合做测试的观点。

我们先来看几个算法(第一个用递归二分随机抽牌,第二个比较偷机取巧,第三个比较通俗易懂

递归二分随机抽牌

有一次是有一个朋友做了一个网页版的扑克游戏,他用到的算法就是想模拟平时我们玩牌时用手洗牌的方式,是用递归+二分法,我说这个程序恐怕不对吧。他觉得挺对的,说测试了没有问题。他的程序大致如下(原来的是用Javascript写的,我在这里凭记忆用C复现一下):

//递归二分方法
const size_t MAXLEN = 10;
const char TestArr[MAXLEN] = {'A','B','C','D','E','F','G','H','I','J'};

static char RecurArr[MAXLEN]={0};
static int cnt = 0;
void ShuffleArray_Recursive_Tmp(char* arr, int len)
{
    if(cnt > MAXLEN || len <=0){
        return;
    }

    int pos = rand() % len;
    RecurArr[cnt++] = arr[pos];
    if (len==1) return;
    ShuffleArray_Recursive_Tmp(arr, pos);
    ShuffleArray_Recursive_Tmp(arr+pos+1, len-pos-1);
}

void ShuffleArray_Recursive(char* arr, int len)
{
    memset(RecurArr, 0, sizeof(RecurArr));
    cnt=0;
    ShuffleArray_Recursive_Tmp(arr, len);
    memcpy(arr, RecurArr, len);
}

void main()
{
    char temp[MAXLEN]={0};
    for(int i=0; i<5; i++) {
        strncpy(temp, TestArr, MAXLEN);
        ShuffleArray_Recursive((char*)temp, MAXLEN);
    }
}

随便测试几次,还真像那么回事:

第一次:D C A B H E G F I J
第二次:A G D B C E F J H I
第三次:A B H F C E D G I J
第四次:J I F B A D C E H G
第五次:F B A D C E H G I J

快排Hack法

让我们再看一个hack 快排的洗牌程序(只看算法,省去别的代码):

int compare( const void *a, const void *b )
{
    return rand()%3-1;
}

void ShuffleArray_Sort(char* arr, int len)
{
    qsort( (void *)arr, (size_t)len, sizeof(char), compare );
}

运行个几次,感觉得还像那么回事:

第一次:H C D J F E A G B I
第二次:B F J D C E I H G A
第三次:C G D E J F B I A H
第四次:H C B J D F G E I A
第五次:D B C F E A I H G J

看不出有什么破绽。

大多数人的实现

下面这个算法是大多数人的实现,就是for循环一次,然后随机交换两个数

void ShuffleArray_General(char* arr, int len)
{
    const int suff_time = len;
    for(int idx=0; idx<suff_time; idx++) {
        int i = rand() % len;
        int j = rand() % len;
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

跑起来也还不错,洗得挺好的。

第一次:G F C D A J B I H E
第二次:D G J F E I A H C B
第三次:C J E F A D G B H I
第四次:H D C F A E B J I G
第五次:E A J F B I H G D C

但是上述三个算法哪个的效果更好?好像都是对的。一般的QA或是程序员很有可能就这样把这个功能Pass了。但是事情并没有那么简单……

如何测试

在做测试之前,我们还需要了解一下一个基本知识——PC机上是做不出真随机数的,只能做出伪随机数。真随机数需要硬件支持。但是不是这样我们就无法测试了呢,不是的。我们依然可以测试。

我们知道,洗牌洗得好不好,主要是看是不是够随机。那么如何测试随机性呢?

试想,我们有个随机函数rand()返回1到10中的一个数,如果够随机的话,每个数返回的概率都应该是一样的,也就是说每个数都应该有10分之1的概率会被返回。

一到概率问题,我们只有一个方法来做测试,那就是用统计的方式。也就是说,你调用rand()函数100次,其中,每个数出现的次数大约都在10次左右。(注意:我用了左右,这说明概率并不是很准确的)不应该有一个数出现了15次以上,另一个在5次以下,要是这样的话,这个函数就是错的。

举一反三,测试洗牌程序也一样,需要通过概率的方式来做统计,是不是每张牌出现在第一个位置的次数都是差不多的。

于是,这样一来上面的程序就可以很容易做测试了。

下面是测试结果(测试样本1000次——列是每个位置出现的次数,行是各个字符的统计,出现概率应该是1/10,也就是100次):

递归随机抽牌的方法

很明显,这个洗牌程序太有问题。算法是错的!

     1    2    3    4    5    6    7    8    9    10
----------------------------------------------------
A | 101  283  317  208   65   23    3    0    0    0
B | 101  191  273  239  127   54   12    2    1    0
C | 103  167  141  204  229  115   32    7    2    0
D | 103  103   87  128  242  195  112   26    3    1
E | 104   83   62   67  116  222  228   93   22    3
F |  91   58   34   60   69  141  234  241   65    7
G |  93   43   35   19   44  102  174  274  185   31
H |  94   28   27   27   46   68   94  173  310  133
I | 119   27   11   30   28   49   64   96  262  314
J |  91   17   13   18   34   31   47   88  150  511

快排Hack法

看看对角线(从左上到右下)上的数据,很离谱!所以,这个算法也是错的。

      1    2    3    4    5    6    7    8    9    10
-----------------------------------------------------
A |   74  108  123  102   93  198   40   37   52  173
B |  261  170  114   70   49   28   37   76  116   79
C |  112  164  168  117   71   37   62   96  116   57
D |   93   91  119  221  103   66   91   98   78   40
E |   62   60   82   90  290  112   95   98   71   40
F |   46   60   63   76   81  318   56   42   70  188
G |   72   57   68   77   83   39  400  105   55   44
H |   99   79   70   73   87   34  124  317   78   39
I |  127  112  102   90   81   24   57   83  248   76
J |   54   99   91   84   62  144   38   48  116  264

大多数人的算法

我们再来看看大多数人的算法。还是对角线上的数据有问题,所以,还是错的。

      1    2    3    4    5    6    7    8    9    10
-----------------------------------------------------
A |  178   98   92   82  101   85   79  105   87   93
B |   88  205   90   94   77   84   93   86  106   77
C |   93   99  185   96   83   87   98   88   82   89
D |  105   85   89  190   92   94  105   73   80   87
E |   97   74   85   88  204   91   80   90  100   91
F |   85   84   90   91   96  178   90   91  105   90
G |   81   84   84  104  102  105  197   75   79   89
H |   84   99  107   86   82   78   92  205   79   88
I |  102   72   88   94   87  103   94   92  187   81
J |   87  100   90   75   76   95   72   95   95  215

正确的算法

下面,我们来看看性能高且正确的算法—— Fisher_Yates算法

void ShuffleArray_Fisher_Yates(char* arr, int len)
{
    int i = len, j;
    char temp;

    if ( i == 0 ) return;
    while ( --i ) {
        j = rand() % (i+1);
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

这个算法不难理解,看看测试效果(效果明显比前面的要好):

      1    2    3    4    5    6    7    8    9    10
-----------------------------------------------------
A |  107   98   83  115   89  103  105   99   94  107
B |   91  106   90  102   88  100  102   97  112  112
C |  100  107   99  108  101   99   86   99  101  100
D |   96   85  108  101  117  103  102   96  108   84
E |  106   89  102   86   88  107  114  109  100   99
F |  109   96   87   94   98  102  109  101   92  102
G |   94   95  119  110   97  112   89  101   89   94
H |   93  102  102  103  100   89  107  105  101   98
I |   99  110  111  101  102   79  103   89  104  102
J |  105  112   99   99  108  106   95   95   99   82

但是我们可以看到还是不完美。因为我们使用的rand()是伪随机数,不过已经很不错的。最大的误差在20%左右。

我们再来看看洗牌100万次的统计值,你会看到误差在6%以内了。这个对于伪随机数生成的程序已经很不错了。

      1       2     3       4      5      6      7      8     9      10
-------------------------------------------------------------------------
A | 100095  99939 100451  99647  99321 100189 100284  99565 100525  99984
B |  99659 100394  99699 100436  99989 100401  99502 100125 100082  99713
C |  99938  99978 100384 100413 100045  99866  99945 100025  99388 100018
D |  99972  99954  99751 100112 100503  99461  99932  99881 100223 100211
E | 100041 100086  99966  99441 100401  99958  99997 100159  99884 100067
F | 100491 100294 100164 100321  99902  99819  99449 100130  99623  99807
G |  99822  99636  99924 100172  99738 100567 100427  99871 100125  99718
H |  99445 100328  99720  99922 100075  99804 100127  99851 100526 100202
I | 100269 100001  99542  99835 100070  99894 100229 100181  99718 100261
J | 100268  99390 100399  99701  99956 100041 100108 100212  99906 100019

如何写测试案例

测试程序其实很容易写了。就是,设置一个样本大小,做一下统计,然后计算一下误差值是否在可以容忍的范围内。比如:

  • 样本:100万次
  • 最大误差:10%以内
  • 平均误差:5%以内 (或者:90%以上的误差要小于5%)

注意

其实,以上的测试只是测试了牌在各个位置的概率。这个还不足够好。因为还可能会现在有Patten的情况。如:每次洗牌出来的都是一个循环顺序数组。这完全可以满足我上面的测试条件。但是那明显是错的。所以,还需要统计每种排列的出现的次数,看看是不是均匀。但是,如果这些排列又是以某种规律出现的呢?看来,这没完没了了。

测试的确是一个很重要,并不简单的事情。谢谢所有参与讨论的人。

附录

之前忘贴了一个模拟我们玩牌洗牌的算法,现补充如下:

void ShuffleArray_Manual(char* arr, int len)
{
    int mid = len / 2;

    for (int n=0; n<5; n++){

        //两手洗牌
        for (int i=1; i<mid; i+=2){
            char tmp = arr[i];
            arr[i] = arr[mid+i];
            arr[mid+i] = tmp;
        }

        //随机切牌
        char *buf = (char*)malloc(sizeof(char)*len);

        for(int j=0; j<5; j++) {
            int start= rand() % (len-1) + 1;
            int numCards= rand()% (len/2) + 1;

            if (start + numCards > len ){
                numCards = len - start;
            }

            memset(buf, 0, len);
            strncpy(buf, arr, start);
            strncpy(arr, arr+start, numCards);
            strncpy(arr+numCards, buf, start);
        }
        free(buf);

    }
}

我们来看看测试结果:(10万次)效果更好一些,误差在2%以内了。

      1       2     3       4      5      6      7      8     9      10
-------------------------------------------------------------------------
A |  10002   9998   9924  10006  10048  10200   9939   9812  10080   9991
B |   9939   9962  10118  10007   9974  10037  10149  10052   9761  10001
C |  10054  10100  10050   9961   9856   9996   9853  10016   9928  10186
D |   9851   9939   9852  10076  10208  10003   9974  10052   9992  10053
E |  10009   9915  10050  10037   9923  10094  10078  10059   9880   9955
F |  10151  10115  10113   9919   9844   9896   9891   9904  10225   9942
G |  10001  10116  10097  10030  10061   9993   9891   9922   9889  10000
H |  10075  10033   9866   9857  10170   9854  10062  10078  10056   9949
I |  10045   9864   9879  10066   9930   9919  10085  10104  10095  10013
J |   9873   9958  10051  10041   9986  10008  10078  10001  10094   9910

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (30 人打了分,平均分: 4.10 )
Loading...

如何测试洗牌程序》的相关评论

  1. 用统计频率来测试随机性,也太随意了吧……
    绝对不应该这么测试的,有专门的随机测试办法的

    ”(注意:我用了左右,这说明概率并不是很准确的)“又是在说什么
    概率是准确的精确值,但是频率依据大数定理的证明,只是在样本数趋无穷的情况下趋近概率,当然是不准确的……

  2. 双手洗牌是这样洗的吗……?是我平时用的不是这种洗法抑或我没看懂代码啊……想不到那段代码模拟的双手洗牌在现实中怎么操作的……

  3. 昨天看了微博就知道皓哥一定会些博客来得瑟,果然今天就看到了。皓哥这里提到的测试和一般所谓的软件验证测试本来就不是一个概念。一般的测试只是验证软件的结果和需求是否匹配,一般叫黑盒。像洗牌的你要先给出需求比如多次洗牌出现同模式的必须小于多少或者各个位置的需求作为输入.模糊的说洗牌程序那就只有写程序的人知道是做什么的。 白盒的测试也只是检验代码实现的逻辑和设计的逻辑是否匹配。有了预先的设计,才能验证。 也就是说一般讨论的测试就是如何验证软件结果与预期是否一致。而不是有多好。算法的好坏自己然开发做的。

    就算拿你列举的前三份代码来说, 他们的代码实现首先就没有验证。如果代码中本身就有错误呢?比如,扑克牌是54张的。测试代码里只用了10个数,伪随机序列只有在长度比较大的情况下,数值才能体现随机性。想你列举的测试过程,应该每次改变随机因子。代码本身使用随机函数方法就有问题。

    我相信,不是大部分资深程序员回答不了你的问题,而是你的问题本来就有问题。洗牌程序怎么测? 鬼知道怎么测。“测”的前提就是要了解需求,根据需求细化case。但是一个需求可能覆盖到的软件路径是极多的,所以需要有一定的方法。当然现在没有完美的方法,但是出去工程话的管理,就要有总结方法去控制风险。这个敏捷的目的是一样的。我不是推崇敏捷,只是当软件作为工程概念的时候,需要科学的方法管理。尽管未必尽善尽美,但也要尽可可控。而不是像艺术家一样的天马行空。 当然国内很多人水平有限,这就给了皓哥攻击的砝码。

  4. 皓哥每次都是变着法的偷换概念,拿着国外大牛狐假虎威。大师们自然有自己的门道,但是作为一个行业来说,软件开发和测试都是在不断探索科学化的管理方法的。这才有可能想现在大家都可以写出可以用的软件。不然,软件就只能停留在只有大师们和皓哥你这样的人才能写软件的阶段了。 当然已皓哥的睿智自然是明白这些的,这都只不过是作为技术人员的一点得瑟之心而已。会写点代码的人,总是瞧不起别人,把自己当大牛,把自己的准则当作准神,其实狭隘的一塌糊涂。

    皓哥所有的文章都不过是为了YY自己的技术技高一筹,已产生一种自己比肩大师的自我满足,根本无所谓所讨论问题的定义究竟是什么。踩着一群国内大忽悠的身体,被众人的吹捧送上神坛。 微博里最后还让别人来出题,就为的自己show一把。

    浏览了一下皓哥的博客,所有文章里,有营养的文章有两类 1)转贴大师的话+comments 2)转贴 还大言不惭抨击infoQ的空洞文章。

    补充一点,皓哥当年的Makefile对于年幼无知的我还算是上品。

    当然皓哥会把我打为敏捷控,人身攻击控,空洞理论控等牛鬼蛇神直接枪毙。然后封我ip,禁我评论。于是又是一片赞叹,万众景仰,顶礼膜拜。

  5. 说伪随取模不够随机的… RAND_MAX通常是多少? 扑克牌有多少张? 那么这个问题的实际影响有多大? 对于这个测试影响有多大?

    “试想,我们有个随机函数rand()返回1到10中的一个数,如果够随机的话,每个数返回的概率都应该是一样的,也就是说每个数都应该有10分之1的概率会被返回。” 这种说法是错的, 一个硬币扔两次就一定一正一反吗? 真懂概率的人, 真不多…

    楼上的你不是敏捷控是什么? 不过我觉得设计师跟包工头打架这事儿没啥意思.

  6. 我测试了一下,至少结果确实不是我平时双手洗牌的效果,我双手洗牌的时候事实上是将一半的牌组A的牌逐张插入到另一半的牌组B的两张牌之间,在新的整副牌中,牌组A的牌的相对位置还是没有变的,牌组B的牌的相对位置也没有变。
    也就是说原本a,b.c.d.e.f.g,洗了之后应该是a,e,b,f,c,g,d.难道不是这样双手洗的吗?@zhangzhenyue

  7. fuckm :那个叫M的该是个什么样的SB啊

    这个人的网名叫michaelchen,自从因为博主批评敏捷的事,他就开始骂博主了,说话阴阳乱气的,博主基本都不理他。我在博主的微博和图灵的采访那边也看到过他的SB评论。

    我觉得他是爱上博主了,因为博主出现的地方都有他的身影,因为博主已经成了他生活中不可缺少的一部分了。

  8. @colin
    我同意你的说法,
    这文章的测试方法比较原始……我到现在都不懂他为啥要测这个所谓的“误差”以及这个“误差”能“证明”啥。
    在american scientist的2011年7,8月刊有篇文章讲到随机数的叫Quasirandom Ramblings,里面提到(几乎所有关于概率的教材都会提到)随机数必须符合:1.不可以预测,2,相互独立,3,均匀分布。
    我想如果文章的测试程序也仅仅是测试了均匀分布,而没有测试“不可以预测”,“相互独立”。而且像这种所谓的测试根本就不可能去“证明算法”是对还是错的。仅仅是“测试”了均匀分布就算是测试了?这有点鬼扯吧!如果你需要完备的测试的话,我觉得2 gram, 3 gram估计都不够,而且这“够不够”也完全是很人为的设定的,就跟语义识别的做法一样。大部分伪随机数都仅仅是符合了均匀分布而已。

    开发前就没有说清楚对程序的需求,后面又要求测试能够“完备”,然后又责备测试人员不懂测试这个程序,最后还说测试人员肯定会就这样pass了。拜托博主,我也是测试人员,也没有你说的那么肤浅,肤浅到连概率统计都不懂。而且你这样“情绪化”的下这个结论,也暴露出你的逻辑修养不足–不是就事论事,而是以自己的偏见论事。

    如果你真的要测试随机性,还不如用个程序去捕获硬件的电子噪声,这个白噪声完全是随机的,现在有些Unix系统的原生random程序就是以这个做出来的。

  9. M 你好,
    你说的虽有道理,但言语过于犀利。毕竟大家的目地是为了交流和学习技术。我觉的这里的很多文章还是很有价值的,尤其提供了一个中文环境下的技术学习窗口和沟通渠道。听你的话好像有很多其他的见解,如果有个人博客/网站的话,是否介意也公开出来和大家分享?

  10. 我们来看一下第三个方法(大多数人算法)为啥对角线会有问题。每次洗牌循环交换10次,洗牌结束后,A排在第一位有两种情况,一种是这10次交换没有交换到A,另一种是第10次交换将其他位置的A交换到第一位。前一种的概率是0.8^10;后一种的概率大概为(前9次交换交换到A的概率)*(1/9),约等于0.1;加一起大约0.2。很明显这算法本身有问题,和伪随机真随机没有什么关系。而且我们可以看到这个误差和数组长度有关(虽然实际上影响不大)。用10个元素的数组测试顶多能验证算法本身有没有系统性错误,而不能真正检验实际情况下(54张牌)的误差分布。

  11. 测试案例那一项有=一种情况没考虑到:
    如果测试100w次,得出的结果为每个字符10W次,或者相差很少,10以内,算不算是缺陷。

  12. 其实“开发人员更适合做测试”这句话给我的理解是——测试人员应该要比开发更懂这个软件的业务和代码,否则就不会被开发忽悠。。。

  13. @茶话汇
    我的观点是:开发人员不适合测试自己的代码,写自己项目的文档,因为人往往熟视无睹,自己知道了以为别人也知道
    测试尤其危险,因为开发人员往往走正确的操作路径,也就很难出错了

  14. 谢谢。我没有什么技术博客,我也不是搞技术的。我也没什么技术。早期学习makefile的时候拜读了皓哥的跟我一起些makefile 感觉非常不错。后来就关注了皓哥的博客。看到他对敏捷的一些观点颇为偏颇。偷换概念,根本没说到点子,所以发表了一些观点。想不到皓哥不就具体问题反驳,就把我打入了“疯狗派”,还禁我评论。所以我看了其他的文章,才发现了皓哥所谓技术文章的奥义,就不过是技术人员特有的自我感觉良好。凡是会写点代码的人都有这种情节。看不起测试,看不起windows,经不得批评。拿一些大牛当神拜,等等。 很多人不动脑子满口脏话,还说我骂人。我所发表的言论如有骂人之处,我愿意奉献2000w给被骂的人。 @lailai23

  15. 完全同意M的看法。博主的水平说实话是很不入流的。往细里讲,从c到gcc到arch,从tcp/ip到kernel到security
    ,无论是基础理论还是实际应用,完全是还没入门的水平。我早就说了,博主适合的位子是技术类编辑,就跟那个gigix是一路货。

  16. Fisher_Yates算法 的意思是,从最后一张牌开始,和他前面的牌换,然后就不动了,
    接下来每张牌都和它前面的牌换,不和后面的牌换。
    这是为什么呢?有什么用意呢?

    如果也可以和后面的牌换的话,会有什么缺陷呢?例如下面的这个程序:
    void washcard1(int a[], int n)
    {
    int i=0;
    int j=0;
    int tmp;
    for(;i<n;i++){
    j = rand()%n;
    tmp = a[i];
    a[i]=a[j];
    a[j]=tmp;
    }
    }
    而且我觉得这个方法和“大多数人用的算法”差不多啊,为啥结果会不一样呢?
    我自己试了,试了“大多数人的算法”和我上面的这个算法,都没发现问题,结果如下:
    1000次:
    112 102 89 96 105 101 96 84 107 108

    101 107 103 85 114 106 105 91 96 92

    113 90 81 99 93 118 98 93 103 112

    78 85 122 105 110 92 86 106 105 111

    98 101 98 103 86 101 115 98 101 99

    97 110 100 111 89 112 94 110 82 95

    94 103 98 107 88 112 103 98 98 99

    98 112 81 96 107 89 109 105 104 99

    93 96 121 95 104 89 98 100 111 93

    116 94 107 103 104 80 96 115 93 92

    10000次:

    1008 1000 985 966 891 1048 1066 1005 983 1048

    973 1053 957 979 988 1020 1039 966 1052 973

    1047 982 997 988 939 1029 1020 972 1024 1002

    1018 1038 1005 984 1066 1008 969 970 961 981

    992 1004 1000 1042 985 1028 942 996 1001 1010

    981 975 1030 989 1034 987 978 1072 984 970

    979 935 1015 1016 1003 952 1024 1051 1025 1000

    1008 951 1016 1041 1115 994 951 978 937 1009

    978 1006 1046 984 1001 958 1014 988 1013 1012

    1016 1056 949 1011 978 976 997 1002 1020 995

    谁能帮忙解答一下,谢谢!

  17. 我试了qsort的那个方法,1000次误差在20%以内,10000次在10%以内。
    都没有出现200次的那种情况。
    为啥?是我的程序有问题吗?
    #include
    #include
    #include

    #define MAXLEN 10
    int TestArr[MAXLEN][MAXLEN];
    typedef void (*FunType)(int a[], int n);

    void tranverse_arr(int a[], int n, FunType fp);
    void initial_arr(int a[], int n);
    void print_arr(int a[], int n);

    void shufflecard1(int a[], int n);
    void shufflecard2(int a[], int n);
    void shufflecard3(int a[], int n);
    /*
    void shufflecard4(int a[], int n);
    void shufflecard5(int a[], int n);
    */

    int main(void)
    {
    int i,j;
    FILE *fp;
    int ori[MAXLEN] = {0};
    fp = fopen(“D:/b.txt”, “w”);

    srand((unsigned) time(NULL));

    tranverse_arr(ori, MAXLEN, initial_arr);
    //tranverse_arr(ori, MAXLEN, print_arr);
    tranverse_arr(ori, MAXLEN, shufflecard3);
    tranverse_arr(ori, MAXLEN, print_arr);

    for(i=0; i<1000; i++){
    for(j=0; j<MAXLEN; j++){
    TestArr[ori[j]][j]++;
    }
    tranverse_arr(ori, MAXLEN, shufflecard3);
    }

    for(i=0; i<MAXLEN; i++){
    for(j=0; j<MAXLEN; j++){
    fprintf(fp, "%d\t", TestArr[i][j]);
    }
    fprintf(fp, "\r\n");
    }
    fclose(fp);
    return 0;
    }

    void tranverse_arr(int a[], int n, FunType fp)
    {
    fp(a, n);
    }

    void initial_arr(int a[], int n)
    {
    int i=0;
    for(;i<n;i++){
    a[i]=i;
    }
    }

    void print_arr(int a[], int n)
    {
    int i=0;
    for(;i<n;i++){
    printf("%d ", a[i]);
    }
    printf("\n");
    }

    void shufflecard1(int a[], int n)
    {
    int i=0;
    int j=0;
    int tmp;
    for(;i<n;i++){
    j = rand()%n;
    tmp = a[i];
    a[i]=a[j];
    a[j]=tmp;
    }
    }

    void shufflecard2(int a[], int n)
    {
    int i, j, temp, idx;
    const int suff_time = n;
    for (idx=0; idx<suff_time; idx++){
    i = rand() % n;
    j = rand() % n;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }
    }

    int cmp(const void *a, const void *b)
    {
    return rand()%3-1;
    }
    void shufflecard3(int a[], int n)
    {
    qsort((void *)a, n, sizeof(int), cmp);
    }

  18. 最近在看《测试之美》这本书,开发是有必要了解测试的,在敏捷开发里还有个叫——测试驱动呢。。。

  19. rand()的后面用取余%是错误的用法,特别当%后面的数字稍大(比如10000)时。
    正确的做法是尽量取rand()返回值尽量靠左边的数字,而不是用%取末几位。原因可以猜猜看 :)

  20. Pingback: 一牛过河
  21. @fuckm 支持你的说法,其实楼主追求的才是真的伪随机。例如,在某个小样本范围内,必须可以有某个值是超越10%的。如果考虑极限,甚至可以出现洗完以后和没洗时候是一样的结果。

  22. 洗牌的问题在于是否够随机,随机算法一旦测试没问题,剩下的就是个牌型打撒问题(交换顺序),的确,没有真随机,都是伪随机,伪随机算法很多,JAVA的JDK用的是PRNG算法,还有Mersenne Twister:
    http://en.wikipedia.org/wiki/Mersenne_twister

    总结楼主的意思,是在讲如何测试随机性,跟棋牌无关。

  23. 我写的第一个需要创建随机序列的程序就是用的Fisher_Yates算法(当然我现在才知道它叫这个名字),我觉得这才是最直观的想法啊……

  24. 如果从内核中获取随机数,能不能真正的随机呢,比如使用计算机时敲击键盘的时间间隔,移动鼠标的距离与间隔?

  25. @james
    你说的就是 Linux 的 /dev/random 的实现了,Linux 会把所有驱动程序产生的垃圾数据扔进熵池里面。关键的问题是,里面的数据是不能指定范围的。

  26. 十年前我还上学的时候用了很少的代码做过shuffle:
    1 生成相同长度的随机数
    2 按随机数大小对数据进行关联排序
    随机程度和随机函数保持一致,复杂度与排序函数一致。

  27. Fisher_Yates就是从后向前,保证每张牌与前面的牌随机交换一次,思路非常顺,至于效果,另说
    那个大部分人的算法,就有问题了,首先,每次都是任意两张牌交换,那么交换n次就莫名奇妙了,n好像可以但是实际不能保证每张牌都参与过交换。

  28. C的rand()用的是线性生成随机数……考虑%P之后如果P不是一个素数产生的碰撞了吗。。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注