3.3枚举算法及程序实现（2）.ppt

1、1双重循环：某些枚举算法的问题比较复杂，需要通过复杂的双重循环来实现。双重循环就是循环的嵌套，在一层循环结构内部又是另一层循环，其结构如下所示： For i 语句块 For j 语句块 Next j Next i,33枚举算法及程序实现(2),此结构由两个For循环构成，外循环是循环变量为i的循环，内循环是循环变量为j的循环，这两个循环之间的关系是嵌套关系，循环变量为i的循环将循环变量为j的循环包含在内，在循环执行时，外循环变量i每变化一次，都要执行一次完整的内循环。 在枚举算法中，有很多时候用到循环的嵌套来解决问题。,2循环嵌套：循环嵌套的层数没有具体限定，选考时的多重循环结构一般只要求到双

2、重循环。多重循环在使用时，每个循环必须只有一个唯一的变量名作为循环变量；在Next语句结束循环时，必须内循环先结束，不得出现互相交叉。 3编写枚举算法的程序要注意两个要点: For循环的范围要尽可能的小，这决定可能解的范围是否已经尽可能的小； 条件表达式必须要正确无误，这决定哪些解才是真正的解。,4素数问题 素数的概念 素数(质数)就是一个大于等于2的整数，并且只能被1和本身整除，而不能被其他整数整除的数。 算法说明 判别某数n是否是素数的经典算法是，对于n，从i2,3,4，n1依次判别能否被i整除，只要有一个能整除，n就不是素数，否则n是素数。,代码实现 Function sushu(n A

3、s Long) As Boolean 定义素数函数 Dim i As Long For i 2 To n 1 If (n Mod i) 0 Then Exit For Next i If in then sushuTrue End Function,5最大公约数问题 最大公约数：就是几个数共同最大的约数。 算法说明：用辗转相除法求两自然数m、n的最大公约数，再由最大公约数求出最小公倍数。 首先，对于已知两数m、n，比较并使得mn； m除以n得余数r； 若r0，则n为求得的最大公约数，算法结束；否则执行步骤； 使mn，nr再重复执行。,代码实现： Function gcd(m As Long,

4、n As Long) As Long Dim temp As Long If m n Then temp m: m n: n temp Dim r As Long Do while r m Mod n If r 0 Then Exit Do m n n r Loop gcd n End Function,本节课学习多重循环的程序实现方法，难点是理解内循环与外循环的概念，并能根据算法编写简单的多重循环代码。掌握常见素数问题算法与最大公约数问题算法。考查方式为选择题与填空题。,有如下VB程序段： For i0 to 3 For j5 to 1 Step 1 If i*j7 Then si*j Ne

5、xt j Next i 则语句si*j的执行次数是 () A15B4C5D20,C,2某工厂购入100千克原材料，每4千克原材料可以生产一件 A产品，每5千克原材料可以生产一件 B产品。下列VB程序的功能是：计算恰好用尽这些原材料时，生产 A产品 和B产品数量的各种可能，并在列表框中输出。,Private Sub Command1_Click() Dim x As Integer, y As Integerx、y分别为 A、B产品的数量 For x0 To 25 For y0 To 20 If Then List1.AddItem“A产品”Str(x)“件， ” “B产品”Str(y)“ 件”

6、 End If Next x End Sub 请在划线处填入合适代码。 (1)划线处应填入_。 (2)划线处应填入_。,(x*4+y*5)=100,Next y,3一个十进制数的二进制表示中，如果数字“1”的个数多于数字“0”的个数，则称该整数为A类数。如十进制整数26的二进制表示为11010,26是一个A类数。下列VB程序的功能是：统计前1000个自然数中A类数的个数，并在文本框Text1中输出。,Private Sub Command1_Click() Dim i As Integer, n As Integer Dim s As Integer s为 A类数的个数 Dim t As In

7、teger t为二进制数中的“1 ”的个数 Dim k As Integer k为二进制数中的“ 0 ”的个数 s0 For i1 To ni：t0：k0 Do While n0 If n Mod 21 Then tt1 else kkl n n2 Loop If Then ss1 Next i Text1.Text Str(s) End Sub 请在划线处填入合适代码。 (1)划线处应填入_。(2)划线处应填入_。,1000,tk,4寻找勾股数：“勾股数”是指满足勾股定理关系的一组数，也就是直角三角形三边长恰好都取整数的特殊情况。3、4、5就是一组勾股数324252。请编程实现30以内能够组

8、成勾股数的整数组及组数。该程序运行界面如下图所示：,程序代码如下： Private Sub Command1_Click() Dim a As Integer, b As Integer, c As Single Dim s As Integer s 0 For a 1 To 30 For b a 1 To 30 c If Then s s 1 List1.AddItem (Str(a) Str(b) Str(c) End If Next b Next a Label1.Caption “共找到” Str(s) “勾股数。” End Sub 请在划线处填入合适代码。 (1)划线处应填入_。 (

9、2)划线处应填入_。 注：该示例程序在素材文件夹下vb18文件夹中。,Sqr(a2+b2),c=Int(c) And c=30,设计一个VB程序，求100以内所有素数的和。该程序运行后界面如下：点击“找素数”按钮Command1，在列表框List1中显示所有100以内的素数，并在标签Label1中显示所有素数的和。,程序代码如下： Private Sub Command1_Click() Dim n As Integer Dim i As Integer Dim sum As Integer s 0 For n 1 To 100 For If (n Mod i) 0 Then Exit For

10、 Next i If i n Then List1.AddItem n End If Next n Label1.Caption “所有的素数和为” Str(sum) End Sub 请在划线处填入合适代码。 (1)划线处应填入_。(2)划线处应填入_。,sum=sum+n,i=2 to n-1,某电视台的直播节目结束后，主持人从参与短信投票的观众中抽取若干名幸运观众。假设共有500名观众参与短信投票，抽奖程序的部分VB代码如下，程序运行时界面如图所示。主持人在文本框Text1中输入幸运观众数量后，单击“开始”按钮Command1，在列表框List1中显示幸运观众的手机号码。请在划线处填入合适

11、的代码。,Dim a(1 To 500) As String参与短信投票观众的手机号码 Form_load过程用于将参与短信投票观众的手机号码存放到数组a中 Private Sub Form_Load () 该过程代码略 End Sub Private Sub Command1_Click() Dim n As Integer 幸运观众的数量 Dim t As Integer 幸运观众的序号 Dim i As Integer Randomize (1) List1.Clear For i1 To n t Int(Rnd*500)1 Do While _(2)_ True t Int(Rnd*5

12、00)1 Loop List1.Addltem Mid(a(t),1,3)“*”Mid(a(t) ,8,4) Next i End Sub,check函数用于判断随机产生的幸运观众的序号是否重复 Private Function check(t As Integer)As Boolean 函数值为True表示序号重复 该函数代码略 End Function 请在划线处填入合适代码。 (1)划线处应填入_。 (2)划线处应填入_。,n=Val(Text1.text),Check(t),将一张100元的钞票兑换成面值为20元、10元和5元的钞票，要求每种至少有1张，共有多少中不同的换法？程序运行时

13、的界面如下所示，点击“计算方案”按钮Command1，在列表框List1中显示详细的兑换方案列表，同时在标签Label1中显示兑换方案的总数。,程序代码如下所示： Private Sub Command1_Click() Dim a As Integer存储20元张面值张数 Dim b As Integer存储10元张面值张数 Dim c As Integer存储5元张面值张数 Dim i As Integer存储兑换方案数 i 0 For a _ For b 1 To 9 For c 1 To 19 If _ Then i i 1 List1.AddItem ”第” Str(i) ”种方案：

14、” Str(a) ”*20” Str(b) ”*10” Str(c) ”*5” End If Next c Next b Next a Label1.Caption ”共有” Str(i) ”种兑换方案。” End Sub 请在划线处填入合适代码。 (1)划线处应填入_。(2)划线处应填入_。 注：该示例程序在素材文件夹下vb20文件夹中。,1 to 4,a*20+b*10+c*5=100,在1000个奇自然数中，计算恰好有三位为1的二进制数的个数(例如19对应的二进制数10011，是一个符合题目要求的数字，而23对应的10111，则不符合本题目的要求)。 解决此问题的算法如下： 计数器c的初

15、值置为 0,For i1 To 1000 计算第 i个奇数 j：j2使用除2取余法将 j化成为二进制数，并统计其中1的位数 w 计数器 w的初值置为 0 Do while j0 计算 j除以2的余数 n If余数 n是1 Then ww1 j的值缩小1/2 Loop If w3 Then cc1 输出j 输出j的二进制编码 End if Next i,程序运行界面如下：,相应的VB程序如下： Private Sub Command1_Click() Dim c As Integer, i As Integer, j As Integer, w As Integer, n As Integer

16、Dim s As String List1.Clear c 0 For i 1 To 1000 j 2 * i 1 w 0 s “” Do While j 0 (1) If n 1 Then w w 1 (2) s s Str(n) Loop If w 3 Then c c 1 List1.AddItem Str(2 * i 1) “：” s End If Next i Label1.Caption “个数： ” Str(c) End Sub,N=j2,j=j2,程序加框处代码有错，请改正。 (1)加框处有错，应改为_。 (2)加框处有错，应改为_。 注：该示例程序在素材文件夹下vb21文件夹中。,n=j Mod 2,j=j2,求两数最大公约数的VB程序代码如下： Function gcd(m As Long, n As Long) As Long Dim temp As Long If m n Then temp m: m n: n temp Dim r As Long Do r m Mod n If r 0 Then Exit