彩票问题（随机数）

122 阅读 0 评论 81 点赞

我是靠谱客的博主清爽大碗，这篇文章主要介绍彩票问题（随机数），现在分享给大家，希望可以做个参考。

问题描述

前一阵子想买个大了透玩玩，可是选号这个过程对我这个选择恐惧症的人来说太难了，因此想写个程序帮忙选定。大了透规则如下：
大乐透投注区分为前区号码和后区号码，前区号码范围为01～35，后区号码范围为01～12。大乐透每期从35个前区号码中开出5个号码，从12个后区号码中开出2个号码作为中奖号码，大乐透玩法即是竟猜开奖号码的5个前区号码和2个后区号码，顺序不限。

解题思路

由规则不难看出，我们需要从1-35中选取5个互不相同的随机数，从1-12中选取两个互不相同的随机数，我们可以通过生成随机数的函数rand()以及srand()来实现，函数的具体用法请见：rand函数介绍
最简单的方法即每产生一个随机数便与之前的数进行对比，如果相同便重新生成，直至不同为止。然而，这种方法有可优化的方法吗？

思路优化

当然，上面这种思路是可以实现的，但是每次随机生成一个随机数都要判断在结果集合中是否已经存在这个数，如果存在还要继续下一个循环，这样一来并不是每一轮循环都能生成一个有效（即不重复）的随机数，但实际在内部还是要通过循环来判断，效率还是较低。假如有一天有个人看到这篇文章，他想：很好，我终于可以试试了，我要从1到10000个数中取出9999个不重复的随机数，用上面的这个方法，可能很长时间都得不到结果。由此我们可以作出以下改动。
具体做法是这样的，我们将初始化一个数组，该数组包含所有值且数组下标于数组值相等，然后勇随机数产生某个数值n,再将arr[n]的值改为0，在后续的过程中先判断该位置的值是否为0，如果不为0则置0，否则重新生成。该方法事一种牺牲空间复杂度代换取时间复杂度的方式。代码如下：

代码实现

复制代码

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
//rand.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int randm(int m, int n)
{
    int arr1[m],arr2[n];
    int index, i, j;

    for (i = 0; i < m; ++i) {
        arr1[i] = i + 1;
    }
    srand((unsigned)time(NULL));
    for (i = 0; i < n;) {
        index = rand() % m;
        if (arr1[index] != 0) {
            arr2 [i] = arr1[index];
            arr1[index] = 0;
            ++i;
        }
    }
    for (i = 0; i < n; ++i){
        printf("%-3d",arr2[i]);
    } 
    printf("n");
    return 0;
}
int main()
{
    randm(32,5);
    randm(11,2);
    return 0;
}