STL系列十一 随机三趣题——随机重排,文件中随机取一行,生成N个随机数

2024-04-23 01:58

本文主要是介绍STL系列十一 随机三趣题——随机重排,文件中随机取一行,生成N个随机数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

8人阅读 评论(0) 收藏 举报

目录(?)[+]

本文将介绍三个有趣的随机问题,分别是随机重新排列、从文件中随机取一行数据、生成N个随机数。

 

一.随机重新排列

将一个序列打乱并对其进行随机的重新排列,关键在于每种序列的被选择概率要一样,不然有失“公平”。现在让我们来寻找如何保证每种序列被选择的概率一样大的算法。

首先假设这个数组只有二个元素,设数组a{1, 2},显然这个数组只有二种可能的排列,要么是{12}要么是{21}。很容易想到一种方法——只要第二个元素有50%的概率与第一个元素交换即可。用代码表现下:

if (rand() % 2 == 0)

      swap(a[0], a[1])

由于rand() % 2的结果要么为0,要么为1,且各占50%的概率。因此swap(a[0],a[1])的执行概率也是50%,如果执行了,结果会是{21}。没有执行,结果会是{12}。所以这样两种排列出现的可能均为50%

 

接下来再假充这个数组有三个元素设数组a{1, 23},这个数组有六种可能的排列,要么是{123}{132}{213}{231}{312}{321}。这么多的排列看起来好象有点复杂,不知道从何下手。其实结合上面的分析,我们可以这样考虑:

1.先调整前二个元素即{1, 23}先生成{123}{213}

2.然后对{123},第三个元素以1/3的概率与第一,第二,第三个元素进行交换就可以等概率的得到{321}{132}{123}

3.同理对{213},可以等概率的得到{312}{231}{213}

根据贝叶斯公式,不难计算出由这些排列出现的可能性都是1/2 * 1/3 = 1/6。完全符合每种序列的被选择概率相同的要求。

 

这样随机重新排列的算法就找到了,下面给出示意代码:

[cpp] view plain copy
  1. //随机重新排列  
  2. //参照STL中的random_shuffle  
  3. #include <stdio.h>  
  4. #include <stdlib.h>  
  5. #include <time.h>  
  6. inline void Swap(int *a, int *b)  
  7. {  
  8.     int c = *a;  
  9.     *a = *b;  
  10.     *b = c;  
  11. }  
  12. //随机重新排列函数  
  13. void Random_shuffle(int a[], int n)  
  14. {  
  15.     srand(time(NULL));  
  16.     for (int i = 1; i < n; i++)  
  17.         Swap(&a[i], &a[rand() % (i + 1)]);  
  18. }  
  19. void PrintfIntArray(int a[], int n)  
  20. {  
  21.     for (int i = 0; i < n; i++)  
  22.         printf("%d ", a[i]);  
  23.     putchar('\n');  
  24. }  
  25. int main()  
  26. {  
  27.     printf("           随机重新排列 \n");  
  28.     printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");  
  29.   
  30.     const int MAXN = 8;  
  31.     int a[MAXN] = {1, 2, 3, 4, 5, 6, 7, 8};  
  32.   
  33.     printf("原数组:\n");  
  34.     PrintfIntArray(a, MAXN);  
  35.   
  36.     Random_shuffle(a, MAXN);  
  37.   
  38.     printf("随机重新排列后:\n");  
  39.     PrintfIntArray(a, MAXN);  
  40.     return 0;  
  41. }  

运行结果如下:

有兴趣的童鞋可以用STL中的random_shuffle()来改写上面的程序,相信知道其实现原理后会对random_shuffle()有更深的认识。

另外,这种按顺序先后来交换元素得到新排列的方法与生成全排列非常类似,可以参考《STL系列之十 全排列(百度迅雷笔试题)》然后对比下两种方法在思路上相似之处。

 

二.从文件中随机取一行数据

如果先统计文件有多少行,再根据rand() % 行数选择对应行也是可以行的,但效率显然会有点低了。有没有一种方法可以只遍历文件一次了?请看代码:

[cpp] view plain copy
  1. //从文件中取机选取一行  
  2. #include <stdio.h>  
  3. #include <stdlib.h>  
  4. #include <time.h>  
  5. int main()  
  6. {  
  7.     printf("           从文件中取机选取一行 \n");  
  8.     printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");  
  9.   
  10.     int i, num, nChooseNum;  
  11.     const char strFileName[] = "in.txt";  
  12.       
  13.     freopen(strFileName, "r", stdin);  
  14.     srand(time(NULL));  
  15.     i = 1;  
  16.     while (scanf("%d", &num) != EOF)  
  17.     {  
  18.         if (rand() % i == 0)  
  19.             nChooseNum = num;  
  20.         i++;  
  21.     }  
  22.     printf("从文件中选取出: %d\n", nChooseNum);  
  23.     return 0;  
  24. }  

运行结果如下(in.txt中为09,每个数字占一行):

对代码进行下讲解,以三行数据为例,首先对文本的第一行,rand() % 1,结果必然为0。所以第一行已被选中了,然后对第二行,rand()%2,结果要么为0,要么为1。故第二行有 50的可能性被选中,然后对第三行,rand()%3,显然被选中的概率为1/3。故有:

选中第一行的概率为1 * 1/2 * 2/3 = 1/3

选中第二行的概率为1/2 * 2/3 = 1/3

选中第三行的概率为1/3

故每一行被选中是等概率的。

 

三.生成N个随机数

这个有很多方法,常见方法用set记录已经生成的数据,然后判断set的大小是否符合要求。代码如下所示:

[cpp] view plain copy
  1. //生成n个指定范围的随机数  
  2. #include <stdio.h>  
  3. #include <time.h>  
  4. #include <set>  
  5. //生成n个[s, e)范围的数  
  6. void GetRandNumberInRange(int *a, int n, int s, int e)  
  7. {  
  8.     int   i, j;  
  9.     std::set<int>  m;  
  10.     std::set<int>::iterator setpos;  
  11.       
  12.     srand(time(NULL));    
  13.     while (m.size() < n)  
  14.     {  
  15.         j = rand() % (e - s) + s;  
  16.         m.insert(j);  
  17.     }  
  18.       
  19.     i = 0;  
  20.     for (setpos = m.begin(); setpos != m.end(); setpos++)  
  21.         a[i++] = *setpos;  
  22. }  
  23. void PrintfIntArray(int a[], int n)  
  24. {  
  25.     for (int i = 0; i < n; i++)  
  26.         printf("%d ", a[i]);  
  27.     putchar('\n');  
  28. }  
  29. int main()  
  30. {  
  31.     const int NMAX = 20;  
  32.     const int NUMSTART = 1;  
  33.     const int NUMEND = 100;  
  34.   
  35.     printf("           生成%d个%d到%d之间的数 \n", NMAX, NUMSTART, NUMEND);  
  36.     printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");    
  37.   
  38.     int    a[NMAX];  
  39.       
  40.     GetRandNumberInRange(a, NMAX, NUMSTART, NUMEND + 1);  
  41.     PrintfIntArray(a, NMAX);  
  42.     return 0;  
  43. }  

运行结果如下:

这种方法会导致调用随机函数次数过多,从而效率低下。可以采用一种改进的方法,如要生成3110之间的数,取10-3=7,因此可以先t=rand()%7,保存t,然后再t=rand()%8,如果t这个数已经存在就取8保存,再t=rand()%9,同样如果t这个数已经存在就取9保存。这样只会调用3次随机函数。当然这种方法不能完全保证每个数字被选择概率相同,算是牺牲“公平”来保证效率吧。

生成N个随机数的改进方法代码如下:

[cpp] view plain copy
  1. //生成n个指定范围的随机数  
  2. #include <set>  
  3. #include <cstdio>  
  4. #include <cstdlib>  
  5. #include <ctime>  
  6. //在[s, e)区间上随机取n个数并存放到a[]中  
  7. void GetRandomNum(int *a, int n, int s, int e)  
  8. {  
  9.     std::set<int> set_a;  
  10.     srand(time(NULL));  
  11.     for (int i = e - n; i < e; i++)  
  12.     {  
  13.         int num = (rand() % (i - s)) + s;  
  14.         if (set_a.find(num) == set_a.end())  
  15.             set_a.insert(num);  
  16.         else  
  17.             set_a.insert(i);  
  18.     }  
  19.     i = 0;  
  20.     std::set<int>::iterator pos;  
  21.     for (pos = set_a.begin(); pos != set_a.end(); pos++)  
  22.         a[i++] = *pos;  
  23. }  
  24. void PrintfIntArray(int a[], int n)  
  25. {  
  26.     for (int i = 0; i < n; i++)  
  27.         printf("%d ", a[i]);  
  28.     putchar('\n');  
  29. }  
  30. int main()  
  31. {  
  32.     const int NMAX = 20;  
  33.     const int NUMSTART = 1;  
  34.     const int NUMEND = 100;  
  35.       
  36.     printf("           生成%d个%d到%d之间的数 改进版\n", NMAX, NUMSTART, NUMEND);  
  37.     printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");   
  38.     int a[NMAX];  
  39.       
  40.     GetRandomNum(a, NMAX, NUMSTART, NUMEND + 1);  
  41.     PrintfIntArray(a, NMAX);  
  42.     return 0;  
  43. }  

运行结果如下:

 

有关随机的趣味题就介绍到这里,有任何问题欢迎和我交流,直接留言或发送邮件均可。邮箱:morewindows@126.com

 

下一篇《STL系列十二链表排序的6次改进(对《STL源码剖析》作个补充)》将会对STL中的链表排序进行详细讲解,如果看过《STL源码剖析》书中142页的链表排序代码将会更有收获。更多内容,请继续关注MoreWindows

这篇关于STL系列十一 随机三趣题——随机重排,文件中随机取一行,生成N个随机数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/927473

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系