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 總算能睡著覺了，我猜。

他這些日子被“神器（七）”折騰得寢食難安。