Harry 洗牌奇遇“神七”

上回 Lucas 在实现洗牌算法时差点颠覆了自己长期珍视的变量互换小妙招。

昨天 Harry 竟也遭遇了不可思议的事情。他用递归实现了自己的洗牌逻辑。程序如下：

$ cat harry.c 
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void shuffle(int *arr, int size){
  if(size==1)return;
  int num=rand()%size;
  int temp = arr[size-1];
  arr[size-1]=arr[num];
  arr[num]=temp;
  shuffle(arr,size-1);
}
int main(){
  int n=7;scanf("%d",&n);
  int arr[n];
  srand(time(0));
  for(int i=0;i<n;i++)arr[i]=i+1;
  for(int i=0;i<n;i++)printf("%d ",arr[i]);putchar('n');
  shuffle(arr,n);
  for(int i=0;i<n;i++)printf("%d ",arr[i]);putchar('n');
}

洗 52 张牌一切正常：

$ clang harry.c && ./a.out
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 
30 1 40 39 34 47 5 50 18 48 24 35 23 11 42 13 46 16 8 27 44 25 29 4 49 38 52 19 51 10 9 20 37 43 2 21 31 3 28 7 14 17 12 36 26 45 33 32 6 22 15 41 

$ clang harry.c && ./a.out
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 
45 50 9 3 21 8 4 17 33 31 51 29 15 40 32 16 5 10 47 14 35 18 22 2 25 52 38 7 26 37 6 42 36 49 41 48 13 19 34 44 23 46 11 43 30 12 24 20 28 27 1 39 

似乎洗任何张牌都正常。

20 张：

$ clang harry.c && ./a.out
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
7 2 9 6 12 11 3 14 5 17 13 8 16 1 10 19 4 15 18 20 
$ clang harry.c && ./a.out
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
2 11 8 10 13 19 7 4 9 6 12 15 20 16 14 5 17 18 1 3

10 张：

$ clang harry.c && ./a.out
10
1 2 3 4 5 6 7 8 9 10 
9 2 6 3 1 10 5 4 8 7

9 张：

$ clang harry.c && ./a.out
9
1 2 3 4 5 6 7 8 9 
6 1 5 4 7 2 9 3 8

8 张：

$ clang harry.c && ./a.out
8
1 2 3 4 5 6 7 8 
7 5 1 3 6 8 4 2

6 张：

$ clang harry.c && ./a.out
6
1 2 3 4 5 6 
1 6 2 3 5 4

5 张：

$ clang harry.c && ./a.out
5
1 2 3 4 5 
1 2 3 4 5 
$ clang harry.c && ./a.out
5
1 2 3 4 5 
2 4 3 1 5

4 张：

$ clang harry.c && ./a.out
4
1 2 3 4 
4 1 3 2 

3 张：

$ clang harry.c && ./a.out
3
1 2 3 
1 2 3 
$ clang harry.c && ./a.out
3
1 2 3 
2 3 1 
$ clang harry.c && ./a.out
3
1 2 3 
3 1 2 

2 张：

$ clang harry.c && ./a.out
2
1 2 
2 1

唯独 7 张犹如一个不散的幽灵：

$ clang harry.c && ./a.out
7
1 2 3 4 5 6 7 
4 1 3 5 6 2 7 
$ clang harry.c && ./a.out
7
1 2 3 4 5 6 7 
1 6 2 4 3 5 7 
$ clang harry.c && ./a.out
7
1 2 3 4 5 6 7 
5 6 1 2 4 3 7 
$ clang harry.c && ./a.out
7
1 2 3 4 5 6 7 
4 3 6 1 2 5 7

最后一张牌雷打不动，永远洗不动！真见着“鬼”了。我听见 Harry 在那头惊吼：“What？！”

课后我在我的电脑上重现了 Harry 的“神七”。然后上网搜了一下。才知系统的随机数发生器居然这么搞笑。分享给了 Harry：

It means that the pseudo random number generator uses a multiple of 7 (could be 16807) internally. 

See:

https://stackoverflow.com/questions/7866754/why-does-rand-7-always-return-0

Harry 总算能睡着觉了，我猜。

他这些日子被“神器（七）”折腾得寝食难安。