3.3枚举算法及程序实现(2)课件.ppt

1、1双重循环：某些枚举算法的问题比较复杂，需双重循环：某些枚举算法的问题比较复杂，需要通过复杂的双重循环来实现。双重循环就是循环的嵌要通过复杂的双重循环来实现。双重循环就是循环的嵌套，在一层循环结构内部又是另一层循环，其结构如下套，在一层循环结构内部又是另一层循环，其结构如下所示：所示：For i语句块语句块 For j 语句块语句块Next jNext i33枚举算法及程序实现枚举算法及程序实现(2)此结构由两个此结构由两个For循环构成，外循环是循环变量为循环构成，外循环是循环变量为i的的循环，内循环是循环变量为循环，内循环是循环变量为j的循环，这两个循环之间的关的循环，这两个循环之间的关系

2、是嵌套关系，循环变量为系是嵌套关系，循环变量为i的循环将循环变量为的循环将循环变量为j的循环的循环包含在内，在循环执行时，外循环变量包含在内，在循环执行时，外循环变量i每变化一次，都要每变化一次，都要执行一次完整的内循环。执行一次完整的内循环。在枚举算法中，有很多时候用到循环的嵌套来解决问在枚举算法中，有很多时候用到循环的嵌套来解决问题。题。2循环嵌套：循环嵌套的层数没有具体限定，选考时循环嵌套：循环嵌套的层数没有具体限定，选考时的多重循环结构一般只要求到双重循环。多重循环在使用的多重循环结构一般只要求到双重循环。多重循环在使用时，每个循环必须只有一个唯一的变量名作为循环变量；时，每个循环必须

3、只有一个唯一的变量名作为循环变量；在在Next语句结束循环时，必须内循环先结束，不得出现互语句结束循环时，必须内循环先结束，不得出现互相交叉。相交叉。3编写枚举算法的程序要注意两个要点编写枚举算法的程序要注意两个要点:For循环的范围要尽可能的小，这决定可能解的范循环的范围要尽可能的小，这决定可能解的范围是否已经尽可能的小；围是否已经尽可能的小；条件表达式必须要正确无误，这决定哪些解才是真条件表达式必须要正确无误，这决定哪些解才是真正的解。正的解。4素数问题素数问题素数的概念素数的概念 素数素数(质数质数)就是一个大于等于就是一个大于等于2的整数，并且只能被的整数，并且只能被1和本身整除，而不

4、能被其他整数整除的数。和本身整除，而不能被其他整数整除的数。 算法说明算法说明判别某数判别某数n是否是素数的经典算法是，对于是否是素数的经典算法是，对于n，从，从i2,3,4，n1依次判别能否被依次判别能否被i整除，只要有一个能整整除，只要有一个能整除，除，n就不是素数，否则就不是素数，否则n是素数。是素数。代码实现代码实现Function sushu(n As 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 En

5、d Function 5最大公约数问题最大公约数问题最大公约数：就是几个数共同最大的约数。最大公约数：就是几个数共同最大的约数。算法说明：用辗转相除法求两自然数算法说明：用辗转相除法求两自然数m、n的最大公的最大公约数，再由最大公约数求出最小公倍数。约数，再由最大公约数求出最小公倍数。首先，对于已知两数首先，对于已知两数m、n，比较并使得，比较并使得mn；m除以除以n得余数得余数r；若若r0，则，则n为求得的最大公约数，算法结束；否则为求得的最大公约数，算法结束；否则执行步骤；执行步骤；使使mn，nr再重复执行。再重复执行。代码实现：代码实现：Function gcd(m As Long, n

6、 As Long) As Long Dim temp As Long If m 7 Then si*jNext jNext i则语句则语句si*j的执行次数是的执行次数是 ()A15B4C5D20C C 2某工厂购入某工厂购入100千克原材料，每千克原材料，每4千克原材料可以生产千克原材料可以生产一件一件 A产品，每产品，每5千克原材料可以生产一件千克原材料可以生产一件 B产品。下产品。下列列VB程序的功能是：计算恰好用尽这些原材料时，生程序的功能是：计算恰好用尽这些原材料时，生产产 A产品产品 和和B产品数量的各种可能，并在列表框中输产品数量的各种可能，并在列表框中输出。出。Private

7、Sub Command1_Click()Dim x As Integer, y As Integerx、y分别为分别为 A、B产品的数量产品的数量For x0 To 25 For y0 To 20If ThenList1.AddItem“A产品产品”Str(x)“件，件， ” “B产品产品”Str(y)“ 件件”End If Next xEnd Sub请在划线处填入合适代码。请在划线处填入合适代码。(1)划线处应填入划线处应填入_。(2)划线处应填入划线处应填入_。(x*4+y*5)=100 Next y3一个十进制数的二进制表示中，如果数字一个十进制数的二进制表示中，如果数字“1”的个数多于

8、数字的个数多于数字“0”的个数，则称该整数为的个数，则称该整数为A类数。如十进制整数类数。如十进制整数26的二进制的二进制表示为表示为11010,26是一个是一个A类数。下列类数。下列VB程序的功能是：统计前程序的功能是：统计前1000个自然数中个自然数中A类数的个数，并在文本框类数的个数，并在文本框Text1中输出。中输出。Private Sub Command1_Click()Dim i As Integer, n As IntegerDim s As Integer s为为 A类数的个数类数的个数Dim t As Integer t为二进制数中的为二进制数中的“1 ”的个数的个数Dim

9、k As Integer k为二进制数中的为二进制数中的“ 0 ”的个数的个数s0For i1 To ni：t0：k0 Do While n0If n Mod 21 Then tt1 else kkln n2 Loop If Then ss1Next iText1.Text Str(s)End Sub请在划线处填入合适代码。请在划线处填入合适代码。(1)划线处应填入划线处应填入_。(2)划线处应填入划线处应填入_。1000 1000 tk tk 4寻找勾股数：寻找勾股数：“勾股数勾股数”是指满足勾股定理关系的一组数，是指满足勾股定理关系的一组数，也就是直角三角形三边长恰好都取整数的特殊情况。也

10、就是直角三角形三边长恰好都取整数的特殊情况。3、4、5就是一组勾股数就是一组勾股数324252。请编程实现。请编程实现30以内能够组成勾以内能够组成勾股数的整数组及组数。该程序运行界面如下图所示：股数的整数组及组数。该程序运行界面如下图所示：程序代码如下：程序代码如下：Private Sub Command1_Click()Dim a As Integer, b As Integer, c As SingleDim s As Integers 0For a 1 To 30 For b a 1 To 30 c If Then s s 1 List1.AddItem (Str(a) Str(b)

11、Str(c) End If Next b Next a Label1.Caption “共找到共找到” Str(s) “勾股数。勾股数。”End Sub请在划线处填入合适代码。请在划线处填入合适代码。(1)划线处应填入划线处应填入_。(2)划线处应填入划线处应填入_。注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb18文件夹中。文件夹中。Sqr(a2+b2)c=Int(c) And c0 计算计算 j除以除以2的余数的余数 n If余数余数 n是是1 Then ww1 j的值缩小的值缩小1/2 Loop If w3 Then cc1输出输出j输出输出j的二进制编码的二进制编码 En

12、d if Next i程序运行界面如下：程序运行界面如下：相应的相应的VB程序如下：程序如下：Private Sub Command1_Click()Dim c As Integer, i As Integer, j As Integer, w As Integer, n As IntegerDim s As StringList1.Clearc 0For i 1 To 1000j 2 * i 1w 0s “”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 *

13、 i 1) “：” s End If Next iLabel1.Caption “个数：个数： ” Str(c)End SubN=j2j=j2程序加框处代码有错，请改正。程序加框处代码有错，请改正。(1)加框处有错，应改为加框处有错，应改为_。(2)加框处有错，应改为加框处有错，应改为_。注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb21文件夹中。文件夹中。n=j Mod 2 j=j29.求两数最大公约数的求两数最大公约数的VB程序代码如下：程序代码如下：Function gcd(m As Long, n As Long) As Long Dim temp As Long If

14、m n Then temp m: m n: n temp Dim r As Long Do r m Mod n If r 0 Then Exit Do m n n r Loop gcd nEnd FunctionPrivate Sub Command1_Click() Dim m As Long, n As Long Dim r As Long m Val(InputBox(“请输入第请输入第1个数个数”) n Val(InputBox(“请输入第请输入第2个数个数”) r _ MsgBox “两数最大公约数为两数最大公约数为” Str(r)End Sub(1)该程序采用的算法是该程序采用的算法是_。(2)代码中划线处应填入代码中划线处应填入_。注：该示例程序在素材文件下注：该示例程序在素材文件下vb22文件夹中。文件夹中。gcd(m,n)辗转相除法辗转相除法