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

下列程序的功能是在text1中输入的自然数，分解为3个互不相同的质数（三个质数的和等于输入的自然数），并把分解产生的质数按升序顺序显示在左边的列表框中。例如，输入20，那么在列表框中会显示如右图所示结果。其中，上述界面中“分解”按钮的名称是“Command1”，程序中函数f(x)的功能是判断x是否为质数，如果是质数则返回值为true，否则返回false.

请在下列程序代码的基础上按照要求设计该程序, 完善程序中的划线部分。

Dim n As Integer, a1 As Integer, a2 As Integer, a3 As Integer

Function f(x) As Boolean

f = True

      For i = 2 To Sqr(x)

         If x Mod i = 0 Then      ①     

Next i

End Function

Private Sub Command1_Click()

n =      ②       

For a1 = 2 To n

 For a2 = a1 To n

  For a3 = a2 To n

   If     ③      And f(a1) And f(a2) And f(a3) Then

    List1.AddItem (Str(a1) + " " + Str(a2) + " " + Str(a3))

   End If

  Next a3

 Next a2

Next a1

End Sub

其中①处填入；②处填入；③处填入

《孙子算经》中提出“物不知其数”的问题，此数以3除余2，以5除余3，以7除余2。以下程序段是求指定范围内满足该问题条件的自然数及其个数。

k = 0                                 '用来计数

Max = Val(Text1.Text)                   '指定范围

n = 9                            '①

Do While n <= Max                    

  If n Mod 3 = 2 And n Mod 5 = 3 Then  '②

     List1.AddItem Str(n)            

  End If                            

  n = n + 7        ' ③

  k = k + 1         ④

Loop

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

运行程序，在文本框中输入自然数600，结果统计的个数与列表框中输出的个数不相符，如图所示：

请问出现此问题的原因是  (    )

对称字符串的特征是从左到右读和从右往左读是完全一样的。如“abba”是对称的，”abcba”也是对称的。判断字符串是否对称的VB程序段如下：

n = Len(s)  's是判断的字符串

  k = 0: j = n

  For i = 1 To n \ 2

   

  Next i

  If k = 0 Then Label1.Caption = "对称" Else Label1.Caption = "不对称"

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

①j = j - 1

②If c1< >c2 Then k = k + 1

③c1 = Mid(s,i,1) : c2 = Mid(s,j,1)

代码顺序正确的是（  ）

【加试题】某密码的破译步骤如下：

⑴找出文章(以“.”结束)中所有用英文表示的数字(均为小写，数字范围1≤n≤20)，单词与数字对应如下：

⑵将这些数字平方后除以100取余，得到两位数如00，04，21，96。

⑶把这些两位数按升序排成一行，组成一个最小的新数，如果新数开头为0，就去除。

⑷步骤(3)找出的最小数即为密码。

小明按照上述方法，设计了一个解密的VB程序，功能如下：单击“解密”按钮Command1，程序依次将文本框Text1中以空格分隔的每个英文单词取出，若单词属于数字单词，则按解密步骤进行处理，最后在文本框Text2中输出解密结果。

程序运行效果如图所示，请回答下列问题：

下列VB程序功能可以找出1000以内的完全数，并在标签中一一列出来。

Private Sub Command1_Click()

 Dim i As Integer, m As Integer, n As Integer

    Label1.Caption = "1000以内的完全数如下："

    For i = 1 To 1000

        n = 0

        For m = 1 To i \ 2

            If i Mod m = 0 Then n = n + m

        Next

        If n = i Then Label2.Caption = Label2.Caption & "" & Str(i)

    Next

End Sub

该过程采用的算法是（    ）

现有n根棍子，第i根棍子的长度为a_i 。想要从中选出三根棍子组成周长尽可能长的三角形，输出最大的周长；若无法组成三角形，则输出0。如当n=5，a={2，3，4，5，10}时，输出12，即选择了3、4、5。当n=4，a={4，5，10，20}时，无法组成三角形，输出0。加框处代码有误，请改正。

Dim a(1 To 1000) As Integer

Dim n As Integer

Private Sub Form_Load()

‘确定n的值和数组a的各个元素值，即每根棍子的长度值，代码略

End Sub

Function max(x As Integer, y As Integer) As Integer

If x > y Then

    max=x

  Else

    max=y

  End If

End Function

Private Sub Command1_Click()

  Dim i As Integer , j As Integer , k As Integer

  Dim ans As Integer , c As Integer , longest As Integer , rest As Integer

ans=0

  ‘让 i<j<k,保证棍子不会重复选中

  For i=1 To n

  For j=i+1 To n

   For k=j+1 To n

    c=a(i)+a(j)+a(k)

    longest=     ‘①

    rest=c-longest    ‘rest 保存最短的两条边的和

    If  Then    ‘②

     ans=max(ans , c)

End If

   Next k

Next j

  Next i

Print ans

End Sub

① ② 

如果一个4位数恰好等于它的各位数字的4次方和，则这个数被称为“玫瑰花”数。例如1634就是一个玫瑰花数：1634＝14＋64＋34＋44。如果要求出所有的玫瑰花数，下列算法合适的是( )

算法设计与程序实现

换钱问题：

要将一张100元的钞票，换成等值的5元、2元、1元一张的钞票共50张。其中一种换法如下：

5元：3张

2元：38张

1元：9张

求出所有的换钱方案。

【算法设计】

x表示5元的张数：1≦x≦20；

y表示2元的张数：1≦y≦50；

z表示1元的张数：1≦z≦100。

【参考程序】

Dim x AsInteger

Dim y AsInteger

Dim z As Integer

For x=1 To20

    For y=1To 50

        Forz=1 To 100

           If           Then

               Print x；y；z       ‘x y z 之间以分号分隔

           End If

        Nextz

   Next y

Next x

根据上述回答下列问题：

求不大于n的五位正整数中，满足高两位与低两位相同，且能被3除余2的所有数之和。

有如下Python程序段：

s=0

for i in range(1, 101)：

   if i%2== 0：

        s+=i

该程序段被执行后，变量s中存储的是1~100之间的(    )

密码的合法性。某网络服务平台，要求新注册用户的密码必须以字母开头，并且含有字母(区分大小写)、数字和下划线，密码字符的长度为6~18个字符。判断用户的密码是否合法的某Python程序如下，请在程序划线处填入合适的代码，完善程序。

n1 =False #判断数字

n2=False #判断下划线

flag=False #判断首字符和长度是否满足要求

password=input('请输入密码:\n')

n=     ①      

ch=password[0]

if 19>n>5 and (z'>=ch>='a' or 'Z>= =ch>='A')：

    flag=True

if flag：

    for i in range(1, n)：

        ch=password[i]

        if '9'>=ch>='0'：

            n1=      ②     

      elif ch= '_'：

          n2=True

if      ③      

    print('结果：', '合法')

else：

    print('结果：', '不合法')
①  ②  ③

古希腊著名科学家毕达哥拉斯把1、3、6、10、15、21、28……称为三角形数。这些三角形数序列有一定的规律，后一个数与前一个数的差刚好构成一个等差数列2、3、4、5、6、7、……，所以，第2位的“3”等于序列的第1位数“1”加上等差数“2”，第3位的6等于序列的第2位数“3”加上等差“3”……，第n位数m等于序列的第n-1位数加上等差数n。小金利用这个规律编写了一个判断三角形数的VB程序，在文本框Text1中输入一个大于1的正整数，单击“判断”按钮Command1，在标签Label1中显示判断结果。程序设计界面如图所示。

用VB编程解决一个问题：求所有五位数中满足能被17整除且十位数字为5的数之和。

火柴棒等式。用火柴棒可以摆出0-9的数字，摆放规则如下图所示：

有一种火柴棒游戏，将火柴棒摆成形如“A+B=C”的火柴棒等式。用n根火柴棒摆放数学等式的规则约定如下：

⑴A、B都是不大于1000的正整数，若数值非零，则最高位不能是0；

⑵摆放“+”与“=”各使用两根火柴棒；

⑶A+B=C 与B+A=C视为相同的等式；

⑷n根火柴棒必须全部用上。

小明依据上述规则使用VB编写程序，研究“使用n根火柴棒，可以摆放出哪些不同的等式”，代码如下所示。请回答下列问题。

Dim sz(0 To 9) As Integer     ‘数组元素sz(i)用于存储数字i所使用的火柴棒的数量

Private Sub Form_Load()

    sz(0) = 6 : sz(1) = 2 : sz(2) = 5 : sz(3) = 5 : sz(4) = 4

    sz(5) = 5 : sz(6) = 6 : sz(7) = 3 : sz(8) = 7 : sz(9) = 6

End Sub

‘自定义函数hcs用于求解摆放数字x需要使用的火柴棒数量

Function hcs(ByVal x As Integer) As Integer

    Dim s As Integer, k as integer

    s = 0

    Do While     ①    

        k = x Mod 10

        s=s+sz(k)

        x = x \ 10

    Loop

    hcs = s + sz(x)

End Function

Private Sub Command1_Click()

    Dim n As Integer

    Dim a As Integer, b As Integer, c As Integer

    n = Val(Text1.Text)

    ans = 0

    List1.Clear

    For a = 0 To 999

        For b =    ②     To 999

            c = a + b

            If     ③    Then

                List1.AddItem (Str(a) + "+" + Str(b) + "=" + Str(c))

                ans = ans + 1

            End If

        Next b

    Next a

    List1.AddItem ("共有" + Str(ans) + "种等式")

End Sub

“一笔画游戏”是指图上的所有边有且仅经过一次刚好将整个图描完。一般图由点和边组成，一条边连接两个点，一个点可以连接多条边。若某点连接的边数是奇数，则被称为奇点，反之称为偶点。如图a图中A点连接的边有3条，A点就是奇点，B点连接的边为2条，B点就是偶点。如果图中存在0个奇点或2个奇点，则能被一笔画成，否则就不能。如图a图中奇点数为2个，可以一笔画成；如b图中奇点数为4个，不可以一笔画成。

现有VB程序用于判断某图能否一笔画成，若能，则通过穷举边的顺序来找到一种合法的路径。如c图有三条边，第1条由①②相连，第2条由④③相连，第3条由③②相连，若边的顺序231就是其中一种合法的边的顺序，代表先描第2条边，再描第3边，最后描第1条边，对应的路径④→③→②→①。在程序运行过程中，在文本框Text1中输入点的个数n，表示图中有n个点编号为1～n。在文本框Text2中输入若干点的编号，每两个点代表一条边(保证输入为偶数个点)，以“，”开头，点击“一笔画”按钮Command1后，在Label3中输出结果，在若能一笔画成，则输出一条路径，否则，提示“无法一笔画！”。程序界面如c图：

c图

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

for i in range(1):

    if     :

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

下列选择正确的是（   ）。

魔法世界有一个毕达哥拉斯学派，他们将一个数如果恰好等于它的因子之和，则称它为“完美数”。并且认为完美数具有神奇的魔力。例如6的因子为1、2、3，而6=1+2+3，因此6是“完美数”。创始人毕达哥拉斯说：“6象征着完满的婚姻以及健康和美丽，因为它的部分是完整的，并且其和等于自身。”

小明同学想利用所学的Python编程，找出1000之内(包括1000)的所有完美数。程序代码如下：

def f(x):

  s=0

  for i in range(1,//2 + I):

  if x%i= 0:

        ①  

  retum S

for i in range(2, 100):

  t= f(i)

  if    ②  

    print(i, "是完美数", sep="")

[二进制枚举法]小明在玩一个翻转棋盘的游戏，其中棋子只有黑白两面，界面如图a所示：游戏规则是挑选几个棋子，对于每个被挑选的棋子，将该棋子和它上下左右4个相邻棋子一起翻转，若某个方向无棋子，则不作处理，最后使得棋盘纯色(纯白或纯黑)。现需要编写程序找出所选棋子最少的方案并输出所选棋子的个数，若无答案则输出“无法翻转为纯色”

(注：如图a所示，则需翻转第二行第二列、第四行第二列两个棋子便可使得棋盘纯黑)

一开始小明不知从何人手，但很快他发现了突破点。他先将棋盘状态利用二进制进行编码并存储在数组中，编码规则为0表示白，1表示黑，顺序为从左至右，从上至下，则第10题图a中的初始状态可以表示为数列1011000111110001。

随后，他将被选中的棋子的位置也进行二进制编码，0表示不选中，1表示被选中，则可以用一个16位二进制编码表示。例如，二进制编码0000010000000100表示选中了第2行第2列、第4行第2列这两个棋子，随后将编码转化为十进制数，即2^10+2^2= 1028；于是，整张棋盘的所有选棋子方案为000000000000000 ~ 11111111111111，也就是十进制下的0~65535，利用枚举算法即可找到最优方案。

程序界面如图b所示，VB代码如下，请回答下列问题。

生活中大家经常玩“算24点”游戏，规则是给定任意0-9之间的四个整数，玩者利用计算操作符“+”、“-”、“*”、“/”及括号填入四个数字之间，使得运算结果为24，先算出者为赢家。计算24点最合适的算法是（     ）。

一辆车发生交通事故后逃逸，王警官从现场四位目击证人处获得了以下线索。甲说：“车牌照以“苏FS”开头，后跟着四位数，乙说四位数字的前两位数字相同；丙最后两位数字也相同，但与前两位不同，丁是数学家，他说：四位数字刚好是一个整数的平方。请你根据以上线索协助王警官尽快锁定肇事车辆。