枚举算法及程序实现 知识点题库

【加试题】求孪生素数。孪生素数是指两个相邻奇数且都是素数，由于它们是最近的素数，就像孪生兄弟一样。下列Visual Basic程序用于查找100以内的所有孪生素数，其中函数f用于判断一个数是否是素数，程序运行界面如图1所示，Command1鼠标单击事件过程的流程图如图2所示。

 图1
   图2

 程序代码如下：

Private Sub Command1_Click()

  Dim i As Integer

  List1.Clear            '清除列表框内容

For i = 3 To 97 ___①___     If f(i) And     ②     Then       List1.AddItem Str(i) + " 和 " + Str(i + 2)     End If   Next i

End Sub

Private Function f(x As Integer) As Boolean  '自定义函数f,返回值为逻辑型

  Dim j As Integer

  f = True

  For j = 2 To Int(Sqr(x))

    If x Mod j = 0 Then

      f =     ③      '函数返回值

      Exit For           '跳出For循环

    End If

  Next j

End Function

下面程序的功能是：统计输入信息有多少个英文大写字母、小写字母、数字字符。程序运行时，在文本框Text1中输入信息，单击“确定”按钮后，分别在文本框Text2、Text3、Text4中显示大写字母、小写字母和数字字符的个数。程序运行效果如图所示。

Private Sub Command1_Click()

Dim getStr As String

Dim a As String

Dim i As Integer，s As Integer

Dim q As Integer，l As Integer

s=0：q=0：l=0

getStr=Text1.Text

Text2.Text = Str（s）

Text3.Text = Str（q）

Text4.Text = Str（l）

End Sub

求孪生素数。孪生素数是指两个相邻奇数且都是素数，由于它们是最近的素数，就像孪生兄弟一样。下列Visual Basic程序用于查找100以内的所有孪生素数，其中函数f用于判断一个数是否是素数，程序运行界面如图(图1)所示，Command1鼠标单击事件过程的流程图如图(图2)所示。

程序代码如下：

Private Sub Command1_Click()

  Dim i As Integer

  List1.Clear  '清除列表框内容

For i = 3 To 97 ___①___     If f(i) And f(i+2)=true Then       List1.AddItem Str(i) + " 和 " + Str(i + 2)     End If   Next i

End Sub

Private Function f(x As Integer) As Boolean  '判断是否为素数，若是返回true,若不是则返回false

………

End Function

【加试题】《孙子算经》中提出“物不知其数”的问题，此数以3除余2，以5除余3，以7除余2。下列VB程序用来求指定范围内满足该条件的自然数及其个数。程序界面如图所示，VB程序段如下：Private Sub Command1_Click(   )

  k = 0                 '用来计数

  Max = 600             '指定范围600以内

  n = 9                                  

  Do While n <= Max

  Loop

  Label1.Caption = Str(Max) & "范围内满足问题的数有" & Str(k) & "个"

End Sub

方框中的代码由以下五部分组成：

① n=n+7

② k = k + 1

③ List1.AddItem Str(n)

④ End If

⑤ If n Mod 3 = 2 And n Mod 5 = 3 Then

代码顺序正确的选项是（  ）

个位数字是6，且能被3整除的3位数共有多少个？下面程序用于解决这一问题，在划线处填入合适的语句或表达式，设共有n个这样的数，Visual Basic程序如下：

Sub Command1_Click()

Dim i As Integer, n As Integer

m=106

n =

Do While m <= 996

    If Then n = n + 1

    m=

Loop

Text1.Text = Str(n)

End Sub

某校举办竞赛，共有15个试题，每做对一题得8分，做错一题倒扣4分，没有未做的题目，小明共得了8分，则他做对了几题。用VB程序来解决这个问题，单击按钮Command1，在文本框Text1中输出答对的题数，在文本框Text2中输出做错的题数，程序代码如下：

Private Sub Command1_Click()

i＝1

____①____

Do While____②____

____③____

j＝j－1 ′④

Loop

Text1.Text＝Str(i)

Text2.Text＝Str(j)

End Sub

一辆卡车运矿石，晴天每天运20次，雨天每天最多运12次，他一共运了8天，共112次，则晴天和雨天各有几天。用VB程序来解决这个问题，单击按钮Command1，在文本框Text1中输出晴天的天数，在文本框Text2中输出雨天的天数，程序代码如下：

Private Sub Command1_Click()

 i＝1

 j＝7

 Do While ____①____

i＝____②____

j＝____③____

 Loop

 Text1.Text＝Str(i)

 Text2.Text＝Str(j)

End Sub

则下列说法正确的是（  ）

火柴游戏：有n根火柴，第1次取1根，第2次取2根，第i次取i根，当剩余火柴数为0时，不用添加火柴（即k=0），游戏结束。如果剩余火柴数不为0，但不够下一次取，此时添加k（k≥1）根火柴，在剩余火柴中再从1根开始取，直到能取完为止，求k的最小值。

例如：n=3时，第1次取1根，第2次取2根，此时正好取完，无须添加火柴，k=0；

例如：n=8时，第1次取1根，第2次取2根，第3次取3根，第4次要取4根，但剩余2根不够取。则加上1根，剩余3根，再从1根开始取，即第4次取1根，第5次取2根，剩余火柴为0，游戏结束，得k=1。

又如：n=4时，第1次取1根，第2次取2根，第3次不够取，若加上1根，剩余2根，再从1根开始取，第3次取1根，剩余1根不够第4次取，再加1根，又是剩余2根，显然加1根永远不可能取完。所以改用每次加2根，第1次取1根，第2次取2根，第3次不够取，添加2根，第3次取1根，第4次取2根，恰好能取完，得k=2。

编写一个VB程序可实现上述功能：在文本框Text1中输入火柴数量，单击“计算”按钮，在文本框Text2中显示最少添加数量，程序运行界面如下图所示：

实现上述功能的程序代码如下：

Private Sub ok_Click()

Dim a(1 To 100) As Boolean, n As Integer, k As Integer, i As Integer

n = Val(Text1.Text)

For i = 1 To 100

    a(i) = False

Next i

a(n) = True

Do While n <> 0

    i = 1

    Do While i <= n

             ①      

        i = i + 1

    Loop

    If n = 0 Then

        Text2.Text = Str(k)

    Else

        If k = 0 Then k = 1

        n = n + k

        If       ②      Then

            k = k + 1

            n = Val(Text1.Text)

        Else

            a(n) = True

        End If

    End If

Loop

End Sub

以下程序用于统计自然数1到n之间出现多少个x（0<=x<=9），空缺处应填入的代码是（    ）

n = Val(Text1.Text)

x = Val(Text2.Text)

k = 0

For i = 1 To n

        ①       

   Do While temp <> 0

      y= temp Mod 10

      If      ②        Then k = k + 1

      temp = temp \ 10

   Loop

Next

Label1.Caption = Str(k)

有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。

小明编写了一个VB程序，可实现如下功能：在100至999之间的自然数中，找出能被3整除，且至少有一位数字为5的所有整数，并统计个数。程序运行界面如图a所示。

设计算法，求同时满足以下条件的所有四位正整数之合s。①不大于n(n的值由键盘输入)，②能被9整除，③十位数是2。算法流程图如下所示：

穷举法的适用范围是（   ）

学校开展“奇妙的数字”研究性学习活动。张轩小组4人决定把课题定为《探秘水仙花数》。

在n个(1≤n≤15)一连串的方格内填写字母A或B，但相邻两格内不能都填B，求所有可能的填写方案数。例如当n＝3，可能的方案有AAA、AAB、ABA、BAA、BAB等5种。

丽华设计如下算法：考虑到方案中只包含了A与B两个字母，可以用二进制的0和1来代替（0表示A，1表示B）。当全部是0时最小，此数0；当全部是1时此数最大。枚举0到最大数的每一种情况，逐一判断是否包含B相连(二进制数1相连)情况，符合条件的0、1转为A、B后输出。

根据以上算法思想，丽华使用VB程序编写了一个程序来解决这个问题。在文本框Text1中输入n的值，点击“寻找方案”按钮Command1后，在列表框List1中输出所有的方案，在标签Label3中显示方案总数。

小明的支付宝帐号密码忘记了，但他还零星记得有关于密码的一些信息：

①密码是八位数字，前两位为19

②最后两位数字是91

③能被77和133整除

程序界面如图所示，单击“找回密码”按钮（Command1）后，可能的密码显示在列表框List1中。

解决此问题的相应的程序如下：

Private Sub Command1_Click()

    Dim i As Long, s As Long

    For i = 0 To 9999

        s =  ①                  's表示该八位数密码

        If    ②   Then            '符合密码的条件，s能被77和133整除

            List1.AddItem Str(s)

        End If

    Next i

End Sub

班长为合唱比赛准备礼物，预算总金额有n元钱，预计购买p件礼物，每件礼物对应有商品编号、单价、数量和喜爱度。礼物不可分割，每人至多一份，班长希望每位获得礼物的同学都尽可能喜爱获得的礼物。

按上述要求，编写VB程序，功能如下：在文本框Text1中输入预计礼物数，在文本框 Text2中输入总金额，单击“计算”按钮Command1，在列表框List1中显示各类商品的编号、单价、数量、喜爱度，以及最佳购买方案、剩余金额和总喜爱度，若有多种最佳方案，则输出第一个找到的方案信息，如图a所示。

图a

“枚举算法”又称为“穷举法”，其基本思想是：一一列举出所有可能的解，并验证每个可能的解是否是真正的解，若是，就采纳，否则，就抛弃。

小明利用枚举算法解决“百元买百鸡”问题。用100元钱买100只鸡，公鸡，母鸡，小鸡都要有。公鸡5元1只，母鸡3元1只，小鸡1元3只。请问公鸡，母鸡，小鸡各应该买多少只？

假设公鸡有X只，母鸡有Y只，小鸡有Z只。

以下Python程序段实现了“百元买百鸡”的功能，请补全横线处代码。

c = 0

for x in  :

 for y in range(1,33):

  z = 100-x-y

  if  :

    print("公鸡:",x,"母鸡:",y,"小鸡:",z)

print("共有买法",c,"种")

用枚举法在两个□内填入相同的数字使“□3×6528＝3□×8256”表达式成立。

for i in range(1):

  if     :

    print(i，“3×6528＝3”，i，“×8256”，sep＝”）

下列选择正确的是（   ）。

假定母鸡每只4元，公鸡每只3元，小鸡每只0.25元，每种鸡都要买，现有100元，要买100只鸡，问有多少种方案。要求解这个问题，最适合的算法是（    ）。