桶排序学案公开课.docx
桶排序学案学习目标：1 .理解桶排序的算法思想.掌握桶排序算法思想在VB程序中的应用一、桶排序基本思想最快最简单的排序：桶排序接下来出场的我们的主人公小哼，旁边这个可爱的娃就是啦。 期中考试结束了，老师要将同学们的分数按照从高到低排序。小 哼的班上只有5个同学，这5个同学分别考了 5分、3分、5 分、2分和8分，哎考的真是惨不忍睹（总分值是10分）。接下 来将分数进行从大到小排序，排序后是85 5 32。你有没有什么 好方法编写一段程序，让计算机随机读入5个数然后将这5个 数从大到小输出。如以下图所示，桶排序的算法思想是这样的：要对分数进行排序，可以通过这样的方法来 实现，假设有11个桶，编号为0-10o每出现一个数，就在对应编号的桶中放一面小旗子, 最后只要数数每个桶中有几面小旗子就可以了。例如2号桶中有1面小旗子，表示2号出现 一次；3号桶中有1面小旗子，表示3出现一次；5号桶中有2面小旗子，表示5出现两次； 8号桶中有1面小旗子，表示8出现了一次。0 0 0 0 0在输出时，如果是升序排序只要按照桶的编号，从小到大对桶进行检查，如果发现桶里 面只要有1面以上的小旗子（非空）就输出桶的编号，如果有2面小旗子就连续输出两次, 依此类推这样就快速实现升序排列了。而如果是在排序时去除重复的数据，就更快了。一般来说，桶的算法思想主要有以下三种功能：L桶计数功能、2.桶排序功能、3.验证 数据是否存在。桶排序的解题模型:For i = 1 To n b(i) = 0 Next is = Text!. TextFor i = 1 To Len (s)c = Mid(s, i, 1)'数据处理Next iFor i = 1 To nIf b(i) > 0 ThenListl. Additem '输出End IfNext初始化：“洗桶”处理：“装桶” 输出：“数桶”二、桶排序练一练例1：桶排序的算法思想：如图a所示，有10个桶，编号为1-10。每出现一个数，就在对 应编号的桶中放一面小旗子，最后只要看每个桶中有几面小旗子就可以了。例如2号桶中有 1面小旗子，表示2号出现一次；3号桶中有1面小旗子，表示3出现一次；5号桶中有2 面小旗子，表示5出现两次；8号桶中有1面小旗子，表示8出现了一次。最后只要按桶的 编号顺序逐次输出非空的桶编号即可实现排序功能。3 3 0 0 0小哼同学利用桶排序的算法思想实现对5个1,10随机整数的排序过程。实现上述功能 的VB程序如上图b所示，请在划线处填入合适的代码：O桶排序一 口 X23558排序DimDimForDimDimFora(lb(li=lToToto5) AsInteger '数组a用于存放产生的随机整数10) As Integer '数组b相当于桶10b(i)=0Next iFor i = 1 To 5a(i)=int (Rnd*10)Listl. Addtem Cstr(a(i)Next iFor i = 1 To 10for j=l to_List2. AdditemNext jNext iEnd Sub例2：数字频率统计：小哼同学编写VB程序，实现如下功能：在Textl中输入一串包含数字 的任意字符串，单击“统计”按钮Commandl,在列表框Listl中统计并输出数字0-9出现 的次数，并在标签框Labell中输出出现次数最多的数字(次数相同的数字只要输出其中的 第一个)。运行界面如下图，VB程序代码如下：0数字统计一 口 X86-570Phone86-570Phone了了了了了了了了了了 现现现现现现现现现现 出出出出出出出出出出 0123456789出现次数最多的数字是：5为实现上述功能，请在划线处填入合适的代码。Private Sub Commandl_Click ()Dim a(0 To 9) As Integer, s As StringFor i = 0 To 9If Dim k As String, i As Integer, max As Integer s = Textl.TextListl. ClearFor i = 1 To Len (s)k = Mid(s, i, 1)If k = 0 And k 二 9 Then Thenmax = iEnd IfListl. Additem Str (i) & 出现了：&a(i)& 次Next iLabell. Caption = 出现次数最多的数字 是： & Str (max)End SubEnd IfNext i max = 0课后作业：1.某VB程序段如下：Dim a(l To 5) As IntegerDim b(l To 10) As Integera(1)=7:a(2)=5:a(3)=9:a(4)=4:a(5)=3For 仁 1 To 5b(a(i) = b(a(i) + 1Next ipa=0For j= 1 To 10For k= 1 To b(j)pa=pa+ 1a (pa) = jNext kNext j该程序段运行后，数组元素a(l)到a(5)的数据依次是()A. 7, 9, 5, 4, 3B. 3,4, 5,7, 9C. 4, 5, 7, 9, 3D. 9, 7, 5, 4, 32.有以下VB程序段：a(l) = 58: a(2) = 38: a(3) = 46: a(4) = 40: a(5) = 58a(6)= 30: a(7)= 48: a(8) =50: a(9) =36: a(10) =56For i = 1 To 10b(a(i) mod 10) = b(a mod 10) + 1Next i s=For i = 0 To 9If b(i) > 0 Then s = s+ +str(i) + ： + Str(b(i)Next i数组b各元素初值为0,执行该程序段，s的值是(A. 3： 4 4： 3 5： 4B. 3： 4 4： 3 5： 4C. 8： 4 6： 3 0： 3C. 5： 4 4： 3 3： 4D. 0： 3 6： 3 8： 43 .有如下VB程序段：【提示：“a”的ASCII码是97i=l :n=0Do While i二 Len (Textl. Text)c 二 Mid(Textl. Text, i, 1)If Asc (c) >= 105 and Asc (c) <= 115 Then m = 0 Else m = 1a(m)= a(m) + 1If a(m)= 1 Then n = n + 11 = i + 1Loop数组a中各元素的初始值为0,文本框Textl的内容为“china"。执行程序后，变量n 的值为()A.4B. 3C. 2D. 14 .有VB编写的程序如下：Private Sub Command 1 _Click ()Dim a(0 To 9) As IntegerDim t as Longt = Vai(Textl. Text)Do While t<>0a(t Mod 10) = 1t=t10LoopFor i= 0 To 9x=x+aNext iEnd Sub假设在文本框Textl中输入10242048,那么程序执行后，变量x的值为()A. 1B. 2C. 5D. 10.有如下VB程序段：Dim a(0 to 9) As Integers = Textl. TextListl. ClearFor i = 1 To Len (s)k = Mid(s, i, 1)a (Vai (k) = 1Next ians = 0: n = 0: i = 9Do While i >= 0 And n < 3If a(i) = 1 Thenans = ans * 10 + in = n + 1End If= i - 1LoopLabel 1. Caption = Str (ans)数组a中原始数据均为0,在文本框Textl中输入“533774”，运行程序段后，Label 1中显示 的内容是()A. 9876 B. 754 C. 775 D. 7754 6.小王编写了一个依据成绩计算名次的VB程序，成绩为0至U 100之间的整数。算法的基本 思想：先统计每个分数的个数，然后按照分数从高到低依次计算每个有效分数（该分数的个 数不为0）对应的名次，分数相同时名次并列。最高分为第1名，该分数的名次与个数之和 为下一个有效分数的名次，以此类推。程序用数组A存放每个分数对应的个数，数组B存放 每个分数对应的名次。例如，下表中最高分100有2个，并列第1名，那么分数96的名次为 分数100的名次加上分数100的个数,即第3名。分数100999897969594 0个数（A数组）2000103 0名次（B数组）134 程序运行时，学生数据显示在列表框Listl中，单击“计算”按钮Commandl,计算结果显 示在列表框List2中，程序运行界面如下图。5计箕名次821361231A 1A滑玉婷nii计算I7587008576006596 澧王、-s-红Bui实现上述功能的VB程序如下，请回答以下问题：(1)如表所示，假设分数93的个数为2,那么该分数对应的名次为(2)请在划线处填入合适的代码。Dim sName(1 To 50) As String'存放学生姓名Dim sScore (1 To 50) As Integer'存放学生分数Dim recCount As Integer'存放学生人数Private Sub Form Load ()'本过程从数据库中读取学生数据，存储 在相应的变量中，并在Listl中显示'代码略End Sub'整数转换成长度固定的字符串Function ads (x As Integer, n As Integer)As StringDim sx As String, nx As Integer, i As Integersx = Str (x): nx = Len (sx)For i = 1 To n - nx .sx =+ sxNext iEnd FunctionPrivate Sub Commandl_Click ()Dim A(0 To 100) As Integer'存放每个分数的个数Dim B(0 To 100) As Integer'存放每个分数的名次Dim me As Integer, score As Integer, i As IntegerFor i = 0 To 100A(i) = 0Next iFor i = 1 To recCount'计算每个分数的个数Next i me = 1For i = 100 To 0 Step -1'计算每个分数的名次If A(i) <> 0 Then B(i)= meEnd IfNext iList2. ClearList2. Additem 姓名 分数 名次List2.Additem For i = 1 To recCount score = sScore (i) me = B (sScore(i)List2. Additem sName (i) + ads (score, 5) + 第 + ads (me, 3) + 名Next iEnd Sub
