教科版 (2019)选修1 数据与数据结构第2单元 线性表及其应用2.2 随机抽取问题图文ppt课件

这是一份教科版 (2019)选修1 数据与数据结构第2单元 线性表及其应用2.2 随机抽取问题图文ppt课件，共11页。PPT课件主要包含了学习目标，任务一体验随机抽取，知识点一随机抽取等内容，欢迎下载使用。
掌握利用线性表解决随机抽取问题的方法
理解随机抽取问题的概念及实现过程
参加知识竞赛活动时，有个抽取幸运观众环节，就是在参加活动的人群中抽取观众的编号或者姓名作为幸运观众。本任务中，我们通过抽取观众编号形式实现，规则如下（1）幸运观众数量少于观众数量；（2）被抽中的观众编号不再参加此后的抽取活动。 假设现场有200名观众，观众编号范围1-200，需要从中随机抽取10名幸运观众，抽取过程如下（1）第一次随机抽取1名幸运观众，如果抽到了180号，那么180号不能再参与下次抽取过程，第二次在199名观众中抽取；（2）第二次抽到了88号，那么（ ），第三次在（ ）名观众当中随机抽取；（3）以此类推，最后一次，是在（ ）名观众当中随机抽取。
随机抽取：是指在一个有限数量的数据集范围内，随机选择其中的某一个数据元素的过程。 随机抽取的分类：随机抽取分为有放回抽取和无放回抽取。 有放回抽取：允许同一个数据元素被抽取多次（抽取出来的元素放回数据集中） 无放回抽取：只允许同一个数据元素被抽取一次（抽取出来的元素不得放回数据集中）。本节中我们重点学习无放回抽取
第一：题目数量和参赛选手数量相同
第二：抽中的题目不再放回
知识竞赛中随机抽取题目环节的规则如下：
第一次抽取：假设一号选手通过摇号方式抽到了3，那么三号题“题C”，被预抽取题目中去掉，其他的9道题供选手抽取。抽取后的状态如下：
第二次抽取：假设二号选手通过摇号方式抽到了6，那么会有什么样的变化？如果按照上述规则抽题，第六号选手抽题时的摇号范围是什么？
通过观察知识竞赛活动的抽题和选幸运观众时的位置变化可知，这种案例可以通过线性数据结构的线性表来实现。
通过Pythn代码来实现知识竞赛抽题案例或者幸运观众案例都会用的到线性表，用线性表时需要创建线性表对象stulist和cntestlist，作用是分别放幸运观众编号和竞赛题目，步骤如下：
第一步：建立数据结构相关代码如下：imprt randm #导入randm（随机） 模块frm linearList imprt LinearList #导入线性表stuList = LinearList() #创建线性表对象，存放观众编号cntestList = LinearList( ) #创建线性表对象，存放竞赛题目第二步：设计算法假设需要从M位观众中随机抽取N位幸运观众，由N位幸运观众来抽取N道题目，根据知识竞赛的规则，实现随机抽取的算法描述如下：（1）需要进行N次抽取；（2）观众总人数可看成一个随机数集合，跟这个随机数集合中抽取幸运观众编号，每次抽到的观众的编号删除总人数中；（3）可抽取题目数可看成随机数集合，每次抽到的题目删掉总题目中；（4）显示抽取结果
第二步：设计算法根据上述算法，自定义随机抽取函数randSelect（stuList，cntestList）代码如下：def randSelect(stulist,cntestlist): #随机抽取函数 n= cntestlist.size() #确定抽取次数 fr i in range(n): randstu= randm.randrange(stulist.size()) #生成随机数确定观众编号位置 stunum=stulist.getItem(randstu) #获取观众编号 stulist.remveItem(randstu) #删除抽中的观众编号 randtest=randm.randrange(cntestlist.size()) #生成随机数确定题目位置 testnum=cntestlist.getItem(randtest) #获取题目 cntestlist.remveItem(randtest) #删除抽中的题目 print("第",stunum,"号观众抽取的题目为:",testnum) #显示抽取结果
第三步：编程实现假设参赛活动的观众人数200人，观众编号是1-200，随机抽取的题目是以下10个：唐诗，互联网，微信，雾霾，人工智能，二维码，虚拟现实，3D打印，物联网，网络爬虫，代码如下：fr i in range(1,201): stulist.appendItem(i)cntestlist.appendItem("唐诗")cntestlist.appendItem("互联网")cntestlist.appendItem("微信")cntestlist.appendItem("雾霾")cntestlist.appendItem("人工智能")
cntestlist.appendItem("二维码")cntestlist.appendItem("虚拟现实")cntestlist.appendItem("3D打印")cntestlist.appendItem("物联网")cntestlist.appendItem("网络爬虫")randSelect(stulist,cntestlist) #调用随机抽取函数