第一篇：【八斗学院】10.2基于内容的推荐算法(CB)是如何实现的？
基于内容的推荐算法（CB）是如何实现的？
来源：八斗学院
基于内容的推荐（Content Based）应该算最早被使用的推荐方法，它根据用户过去喜欢的产品（本文统称为 item），为用户推荐和他过去喜欢的产品相似的产品。例如，一个推荐饭店的系统可以依据某个用户之前喜欢很多的烤肉店而为他推荐烤肉店。CB最早主要是应用在信息检索系统当中，所以很多信息检索及信息过滤里的方法都能用于CB中。
CB的过程一般包括以下三步：
1)Item Representation：为每个item抽取出一些特征（也就是item的content了）来表示此item；
2)Profile Learning：利用一个用户过去喜欢（及不喜欢）的item的特征数据，来学习出此用户的喜好特征（profile）；
3)Recommendation Generation：通过比较上一步得到的用户profile与候选item的特征，为此用户推荐一组相关性最大的item。
举个例子说明前面的三个步骤。对于个性化阅读来说，一个item就是一篇文章。根据上面的第一步，我们首先要从文章内容中抽取出代表它们的属性。常用的方法就是利用出现在一篇文章中词来代表这篇文章，而每个词对应的权重往往使用信息检索中的tf-idf来计算。比如对于本文来说，词“CB”、“推荐”和“喜好”的权重会比较大，而“烤肉”这个词的权重会比较低。利用这种方法，一篇抽象的文章就可以使用具体的一个向量来表示了。第 学Hadoop大数据，就到八斗学院
www.xiexiebang.com
二步就是根据用户过去喜欢什么文章来产生刻画此用户喜好的 profile了，最简单的方法可以把用户所有喜欢的文章对应的向量的平均值作为此用户的profile。比如某个用户经常关注与推荐系统有关的文章，那么他的profile中“CB”、“CF”和“推荐”对应的权重值就会较高。在获得了一个用户的profile后，CB就可以利用所有item与此用户profile的相关度对他进行推荐文章了。一个常用的相关度计算方法是cosine。最终把候选item里与此用户最相关（cosine值最大）的N个item作为推荐返回给此用户。
接下来我们详细介绍下上面的三个步骤。1)Item Representation：
真实应用中的item往往都会有一些可以描述它的属性。这些属性通常可以分为两种：结构化的（structured）属性与非结构化的（unstructured）属性。所谓结构化的属性就是这个属性的意义比较明确，其取值限定在某个范围；而非结构化的属性往往其意义不太明确，取值也没什么限制，不好直接使用。比如在交友网站上，item就是人，一个item会有结构化属性如身高、学历、籍贯等，也会有非结构化属性（如item自己写的交友宣言，博客内容等等）。对于结构化数据，我们自然可以拿来就用；但对于非结构化数据（如文章），我们往往要先把它转化为结构化数据后才能在模型里加以使用。真实场景中碰到最多的非结构化数据可能就是文章了（如个性化阅读中）。下面我们就详细介绍下如何把非结构化的一篇文章结构化。
如何代表一篇文章在信息检索中已经被研究了很多年了，下面介绍的表示技术其来源也是信息检索，其名称为向量空间模型（Vector Space Model，简称VSM）。记我们要表示的所有文章集合为，而所有文章中出现的词（对
。于中文文章，首先得对所有文章进行分词）的集合（也称为词典）为也就是说，我们有N篇要处理的文章，而这些文章里包含了n个不同的词。我们最终要使用一个向量来表示一篇文章，比如第j篇文章被表示为表示第1个词在文章j中的权重，值越大表示越重要；，其中
中其他向量的解释类似。所以，为了表示第j篇文章，现在关键的就是如何计算
各分量的值了。例如，我们可以
学Hadoop大数据，就到八斗学院
www.xiexiebang.com
选取为1，如果词出现在第 j 篇文章中；选取为0，如果未出现在第j篇文章中。我们也可以选取为词出现在第 j 篇文章中的次数（frequency）。但是用的最多的计算方法还是信息检索中常用的词频-逆文档频率（term frequency–inverse document frequency，简称tf-idf）。第j篇文章中与词典里第k个词对应的tf-idf为：
其中章数量。
最终第k个词在文章j中的权重由下面的公式获得： 是第k个词在文章j中出现的次数，而
是所有文章中包括第k个词的文
做归一化的好处是不同文章之间的表示向量被归一到一个量级上，便于下面步骤的操作。
2)Profile Learning 假设用户u已经对一些item给出了他的喜好判断，喜欢其中的一部分item，不喜欢其中的另一部分。那么，这一步要做的就是通过用户u过去的这些喜好判断，为他产生一个模型。有了这个模型，我们就可以根据此模型来判断用户u是否会喜欢一个新的item。所以，我们要解决的是一个典型的有监督分类问题，理论上机器学习里的分类算法都可以照搬进这里。
下面我们简单介绍下CB里常用的学习算法——KNN：
对于一个新的item，最近邻方法首先找用户u已经评判过并与此新item最相似的k个item，然后依据用户u对这k个item的喜好程度来判断其对此新item的喜好程度。这种做法和CF中的item-based kNN很相似，差别在于这里的item相似度是根据item的属性向量计算得到，而CF中是根据所有用户对item的评分计算得到。
对于这个方法，比较关键的可能就是如何通过item的属性向量计算item之间的两两相似度。[2]中建议对于结构化数据，相似度计算使用欧几里得距离；而如果使用向量空间模型（VSM）来表示item的话，则相似度计算可以使用cosine。
学Hadoop大数据，就到八斗学院
www.xiexiebang.com
3)Recommendation Generation 通过上一步的学习，会得到一个推荐列表，我们直接把这个列表中与用户属性最相关的n个item作为推荐返回给用户即可。
学Hadoop大数据，就到八斗学院
www.xiexiebang.com
第二篇：1-1什么是CB实验室
一、什么是CB实验室？
所谓CB实验室，是指CB体系接受的测试报告被CB各成员认可的实验室。作为CB体系的“最前线单位”，CB实验室“队伍的素质”直接关系到CB报告的公信力。为保证其“贵族血统”，申请成为CB实验室的测试机构，除按IEC25规则对实验室进行体系管理外，还必须具备一流测试能力，经过IECEE专家组层层严格评审，方有可能被批准为CB实验室。
二、企业如何获得CB证书？
CB证书包括CB测试报告和CB测试证书。制造商在国际上申请免于重复测试认证，必须同时提供CB实验室出具的CB测试报告与国家认证机构（NCB）出具的CB测试证书，方为有效。因此，企业申请CB证书，大致分两步走。
第一步，送产品到CB实验室检测，获得测试报告。CB测试报告是由CB实验室出具的一种标准化测试报告，它以一种逐条清单的形式列举相关IEC标准的要求，以及按要求进行的所有测试、测量、验证、检查和评价的结果，包含照片、电路图表、图片以及产品描述等。
第二步，向国家认证机构（NCB）申请CB测试证书。实验室将完成的CB测试报告递交所属NCB进行审核，通过审核后，NCB即颁发CB测试证书。所谓NCB，指颁发电工产品国家范围内认可的合格证书的认证机构。其作用相当于其所辖各CB实验室的总代理，对它们出具的CB测试报告进行审核，审核合格后，由该NCB出具CB测试证书，证明已测试的产品样品符合标准要求，客户便可凭此证书与报告去别国的NCB进行差异测试后换发该国的认证证书。
三、CB实验室的作用
在国际贸易中，由于各国要求的产品测试报告不同，致使同一产品进入不同市场常常需要重复测试，增加了国际贸易成本。因此，亟需一种能够在世界范围内被普遍认可、并作为免于重复测试凭证的证书。而在电工电子产品领域，CB证书的应运而生正是为了实现电气产品进出国际市场“一次测试，多处适用”，免于“重复签证”。
二〇一一年十一月八日下载整理
第三篇：算法及其实现 教学设计(第一课时)
《3.4算法及其实现》教学设计（第一课时）
一、设计思想
随着新课程改革的深入，信息技术课程理念发生了巨大的变化，具体表现为：强调培养学生的信息素养；为学生打造终身学习的平台；关照全体学生的发展；强调培养学生解决问题的能力，运用信息技术创新实践的能力，与人交流合作的能力。新课程要求教师必须改变传统的“教教材”，要 “用教材去教”，要求教学模式由以往的“以教师为主体”转变到“以学生为主体”，提倡“任务型”教学，关注学生的情感态度价值观。
本节课我根据新课标，结合学生的特点对教材的内容进行了深入的挖掘和思考，创作了学生学案，创设丰富的教学情境，提供多样的学习资源。教学以生活中的实际问题和有趣故事作为任务驱动，让学生采用自主、合作、探究、体验等学习方式，通过意义建构获得新知，充分体现学生的主体地位。
二、教材分析
《算法及其实现》是普通高中课程标准实验教科书——《信息技术基础（浙江教育出版社）》的第三章第四节内容，该教材是按照高中信息技术课程标准编写的实验教材。通过学习本节内容可以达到“初步掌握用计算机进行信息处理的几种基本方法，认识其工作过程与基本特征”的课程标准要求。
本节内容是第三章的难点，介绍了算法的基本概念和算法的表示方法。相比较前三节的内容要抽象的多，二本节又是第四节的第一课时，是第二课时《程序设计实例》的知识基础，起到承上启下的作用。本节的学习重点是算法的概念、特点及表示方法；难点是用流程图描述算法。
三、学情分析
从思维品质上来说：高一学生已有使用计算机的感性经验，已经可以 超越简单的技术操作，具备了接受更高层面文化的能力。学生的思维能力已接近成人，他们有旺盛的求知欲，较高的学习自觉性，并具备一定的自学能力，已具有较强抽象思维和逻辑推理能力。
从知识储备上来说：经过前面的学习，学生已经可以使用计算机处理一些实际问题，例如：利用计算机对文字、图片、多媒体信息的处理，但是学生还不了解了使用计算机解决问题的一般过程和解决方法，以及以何种方式来表示。
四、教学目标
（一）、知识与技能：
1、理解算法的含义；
2、了解算法的特点及表示方法；
3、学会用流程图表示算法。
（二）、过程与方法：
1、能初步利用算法解决简单的问题；
2、培养学生的理论联系实际能力和动手操作能力。
（三）、情感态度与价值观：
1、培养学生学习信息技术课程的兴趣；
2、培养学生主动探究和合作学习的意识和能力。
五、重点难点
教学重点：算法的含义、及表示方法 教学难点：用流程图描述算法
六、教学策略与方法
1、学案导学，自主学习
2、问题导入，激情引趣。
3、创设情境，任务驱动。
4、合作探究，交流提高。
七、课前准备
1．教材、教材配套的教师用书、配套光盘 2．学生学案 3．教学课件
4、多媒体教室/大屏幕投影仪
5、将学生分为4人一组，每组都有优、中、差三个不同层次的学生。
八、教学过程
（一）新课导入
同学们，上节课我们讲了声音和视频处理，都是要利用计算机内存储的应用软件来解决处理问题，同样，像我们之前学习的文字处理软件、表格处理软件、多媒体报告处理软件也都是已经编制好的软件帮助我们处理信息。
但是，也有许多问题是没有现成的软件可以借用的，因此，我们必须根据不同的问题和工作要求，设计针对特定问题的解题步骤，编制专用的软件来解决这些问题。
今天开始我们一起来看看如何实际编写一个简单的程序来解决一个特定的问题。
（二）新课教学
1、算法
（1）师生共同完成游戏
师：首先，我们一起来做一个农夫过河的游戏（游戏内容分别用文字和flash动画显示在屏幕上），请同学们按小组讨论，帮农夫设计一个具体的步骤，安全地将这三样东西带过河。
生：分组讨论过河的方案，最终得出了成功的方案。
师：让小组代表与全班同学分享各自的方案，评价各组的方案进而得出正确的步骤并总结：
同学们，这6个步骤是这个游戏中是不可缺少的动作，否则就不能完成总体目标，使问题获得圆满解决。因此，在解决某一问题时我们要把各个步骤都精确的考虑到。
上面这个例子中的解决问题的步骤其实就是编制程序的基础：算法。设计意图：游戏激发学生的兴趣，让学生在完成游戏中已经编出了一个解决问题的算法，让学生轻松进入新知识的学习。
（2）学生阅读，完成学案
师：现在请大家阅读课本3.4.1第一二自然段，完成学案1、2、3题。学生：阅读课本制定内容，完成学案。
学生完成学案时，教师要走进学生，观察学生的完成情况。完成后，学生要对学案的完成做简要展示，教师要对学生的完成情况作简要总结。
师：大家完成的都很好，请同学们告诉我有那些生活中算法的实例呢？ 生：回答（多样）
师：大家说的都很好，乐谱、菜谱、广播体操图解、搬家的次序等等都是生活中的算法，就拿“搬家”来说，是不是设计的次序不一样，搬家的效果就不一样呢？也就是说，解决同一个问题，会有很多种不同的算法，那么什么样的算法更好一点呢？
现在请大家阅读课本3.4.1剩余部分，完成学案4题。学生完成学案时教师引导：
师：方法甲和其他两个方案比较优秀在哪里？节省了什么？
我们在设计算法时应如何做呢？ 生：回答
设计意图：以学案的形式给学生一个一个的任务，让学生自己去尝试、探究，然后在教师的指导下进行小结，接下来再尝试，这样就形成螺旋式的知识学习和能力提高过程。学生的主动和教师的主导都得到充分的发挥。在本节课的教学设计中，教师重视的不应该是结果，而是过程。
2、算法的表示
（1）常见算法的表示形式
师：大家已经知道我们可以编写算法来解决生活中的问题，那么我们可以用什么形式来表示算法呢？请大家阅读课本3.4.2第1自然段，完成学案5题。
完成后要挑选学生回答。（2）流程图
师：通过大家的阅读和总结，流程图是形象直观，便于掌握的描述算法的形式，因此我们需要认真学习如何用流程图描述算法，现在请大家阅读课本3.4.2中2、3、4自然段，完成学案第6题。
生：完成学案第6题。（3）用流程图描述算法
师：我们已经知道了流程图的功能，现在我们就尝试着用流程图来表示算法，需要注意的是在用流程图描述算法之前必须能能够用自然语言描述算法，否则也无法用流程图来描述。
操作一：将大象装冰箱
操作一由老师讲解演示，学生听讲。
操作二：学校上体育课，一般在操场上课，遇到下雨或下雪，改到室内上课，用流程图表示。
操作二由学生独立完成。
生：听老师讲解完操作一之后，完成学案的第7、8题。
操作三：对任意输入的三个整数x，y和z，找出并输出其中的最大值。
操作三老师讲解。
师：操作三用自然语言描述： 1．输入变量x,y,z
2．比较x,y。如果x>y，则x存入以max命名的存储单元中；否则，y存入max 3．比较z和max。如果z>max，则将z存入max。4．输出max。用流程图描述：
课堂练习：对任意输入的三个整数x，y和z，找出并输出其中的最小值。用流程图表示。
听老师讲解后，完成学案第9、10题。
设计意图：本环节设计是充分调动学生的积极性和主动性。教学中不断的给学生新的任务，让学生主动学习，增强技能，在练习设计中注意难度的梯度，让学生不断的战胜困难，而不是一下就被困难吓倒。最后，通过不断的练习，让学生真正掌握知识和技能。
（三）课堂小结
本节课学习了算法的定义、特征、优化和算法的表示方式，并着重学习了如何用流程图表示算法。请同学们在课后完成学案第11、12题，并在小组之间交流。
九、课后作业
1、完成教材P71页上的“练一练”中的第（1）、（2）两题。
2、观察猜数字游戏，尝试画出猜数字游戏算法的流程图。
设计意图：课后作业分为课内作业和课外拓展两部分，让不同层次的学生分别完成。课外拓展部分的算法比较复杂，涉及到了循环结构，可让学生在完成思索的过程中预习第二课时的内容。
十、学生学案（另附）
【问题研讨】
1、信息技术教育，采用任务驱动的形式，围绕一个能激起学生浓厚兴趣的主题展开教学，以学生的探究过程作为学习载体，较之与传统的信息技术课教学，以单纯的计算机知识和计算机操作作为教学内容，更能激发学生强烈的学习欲望。
2、采用学案导学的方式，学生手中都有学案，方便了学习，梳理了思路，提高了效率，更主要的是真正实现了学生主动学习，教师只是引导的教学模式，更加贴近新课程改革的要求。
3、以小组协作学习方式展开教学，使学生的知识、技能的获取变成了多渠道。学生相互之间的只言片语，远胜于教师长篇大论的讲解和繁琐的演示操作，大大提高学生的学习效率和学习兴趣。同时高、中、低不同层次的学生组成小组，充分利用优秀学生资源，进行同伴互助，缩小生生间的差距,改变两极分化的现状。同时也减少教师的课堂工作量，避免了很多学生同时提问教师忙不过来的尴尬局面。
4、自主探究的学习方式，要求学生具有一定的知识准备，并不适合于所有内容的教学。当学生对所要学习的知识毫无所知时，让学生去自主探究要花费很多的时间和精力，大大降低了学生的学习效率，由于受课时限制应有选择的采用。
第四篇：C++ 八种排序算法总结及实现
八种排序算法总结之C++版本
五种简单排序算法
一、冒泡排序
【稳定的】
void BubbleSort(int* a,int Count)//实现从小到大的最终结果 { int temp;for(int i=1;i for(int j=Count-1;j>=i;j--) if(a[j] < a[j-1]) { temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; } } 现在注意，我们给出O方法的定义： 若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n)= O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！） 现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 二、交换排序 【稳定的】 void ExchangeSort(int *a,int Count){ int temp;for(int i=0;i for(int j=i+1;j if(a[j] < a[i]) { temp = a[j]; a[j] = a[i]; a[i] = temp; } } 时间复杂度为O(n*n)。 三、选择法 【不稳定的】 void SelectSort(int *a,int Count){ int temp;//一个存储值 int pos;//一个存储下标 for(int i=0;i temp = a[i]; pos = i; for(int j=i+1;j if(a[j] < temp)//选择排序法就是用第一个元素与最小的元素交换 { temp = a[j]; pos = j;//下标的交换赋值，记录当前最小元素的下标位置 } a[pos] = a[i]; a[i] = temp;} } 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n 所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。 四、插入法 【稳定的】 void InsertSort(int *a,int Count){ int temp;//一个存储值 int pos;//一个存储下标 for(int i=1;i { temp = a[i];//当前要插入的元素 pos = i-1; while(pos>=0 && temp { a[pos+1] = a[pos];//将前一个元素后移一位 pos--; } a[pos+1] = temp;} } 其复杂度仍为O(n*n)。 最终，我个人认为，在简单排序算法中，直接插入排序是最好的。 五、希尔排序法 【不稳定的】 /* * 希尔排序，n为数组的个数 */ void ShellSort(int arr[], int n){ int temp,pos;int d = n;//增量初值 do{ d = d/3 + 1; for(int i= d;i { temp = arr[i]; pos = i-d; while(pos>=0 && temp < arr[pos]){ arr[ pos + d ] = arr[pos]; pos-= d; } arr[ pos + d ] = temp; } } while(d > 1);} //实现增量为d的插入排序 三种高级排序算法 一、快速排序 辅助空间复杂度为O（1） 【不稳定的】 void QuickSort(int *a,int left, int right){ int i,j,middle,temp;i = left;j = right;middle = a[(left+right)/2 ];do { while(a[i] i++; while(a[j]>middle && j>left)//从右扫描小于中值的数 j--; if(i<=j)//找到了一对值 { temp = a[i]; a[i] = a[j]; } a[j] = temp; i++; j--;} } while(i 注意，在扫描过程中，对于给定参考值，对于向右(左)扫描，如果扫描值大(小)于或等于参考值，就需要进行交换。最终得到的结果是，j左边的值都小于参考值，而i右边的值都大于参考值，j和i之间的值都等于参考值。对j左边和i右边的分别使用递归，就可以完成最终的排序。 这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况 1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。 2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。 第一层递归，循环n次，第二层循环2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n)= n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变 成交换法（由于使用了递归，情况更糟），但是糟糕的情况只会持续一个流程，到下一个流程的时候就很可能已经避开了该中间的最大和最小值，因为数组下标变化了，于是中间值不在是那个最大或者最小值。但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。 如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢 于快速排序（因为要重组堆）。 二、归并排序（两种实现方法均要掌握） 【稳定的】 归并排序是一种极好的外部排序方法，即针对数据保存在磁盘上而不是高速内存中的问题。 //以下程序参考数据结构课本P286页的模板,为使用指针链表实现的 #include struct node{ //链表的节点数据 int value;node *next;}; node * divide_from(node * head){ node * position, * midpoint, * second_half;if((midpoint=head)== NULL)//List is empty return NULL;position = midpoint->next;while(position!= NULL)//Move position twice for midpoint's one move { position = position->next; if(position!= NULL) { midpoint = midpoint->next; position = position->next; } } second_half = midpoint->next;midpoint->next = NULL;//在这里将原链拆断，分为两段 return second_half;} node * merge(node * first, node * second){ node * last_sorted;//当前已经链接好的有序链中的最后一个节点 node combined;//哑节点 last_sorted = &combined;while(first!=NULL && second!=NULL){ if(first->value < second->value){ last_sorted->next = first; last_sorted = first; first = first->next; }else { last_sorted->next = second; last_sorted = second; second = second->next; } } if(first==NULL) last_sorted->next = second;else last_sorted->next = first;return combined.next;//返回哑节点的后继指针，即为合并后的链表的头指针 } //这里的参数必须是引用调用，需要这个指引去允许函数修改调用自变量 void MergeSort(node * &head){ if(head!= NULL && head->next!= NULL)//如果只有一个元素，则不需排序 { node * second_half = divide_from(head); MergeSort(head); MergeSort(second_half); head = merge(head, second_half);} } int main(){ node a,b,c,d;node *p1, *p2, *p3, *p4,*head;p1 = &a;p2 = &b;p3 = &c;p4 = &d;a.value = 2;b.value = 4;c.value = 3;d.value = 1;a.next = p2;b.next = p3;c.next = p4;d.next = NULL;//调用归并排序前的结果 head = p1;while(head!= NULL){ cout< head = head->next;} cout< head = p1;while(head!= NULL){ cout< head = head->next;} cout< //以下程序为使用数组实现的归并排序,辅助空间复杂度为O（n） #include void Merge(int data[], int left, int mid, int right){ int n1,n2,k,i,j;n1 = midmid;int *L = new int[n1];//两个指针指向两个动态数组的首地址 int *R = new int[n2];for(i=0,k=left;i L[i] = data[k];for(i=0,k=mid+1;i R[i] = data[k];for(k=left,i=0,j=0;i if(L[i] < R[j]){ //取小者放前面 data[k] = L[i]; i++; } else { data[k] = R[j]; j++; } } if(i for(j=i;j < n1;j++,k++) } /* * left:数组的开始下标，一般为0；right：数组的结束下标，一般为（n-1）*/ void MergeSort(int data[], int left, int right){ if(left < right){ int mid = left +(right-left)/ 2;//mid=(right+left)/2，防止溢出 MergeSort(data, left, mid); MergeSort(data , mid+1, right); Merge(data , left, mid , right);} } int main(){ int data[] = {9,8,7,2,5,6,3,55,1};//排序前的输出 for(int i=0;i<9;i++) cout< for(int i=0;i<9;i++) cout< 三、堆排序 【不稳定的】 /* * 向堆中插入current元素的函数 */ void insert_heap(int data[], const int ¤t, int low, int high) data[k] = L[j];else //if(j for(i=j;i data[k] = R[i];delete []L;//回收内存 delete []R;{ int large;//元素data[low]左右儿子中，大者的位置 large = 2*low + 1;while(large <= high){ if(large < high && data[large] < data[ large+1]) large++; if(current > data[ large ])//待插入元素的值比它的两个儿子都大 break; else { data[ low ] = data[ large ];//将其左右儿子的大者上移 low = large; large = 2 * large + 1; } } data[ low ] = current;} /* * 建立堆函数，num为数组data的元素个数 * 只有一个结点的<2-树>自动满足堆的属性，因此不必担心树中的任何树叶，即 * 不必担心表的后一半中的元素。如果从表的中间点开始并从后向前工作，就 * 能够使用函数insert_heap去将每个元素插入到包含了所有后面元素的部分堆 * 中，从而创建完整的堆。*/ void build_heap(int data[], int num){ int current;for(int low = num/2-1;low>=0;low--){ current = data[ low ]; insert_heap(data, current, low, num-1);} } /* * 堆排序主函数,num为数组data的元素个数 */ void heap_sort(int data[], int num){ int current, last_sorted;build_heap(data, num);//建立堆 for(last_sorted = num-1;last_sorted>0;last_sorted--){ //逐个元素处理 current = data[ last_sorted ];//data[0]在整个数组排序结束前，存储的是待排序元素中最大的元素 data[last_sorted] = data[0]; insert_heap(data, current, 0, last_sorted-1);} } int main(){ //用于排序算法的输入输出 int a[8] = {5,7,1,2,9,4,6,3,};for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< for(int i=0;i< sizeof(a)/sizeof(int);i++) cout< 《对分查找及其算法实现》教学设计 湖北省巴东县第一高级中学 刘少银 一、教材学情分析 本次课是浙江版高中信息技术选修教材《算法与程序设计》第二章算法实例第四节查找中的一部分内容。由于教材体系不适合校本实际，我们在教学过程中对教材体系作了如下调整。 讲授顺序：第一章 算法和算法的表示、第三章 面向对象的程序设计的基本知识、第四章 VB程序设计初步、第二章算法实例，第五章 算法实例的程序实现穿插在相关内容教学中完成。 因此在前期教学中学生已经初步掌握了算法基础及算法表示，VB程序设计初步等。本次课是让学生掌握对分查找的思想及算法的实现。 二、教学目标 知识与技能：理解对分查找的基本含义、方法，理解并能画出对分查找的流程图； 过程与方法：通过案例分析、直观观察，增强分析问题和解决问题的能力； 情感、态度与价值观：感受信息技术与现实生活的关联，激发对信息技术学科的求知欲，培养主动学习和使用信息技术的意识；养成科学的学习态度，不迷信书本、不迷信权威。 三、教学重难点 教学重点：对分查找的基本方法及注意事项； 教学难点：对分查找算法的实现。 四、教学策略 ·以“猜数”游戏导入，引入对分查找的概念； ·师生讨论、生生讨论、生生互助；分析、归纳、总结，理解并掌握对分查找的基本思想； ·采用分类研究、分享成果、课后练习等学习方法，理解对分查找方法及基本主要特征； ·采用自然评价、师生评价、生生评价等形式对学习进行过程性评价。 五、教学过程 1．游戏激趣，释疑对分查找 （三个程序图片） （初始界面）（人工猜数界面）（程序猜数界面） 准备：几张白纸，一支记号笔。启动猜数程序。 师：同学们好！大家看到前面的程序了吗？它是一个什么程序呢？ 同学：猜数游戏程序。 师：对，这是我用VB针对李泳主持的“幸运52”中猜商品价格环节开发的一款程序，我先来说说针对主持人的部分：当李泳宣布商品的价格范围时，比如10000元内，猜商品价格的人就可以在猜数范围栏起始栏填上“0”，终至栏填“10000”，然后再将鼠标移到猜数栏中单击，程序即提示：“准备！倒计时30秒”，当单击提示处，猜价格倒计时开始，猜价格人即可在猜数栏上填上所猜价格的数值，然后根据主持人的提示，选择“不对”重新填写商品价格或选择“正确”让所猜价格在“猜得结果”栏内显示正确结果并停止计时，提示栏中即显示“您猜了M次，对了，恭喜您”。 师：大家觉得程序光有这样的功能神奇吗？ 生：不神奇。 师：对，我也是这样认为的。这个程序神奇的地方在它能帮助猜商品价格人在规定的时间内，根据主持人的提示准确地猜出商品的价格，而且猜中率100%，所以现在“幸运52”停播了，大家知道为什么吗？ 生：不知道。 师：就是因为我开发了这个程序呀！ 生：（有的说信，有的抱着怀疑的态度不吭声，也有说不信的） 师：有同学愿意上来试试吗？ 师：你在纸上写下你的数值范围和要猜的数，然后给大家看一下，别说出来，别让电脑听见了。 师：好，操作程序让程序帮忙把写的数找出来。 （程序找到正确的数） 师：神奇吧。 师：还有那位同学愿意试一下。 师：同样，你还是先写下要猜的数和范围100～200，这次我们不让大家看到他要猜的数，请大家帮忙记下程序每次出现的数字。 师：电脑程序也猜出了正确结果：132。 程序给出的数字是： 第一个数是：150 第二个数是：12 5第三个数是：137 第四个数是：1 31第五个数是：13 4最后是：13 2大家能看出什么规律了吗？ 生：看不出 师：单纯从这几个数当中是看不出什么规律，现在我们依次把这些数放到数轴上，再看一下，大家看能找出什么规律呢？ 同学发言„„ 师：大家认为他说的怎样？为什么不鼓掌呀！ 师：对，正如刚才的同学说的那样，程序是在给定范围内依次找中点方法来找到我们要找的最终数值，这就是我们今天要讨论的一种新的查找方法：对分查找。 师：我们刚才的游戏中的数列是序的吗？ 生：是有序的，升序排列的。 师：如果是降序能用对分查找方式查找吗？ 生：能。 师：大家想一想，如果我们打乱数据的排序顺序，在没有排序的数列中能否用对分查找的方法，找到我们想找到的数据？ 同学：不能。 师：对，这就是对分查找方法的一个特征，或称为条件。因为我们是根据数据的大小找到它在数列中的位置。 【设计意图】通过游戏和对程序给出数值在数轴上的分布分析，让学生初步理解和掌握对分查找的方法及前提条件，为后一阶段对分查找算法的实现作好铺垫。 2．分析实例，实现对分查找算法 师：下面我们一起来看一下程序是怎样一步一步的给出以上数据并最终找到“132”这个数的。 师：首先在100至200之间找中点，然后再用中点值150与所要找的数132比较，得出的结论是所要找的数在100至150之间的数，一下数值的范围就缩小了一半，终止变量j的值就由200变成了150；第二次查找时，程序就给出100至150的中点值125；当程序进行第三次查找时，起始变量i的值就被修改为125，它们的中点值应该是：（125+150）/2=137.5。有小数了，怎么办？ 生：„„（有点茫然） 师：对于小数，程序可以继续查找，但有可能要增加查找次数。为了保证在整数范围内查找，我们就要对含小数的中间值进行处理：取整。大家还记得我们学过VB的取整函数吗？ 生：int。 师：对。即int（137．5），结果是多少？ 生：137。 师：所以我们查找i到j范围内的中点值的表达式应该为：m=int（（i+j）/2）。 师：依次类推，程序会依次给出131、134、132即找到了要找的数。 师：请同学们根据算法逐步求精的原则在下面画出流程图。 （展示如下流程图，然后请同学完成完善对分查找的算法流程图） 流程图补充完善后的结果： 【设计意图】通过对程序给出中间数的分析，帮助学生理解对分查找算法实现的方法，为学生顺利完成对分查找算法流程图给予理论与实践上的支持。 3．推出特例，完善对分查找算法 师：同学们，刚才我们完成的对分查找的流程图；下面请同学们用刚才的查找方法分析一下在199至200范围内要找200这个数，能找到吗？为什么？如何解决这个问题？ （将教室内学生按座位分成若干组，进行讨论。每个组推选一名小 组长，完成后作小组发言） „„ （每一小组完成发言后，老师或点评，或让学生点评） 师：根据刚才同学的讨论分析，那我们先前给出的流程图就有了一些缺陷，怎么修改？ （在同学们的发言声中，修改完善流程图） 修改后的流程图如下： 【设计意图】给出特例，让学生相互讨论、互助学习，归纳总结出上述流程图中出现问题的症结所在，并给出正确的流程图；由此可让学生体验到科学探究的方法，从而培养学生的科学态度与探索精神。 六、课后作业 师：1．在前面的取整中我们用了取整函数int，大家想一想能不能用四舍五入函数处理？如果用四舍五入函数（round）处理，流程图又将怎样修改？ 2．请看教材P40-43，比较我们所给出的流程图与教材上的流程图有什么差异？两个流程图最后结果是否一致，那个流程图的结果有问题，问题是怎么造成的？请写出一篇500—800字的小论文。 （提示：认真阅读教材P40至P43内容，并分析教材中所给算法的逻辑错误） 作业提交方式：电子邮件（校内、校外均可） 邮件名称：登分号+姓名+论文题目 作业提交地址：bdxyz@qq.com 【设计意图】作业（1）扩充课堂内容，丰富学生知识面，丰富学生分别学习内容；作业（2）通过两个流程图之间差异性比较，引导学生判别书本上所给出流程图的逻辑错误，从而培养学生：1．科学的学习态度和精神，不迷信教材、不迷信权威；2．运用论文等形式来表达自己观点；3．通过学生自己的分析、探索，找出教材中的错误。 七、教学反思 整节课充满了笑声和掌声，课堂气氛活跃，学生参与度高。老师的主导作用和学生的主体地位得到了充分的体现。学生在师生互动、生生讨论、生生互助中比较好地掌握了对分查找的思想和算法实现，教学效果好。但由于时间关系，没有将程序的源代码展示给学生，让学生有一种意犹未尽的感觉是本次课的一个缺憾。第五篇：《对分查找及其算法实现》教学设计
点击咨询 