社团统计问题.ppt_第1页
社团统计问题.ppt_第2页
社团统计问题.ppt_第3页
社团统计问题.ppt_第4页
社团统计问题.ppt_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、社团统计问题,学号:100320071 姓名:黄晞 报告时间(2010-10-22),问题描述,FZU里有许多社团，当然，每个同学也积极的参与了自己喜欢的社团。 现在，小Z要统计学校里共里几个社团，但他又不好意思直接问每个同学“你参加了哪个社团？”，因此，他招募了一些人手，去询问N个人中的任意两个人是否属于同一个社团。最后，得到了一些数据。,对问题的理解和分析,题目的意思就是给出M行数，每行数包含2个整数，表示这2个人在同一个社团，其中每个人只能参加一个社团。 例如： 输入： 1 2 表示1号和2号参加同个社团 2 3 表示2号和3号参加同个社团 因此1、2、3在同一个社团。 输入M行数后，根

2、据总人数N（这N个人都参加了社团）来统计出共有多少个社团。,算法与数据结构的选取,算法设计： 关键就是如何表示学生加入的社团以及如何查找某个特定学生是否在该社团中。 基本算法： 1、用一种树的结构来表示每个集合（即社团）,1,2,4,3,5,1,2在集合（社团）1中,3,4,5,6在集合4中,6,算法与数据结构的选取,2、定义一个数组setn， seti = i , 则i表示本集合，并是集合对应树的根 seti = j, j！=i, 则 j 是 i 的父节点.,4,3,5,如左图，此集合的根结点为4， 此时，set数组为,6,算法与数据结构的选取,3、对于每组输入数据x,y，分别查找出他们所在

3、的集合的父节点，然后将这2个集合合并。 4、合并的算法就是找出x所在集合的根结点（假设是k），令setk=（y所在的集合的根结点）。 比如输入：2 3 则合并这2个集合 5、输入完后，遍历数组set，找出其中seti=i的个数，就是最终要统计的社团个数。,1,2,4,3,5,1,2,4,3,5,核心代码,int findset(int i)/找出第i个人是属于哪个集合 if (seti=i) return i; seti=findset(seti);/递归找到seti所在的那个集合的根结点 return seti; int main() while(m-) cinxy; setfindset(x)=findset(y)； /合并x,y所在的集合 ,算法复杂度分析,输入时间复杂度O(n) 最后遍历数组找出社团数，需要时间O(n) while(m-) cinxy; setfindset(x)=findset(y)； /合并x,y所在的集合 其中findset(x)是递归函数， 写成非递归形式就是： while (seti!=i) i=seti; 最差情况为O(n) 所以整个算法的时间复杂度为O(m*n),1,2,n,最差情形 当i=n时，要查找n-1次才能找到根结点,算法的优缺点分析和改进,缺点就是最差情形时会严重影响算法的执行效率 算法的改进：避免最差

人人文库> 全部分类> 专业文献 > 金融证券

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论