3.3 简单算法及其程序实现 知识点题库

小刚的支付宝账户密码忘记了，但他急用支付宝进行转账，请你帮他尽可能找回密码。他只记得自己密码的一些零星信息：

①密码是六位数字，前面两位为59；

②最后两位数字相同；

③能被12和38整除。

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

【根据宁波效实中学2012学年第一学期高一信息技术期末试卷改编】将一个十进制正整数x转换成十六进制数的方法和转换成二进制类似，反复除16取余法，它的算法如下

    第一步：x被除16取余数r1，r1是所求的十六进制数的一个数（第一次就是个位数）；

    第二步：r1转换成十六进制数的一个基数并转换成字符，追加到十六进制数S的左边;

    第三步：求出x被除16的商x1;

    第四步：对x1重复（1）、（2）、（3）过程，直至商为0；

    第五步：最后的S即为所求的十六进制数；

下列Visual Basic程序的功能是将一个十进制正整数x转换成十六进制数。界面如图所示，在文本框Text1中输入一个十进制数制，单击“十进制转十六进制按钮”（Command1）后，在文本框Text2中输出转换的结果。 相应的Visual Basic程序如下：

Private Sub Command1_Click()

  Dim s As String, r As Integer

  dec = val(Text1.Text)                  ’dec得到一个十进制整数，例如：255；

  base = 16                               ’base表示16

     s = ""                                ’s变量存放要转换到的十六进制整数；

     Do While dec <> 0

          r =        ①   

          If r >= 10 Then                     ’如果base>10进制，r可能>10；

             s = Chr(65 + (r - 10)) + s   ’Chr (65)="A", 16进制数A对应10；

          Else                            ’Chr(66)="B", 16进制数B对应11；
             s = Str(r) + s      ‘余数r<10时，十进制数和十六进制基数相同；
          End If                   ‘Chr (65 +( r - 10))或str(r)在s左边，实现了反次序输出；
          dec =     ②              
    Loop
   Text2.Text = s
End Sub

编写VB程序，实现如下功能：在文本框Text1中输入十进制整数，文本框Text2中输入待转换进制（范围2~16），单击“转换”按钮Command1，在列表框List1中输出该整数对应的进制结果，运行效果如图1所示。

VB编写“字符串生成”程序，实现如下功能：在文本框Text1中输入多个正整数，数字间以“，”为分割符，单击“生成”按钮Command1，程序以这些整数为位置信息，依次从文本框Text2中(字典内容)提取字符并连接成字符串，最后将生成的字符串显示在标签Label1中。程序运行界面如图所示。

如图1所示，这是一个城市街道简图，小明从 A 点出发，到达 B 点，如果在每一个路口只能向右或向上走（0 表示向上走，1 表示向右走），问小明有多少条行走路线，并请输出每条路线。程序界面如图2所示。

算法分析：从A点到B点共有7个路口，即可以有一个7位二进制数表示所走路线。观察以上路线，枚举所有满足路线特征的7位二进制数，再去掉不满足的二进制数即可。

有如下VB程序段:

Dim a(1 to 5) as Integer, i as Integer, c as Integer

a(1) = 2 : a(2) = 1 : a(3) = 3 : a(4) = 4 : a(5) = 5

c = 0

For I = 3 to 5

If a(i - 2) + a(i - 1) = a(i) Then c = c + 1

Next i

Text1.Text = Str(c)

该程序运行后，文本框text1中显示的内容是（  ）

下列程序所计算的数学式子是（  ）

PRIVATE SUB FORM__CLICK( ）

S=0

FOR A= 1 TO 5

    S=S+（10^A-1）/3

NEXT A

PRINT S

END SUB

【加试题】格雷码(Gray code)，又叫循环二进制码。一般的，格雷码可以解码成普通二 进制码。某格雷码 G1 G2 G3 …Gn-1 Gn，解码成普通二进制B1 B2 B3 …Bn-1 Bn的方法如下：

⑴把格雷码第1位G1作为解码后二进制码的第1位B1，即：B1= G1；

⑵从第2位起，将格雷码每一位与左边相邻一位的解码值作异或运算，结果作为该位格 雷码的解码值，即Bi=Gi⊕Bi-1。例如，某格雷码1101110，可解码成普通二进制码 1001011， 如图所示。

异或运算（⊕）规则：如果 a、b 两个值不相同，则 a⊕b 结果为 1；如果 a、b 两个值 相同，则 a⊕b 结果为 0，即:0 ⊕ 0 = 0，1 ⊕ 0 = 1，0 ⊕ 1 = 1，1 ⊕ 1 = 0。

小明编写了一个格雷码解码的VB程序，功能如下：在文本框Text1中输入格雷码,单击 “解码”按钮 Command1，程序对输入的格雷码进行转换处理，转换后的二进制码用十六进 制表示并显示在文本框 Text2 中。程序运行界面如图所示。

有一个n行m列网格状临时停车场，如图a所示：在网格中随机分布若干个石头，网格中“□”表示空位，“●”表示石头。停放一辆车需要长为clen个空位、宽1个空位的空间，且车只能南北停放。编写程序，实现统计该车共有多少种停放方法。

程序实现过程：生成规模为n×m的网格，在网格边界添加一圈交通锥“▲”，并将“□” “●”、“▲”按行依次存入数组a中，在文本框Tex3中输入停放该车最小长度clen值，在文本框Text4中输出共有多少种停放方法。程序运行界面如图b所示，实现上述功能的VB代码如下：

Dim a(1 To 200) As String

Dim n as Integer, m As Integer

Private Sub Command1 Click ()

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

Dim s As string

n= Val(Text1. Text)+2

m=Val(Text2 Text)+2

List1. Clear

For i=1 To n*m

    If i<=m0ri>m*(n-1) or  ①  Then   ‘在矩阵周围加上一圈边界

        a(i)=“▲”

    Else

        k= Int(Rnd 2)

        If k=1 Then a(i)=“□” Else a(i)=“●”

    End If

Next i

‘在列表框List1中显示网格，代码略

End sub

Private Sub Command2 Click ()

Dim i As Integer, j As Integer, c As Integer, x As Integer, y As Integer

Dim cnt As Integer, clen As Integer

Dim flag As boolean

clen= Val(Text3. Text)

y=1

Do While y <=m

    For x =1 To n

        If a((x-1)*m+ y)=“□” Then

            c=c+1

        Else

            If c ≥=clen Then

                cnt=②

            End if

             ③

        End If

    Next x

    y=y+1

Loop

Text4 Text Str(cnt)

End Sub

请回答下列问题

奇偶校验是一种校验数据传输正确性的方法。其中奇校验方法：统计二进制数据的数位中“1”的个数，若个数为奇数，则校验位值为0，否则校验位值为1。小李编写了一个计算奇校验位值的VB程序，功能如下：在文本框Textl中输入1~255间的十进制待校验数，单击“计算”按钮Commandl后，在文本框Text2中显示该数对应的二进制值，并在标签Label3中显示该数的校验位值。程序运行界面如图所示。

已知a、b、c分别为三角形的三条边长，利用海伦公式求该三角形面积

p=(a+b+c)/2

S=√[p(p-a)(p-b)(p-c)]

编程实现：输入边长a,b,c,如果能构成三角形，输出面积，否则输出“No Answer!”

界面如下:

[参考程序]

Dim a, b, c, p, s As Single

a = Val(Text1.Text)

b = Val(Text2.Text)

c = Val(Text3.Text)

If                  Then

p = (a + b + c) / 2

s = Sqr(p * (p - a) * (p - b) * (p - c))

Text4.Text = Format(s, "0.00")

Else

Text4.Text = "no answer"

End If

根据上述回答下列问题

某市对一户一表居民实行阶梯电价，电费计算方式如下：月用电量在1-50千瓦时部分不调价；月用电量在51-200千瓦时部分，电价每千瓦时上调0.03元；月用电量超过200千瓦时部分，电价每千瓦时上调0.10元。

若假定某用户一个月的用电量为x千瓦时，当前单价为p元/千瓦时，则计算标准如下：当x≤50时，电费为p×x元；当50<x≤200时，电费为p×x+(x-50)×0.03元；当x>200时，电费为p×x+4.5+(x-200)×0.1元。

程序设计界面如下图所示，程序的功能是：在文本框Text1中输入用电量x（单位：千瓦时），在文本框Text2中输入电量p（单位：元），单击“计算”按钮（Command1）后，在标签Label4中输出计算结果。

编写一个摄氏温度转换成华氏温度的Python程序，实现功能：输入两个摄氏温度数据(整数)，输出包含两列数据，第1列为两数之间的摄氏温度值(间隔1度、升序)，第2列为对应的华氏温度值。其中，摄氏温度x转换成华氏温度y的计算公式为：。

输入、输出格式如下：

输入第1个数：

15

输入第2个数：

0

摄氏温度    华氏温度

10          50.0

11          51.8

12          53.6

13          55.4

14          57.2

15          59.0

实现上述功能的某Python程序如下，在方框处补充一段程序代码，完善程序，实现程序功能。

t1=int(input(输入第1个整数：\n'))

t2=int(input(输入第2个整数：\n"))

if t1>t2：

      t1，t2=t2，t1    

print(摄氏温度+' '+ 华氏温度)

i=t1

while i<=t2：

编写VB程序，实现如下功能：在文本框Text1中输入一个大于1000的正整数，单击按钮Command1后会去除其中3个数字，保证余下的数字在不改变顺序的情况下其数值最大，然后在文本框Text2中输出该数。

Private Sub Command1_Click()

    Dim s As string

    Dim n As Integer, w As Integer

    s=Text1.Text

    For i=1 To 3

        n=Len(s):w=1

        For j=2 To n

            If ________ Then w=j Else Exit For

        Next j

        s=Mid(s,1,w-1)+Mid(s, w+l, n-w)

    Next i

    Text2.Text=s

End Sub

画线处的正确代码为（    ）

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

小明利用枚举算法解决“百元买百鸡”问题。用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,"种")

（多选）用计算机解决以下问题，与穷举法相比更适合用解析法来解决的有（    ）。

魔法世界有一个毕达哥拉斯学派，他们将一个数如果恰好等于它的因子之和，则称它为“完美数”。并且认为完美数具有神奇的魔力。例如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="")

[矩阵上的枚举]大家有接触过地雷游戏吗？如图所示是一个“挖地雷”游戏的界面，9X9个格子里都有一个数字，红旗代表地雷可以用“★”表示，图中共有10个地雷，“一一”表示空白格，边上的“▲”表示边框。

定义规则：你需要标记出所有空白格子周边相邻的格子上有多少地雷(在正方向和斜45度方向挨着的格子均可视为相邻)，并将数量标记在空白格中，如下图所示。

实现上述功能的VB程序如下，请在划线处填入合适的代码。

Dim n As Integer,m As Integer      'n 存储地雷区域大小,m存储地雷数目

Dim a(1 To 100 * 100) As String

Dim b(1 To 100 * 100) As Integer

Private Sub Command1_Click()       '按要求生成数组a中的数据并显示

    Randomize

    List1. Clear

    n=9 : m=10

    Dim s As String, pos As Integer, i As Integer

    s=" " : n=n+2

    For i=1 To n * n

        If isinside(i) Then a(i)="— —"

        Else a(i)="▲"

    Next i

    For i=1 To m

        pos=Int(Rnd * n * n)+1

        Do While a(pos)="★" Or

            pos= Int(Rnd * n *n)+1

        Loop

            a(pos)="★"

    Next i

    For i=1 To n* n

        s= s+" "+a(i)

        If i Mod n=0 Then

            List1. AddItem s

            s=" "

        End If

    Next i

End Sub

Private Sub Command2_Click()

    Dim i As Integer, j As Integer, row As Integer

    Dim col As Integer, start As Integer, temp As String

    For i=1 To n* n

        If a(i)="★" Then

        row=(i-1) \ n+1 : col=(i-1) Mod n+1

            For j=1 To 3

                start=

                If a(start+col- 1)="— —" Then b

                (start+ col- 1)= b(start+col- 1)+1

               If a(start+col)="— —" Then

                    b(start+ col)= b(start+col)+1

                If a(start+col+1)= "— —" Then b

                (start+col+ 1)= b(start+ col+1)+1

            Next j

        End If

    Next i

    List2. Clear

    For i=1 To n

        temp=" "

        For j=1 To n

            If a((i-1) * n+j)="— —" Then

                temp=temp+" "+ Str(b((i-1) * n+j))

            Else

                temp= temp+" "+a((i- 1)*n+j)

            End If

        Next j

        List2. AddItem temp

    Next i

End Sub

Function isinside(x As Integer) As Boolean

    isinside= x>n And And x

    Modn<；>1AndxMod<> 0

End Function

水仙花数是指一个三位数，它的每个位上数字的3次方之和等于它本身，现要求出所有三位的水山花数，下列算法最合适的是（    ）

以下问题中最适合用解析算法解决的问题是（    ）