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

【加试题】有30个人，其中有男人、女人和小孩，他们在一家商场花去500元。已知，每个男人花20元，每个女人花30元，每个小孩子花10元。问男人、女人、小孩各为多少人？解决上述问题的VB程序如下，单击按钮Command1，列表框List1中输出结果。

Privvate Sub Command1Click( )

Dim man As Integer,woman As Integer,child As Intger,s As Integer

For woman = 1 To 15

Child = 30 – man – woman

S = 20 * man + 30 * woman + 10 * child

If Then

List1.AddItem Str(man) + Str(woman) + Str(child)

End If

Next woman

Next man

End Sub

【加试题】在计算机中用一个字节（8位）来存储一个字符的ASCII码，其中低7位二进制数对应字符的编码，每个字节的最高位一般保持为“0”，在数据传输时该位可用作奇偶校验位。传输时ASCII代码转换成传输码的方法是：若7位ASCII码中有偶数个1，则最高位置为1；有奇数个1，则最高位置为0。例如字母“A”的ASCII码十进制表示为65，二进制表示为1000001。“A”的传输码则为“11000001”，本程序的功能就是把ASCII码转换成这种传输码，运行效果如第17题图所示。

（1）根据上述ASCII代码转换成传输码的方法，字符“D”的传输码为。
（2）实现上述功能的VB程序如下，请在划线处填入合适代码。
Private Sub Command1_Click()
    Dim i As Integer, S As String
    Dim str As String, ch As String
    str = Text1.Text
    List1.Clear
    For i = 1 To Len(str)
        ch =   ①
        S = convert(ch)
        List1.AddItem ch & "==>" & S
    Next i
End Sub

Private Function convert(ch As String) As String
    Dim m As Integer, k As Integer, n As Integer, i As Integer
    convert = ""
    n = Asc(ch)
    Do While n > 0
②
        convert = m & convert
        If m = 1 Then
            k = k + 1
        End If
        n = n \ 2
    Loop
    For i = 1 To 7 - Len(convert) '将字符的二进制代码补足7位
        convert = "0" & convert
    Next i
    If k Mod 2 = 0 Then
        convert =   ③
    Else
        convert = "0" & convert
    End If
End Function
程序中划线处①的代码应为。
程序中划线处②的代码应为。
程序中划线处③的代码应为。

【加试题】火柴棍可以拼成数字0～9，拼法如图a所示。

输入火柴棍的数量n(n≤24)，计算可以拼出多少个“A+B=C”的等式?

要求：

①加号与等号各自需要两根火柴棍。

②A，B，C为非负的整数，且该数非零时，最高位不能是0。

③如果A≠B，则A+B=C与B+A=C视为不同的等式。

④n根火柴棍必须全部用上。

小明发现，数字1用的火柴棍最少，24根火柴棍全部用上的话，能拼出最大的整数A或B不超1111，C不超过2222，他编写了一个VB程序，在文本框Text1中输入火柴棍的数量，单击“统计”按钮Command1，在文本框Text2中输出“A+B=C”的方案数，程序界面如图b所示。

实现上述功能的VB程序如下，请回答下列问题：

（1）请在画线处填入合适的代码。
Private Sub Command1_Click()

Dim a(0 T0 2 222)As Integer        ‘存储每个整数需用的火柴棍数

Dim n As Integer，ans As Integer

Dim i As Integer，j As Integer

n=Val(Text1．Text)

For i=0 To 2 222

   a(i)=0

Next i

‘得到0～9中每个数字需用的火柴棍数

a(0)=6：a(1)=2：a(2)=5：a(3)=5：a(4)=4

a(5)=5：a(6)=6：a(7)=3：a(8)=7：a(9)=6

n=    ①       ‘去掉等号与加号后，剩余的火柴棍数量

For i=10 To 222 ‘计算出10～n中每个数字需用的火柴棍数

    a(i)=a(    ②   )+a(i Mod 10)

Next i

ans=0

‘枚举0～n中任意两个数，判断是否符合A+B=C的火柴棍数量

For i=0 To 1 111

    For j=0 To 1 111

    If a(i)+a(j)+a(    ③    )=n Then

     ans=ans+1

    End If

    Next j

Next i

Text2．Text=Str(ans)

End Sub

① ② ③
（2）输入的火柴棍的数量为14时，方案数为。

编写“字母出现频率测试”程序，实现如下功能：在文本框Text1中输入英文句子，单击“统计”按钮，在列表框List1中显示小写字母出现的次数，同时显示字母出现频率最高的次数。程序运行界面如图1所示。

图1

（1）在设计程序界面时，使应使用图2所示“控件工具箱”中的（填写相应编号）添加“统计”按钮。
图2
（2）实现“统计”功能的VB程序如下，请在划线处填入合适的代码。
Private Sub CmdTJ_Click()

Dim count(25) As Integer

Dim ch, ch2 As String

Dim m As Integer

ch = Text1.Text

For k = 1 To Len(ch)

      ①

   n = Asc（ch2）-Asc(“a”)

   If n >= 0 And n <= 25 Then

     count(n) = count(n) + 1

     List1.AddItem "字母" + ch2 + "出现" + Str(count(n)) + "次"

   End If

Next k

m = count(0)

For k = 1 To 25

   If    ②   Then m = count(k)

Next k

Label1.Caption = "字母最高出现" + Str(m) + "次"

End Sub

① ②
（3）分析如上代码，“统计”按钮的对象名称为（单选，填字母：A . Command1 / B . CmdTJ / C . CmdTJ_Click / D .统计）
（4）运行该程序，在文本框中输入It's never too late to mend.，单击“统计”按钮后，对语句m = count(k)执行次数的描述，最合理的是
（单选，填字母：A .执行次数介于1-10； B .执行次数介于10-20； C .执行次数介于20-25）

有如下 VB 程序段：

Dim p As Integer, q As Integer, s As Integer, t As Integer

p = Val(Text1.Text)

t = 0

For q = p+ 1 To 2 * p

s = (p * q) Mod (q - p)

If s = 0 Then

t = t+ 1

End If

Next q

Label1.Caption = Str(t)

该程序段运行时，在文本框T extl中输入8 , 则在标签Labell中显示的内容是（）

A . 3 B . 4 C . 5 D . 6

【加试题】输入一个表达式（运算符号只有加减乘除和小括号，表达式是正确的，不需要检查）,求表达式中最后一次运算的运算符号位置。比如表达式a*(b+c)-4+d最后一次运算的运算符号是在第10个位置的“+”，输出10。算法的思想是：从表达式右边开始往左边查找，对碰到的字符分四种情况考虑：

1)若是运算符“+”或“-”保存该位置并结束查找。

2)若是第一次碰到“*”或“/”，保存该位置，若不是第一次碰到“*”或“/”，继续往左边查找。

3)若是“）”，调用函数找到和它对应的“（”位置，跳过该括号，继续往左查找。

4)若是非运算符，继续往左查找。

运行界面如下图：

实现上述功能的 VB 程序如下，但加框处代码有错，请改正。

Function find(y As String , x As Integer ) As Integer

’该函数的功能是：返回表达式 y 中和位于第 x 位置的“）”配对的“（”的位置，代码略

End Function

Private Sub Commandl _ Click ()

Dim s As String , t As Integer , temp As Integer , p As Integer

s = Text1. Text ‘输入表达式

t = Len (s):p = 0

Do While t>0

If Mid ( s, t , 1) =“*” Or Mid ( s, t , 1) =“-” Then ‘处理+、-

temp=t

Exit Do

End If

If ① Then 处理 *、/

temp = t

P=1 ‘用来标记乘号或除号已经出现了

End If

If Mid(s, t, 1)= ")" Then ‘处理括号

②

End If

t=t -1

Loop

Text 2.Text = Str (temp)

End Sub

① ②

“奔跑吧，兄弟”栏目组要在全国各地挑选节目录制的地点。有来自K(1<=K<=25)个不同省份的N(K<=N<=100)个地区送来了各自的竞选材料。由于参选地区太多，没有办法同时呈现所有材料供评委进行选择。栏目组决定选择一段连续区间内的参选地区，这个区间内每个省份的参选地区至少要有1个，求满足要求的最小区间长度。

参选地区用数字1，2，3……N表示，每个地区所属的省份依次存入数组a(1)到a(N)，若1号地区的省份编号是3，即a(1)=3。分析可知，所求区间的长度至少为K(省份的数量)，最大为N(地区的数量)。我们可以通过二分K到N之间的数求得最小区间长度。例如有10个参选地区，分别来自于5个不同的省份，从左到右排列，地区编号依次为2，1，2，4，3，3，5，5，3，5，则最小的一段包含所有5个地区的区间是从第2个到第7个地区，区间长度为6。

（1）若有12个参选地区，分别来自于6个不同的省份，从左到右排列，地区编号依次为2，1，6，4，6，3，1，2，3，5，5，4，则最小的区间长度为。
（2）请在划线处填入合适的代码。
Dim a(1 To 100) As Integer, K As Integer, N As Integer

Private Sub Form_Load()

‘产生N的值,表示地区数,产生K的值,表示省份数

‘产生编号为1到N的地区的省份编号,并存储在数组a中

‘代码略

End Sub

Private Sub Command1_Click()

Dim M As Integer

i = K: j = N

Do While i <= j

If bh(M) = True Then

j = M -1

ans = M

Else

i = M+1

End If

Loop

Text1.Text = Str(ans)

End Sub

Function bh(M As Integer) As Boolean

Dim f(1 To 25) As Integer ‘f(i)表示是否包含省份为i的地区

Dim t As Integer

bh= False

For i = 1 To N-M + 1 ‘枚举以i为起点的M个地区中各个省份是否都包含

For j =

f(a(j)) = 1

Next j

t= 0

For j = 1 To K

Next j

If t = K Then bh= True: Exit Function

For j = 1 To K

f(j) =0

Next j

Next i

End Function

编写VB程序，实现如下功能：在文本框Text1中输入一个十进制整数，单击命令按钮Command1，在标签Label2上显示转换成十六进制数的结果，运行效果如图所示。

（1）在设计程序界面时，要使按钮Command1上的文字显示为“转化成十六进制”，应修改按钮Command1的属性。
（2）为实现上述功能，请在划线处填入合适的代码。
Private Sub Command1_Click()

Dim y As Integer, r As Integer

Dim s As String, t As String

t = "0123456789ABCDEF"

s = ""

y = ①

Do While y > 0

r = y Mod 16

s = ②

y = ③

Loop

Label2.Caption = Text1.Text + "转化成十六进制数为：" + str(s)

End Sub

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

A . 查找法 B . 解析法 C . 穷举法 D . 排序法

下列问题适合使用枚举算法解决的是（）

A . 计算已知半径圆的面积 B . 超市打折方案 C . 校园歌曲大赛的成绩排名 D . 计算10000以内的所有的素数

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

小王到某城市，时间只有一天了，但小王很想到该城市的著名大景区游玩，该城市的著名大景区内共有N（超过 10）个景点，标号为1至N，假设每个景点都有一个进出口。现在只知道每个景点有一条路连接下一个景点。小王想知道，根据这些道路信息，从其中一个景点出发，最后再回到出发景点离开，最多能游玩多少个景点。

图片_x0020_100010

例如，共有N=5个景点，每个景点连接的下一个景点分别是 2，4，2，3，1。

景点号	1	2	3	4	5
下一景点号	2	4	2	3	1

则他可以从2号景点出发，最多可以游玩2号、3号、4号三个景点。程序代码如下：

Private Sub Command1_Click()

Dim a(1 To 100) As Integer, d(1 To 100) As Integer '数组 a 存放下一景点号

Dim jd As String, m As String, c As Integer, i As Integer

Dim s As Integer, p As Integer, k As Integer, ans As Integer

jd=Text1.Text+","

s=0 : c=0

For i=1 To Len(jd)

m=Mid(jd,i,1)

If m<>"," Then

①

Else

c=c+1 : a(c)=s: s=0

End If

Next i

For k=1 To 100 d(k)=0

Next k

ans=0: k=0

For i=1 To c '枚举起点

If d(i)=0 Then p=i

Do While p<=c

If d(p)=0 Then

k=k+1 :d(p)=k

Else

②

If y>ans Then ans=y k=0

Exit Do

End If

'改错

Loop

End If

Next i

Text2.Text=Str(ans)

End Sub

（1）若有7个景点，且每个景点的连接情况为：6，3，5，2，7，5，4，那么小王最多可以游玩的景点数是。
（2）在上面的程序代码中的下划线中填入代码
① ②
（3）在上面的程序代码中，加框处代码有错，请改正。

从离地500米的空中自由落下一个小球，求从开始落下的时刻起，小球在最后1秒内的位移（重力加速度g以9.8米/秒2计）。程序如下，回答以下问题。

import math

h = 500

g = 9.8

t = math.sqrt（2*h/g）

hx = g*（t-1）*（-1）/2

hh = h-hx

print（“小球最后1秒下落的位移是：”，hh，“m”）

（1）该程序代码中使用了库，库的名称是_____。

A . Limport B . math C . sqrt D . print
（2）该程序代码中使用了常量，它的名称是_____。

A . h B . t C . 500 D . hh
（3）该程序代码中使用了变量hh，它的数据类型是_____。

A . int B . float C . 列表 D . 字符串
（4）该程序中print（“小球最后1秒下客的位移是：”，hh，“m”），其中“m”的数据类型是_____。

A . int B . float C . 列表 D . 字符串
（5）该程序使用了物理公式计算空中自由落下个小球的位移，采用的算法是_____。

A . 解析算法 B . 穷举算法 C . 递归法 D . 选择排序

以下适合用解析算法解决的问题是( )

A . 将10个评委的打分按由大到小的顺序进行排序 B . 计算出租车费 C . 找出一管乒乓球中质量不符合标准的球 D . 求三位正整数中的“水仙花数”

一个十进制整数的二进制表示中，如果数字“1”的个数多于数字“0”的个数，则称该整数为A类数。如十进制整数26的二进制表示为11010，26是一个A类数。下列VB程序的功能是：统计前1000个自然数中A类数的个数，并在文本框中输出。请在划线处填入合适代码。

Private Sub Command1_Click()

Dim i As Integer, n As Integer

Dim s As Integer, t As Integer, k As Integer

s = 0

For i = 1 To 1000

n = i

t = 0

k = 0

Do While n > 0

If n Mod 2 = 1 Then t = t + 1 Else k = k + 1

Loop

If Then s = s + 1

Next i

Text1.Text = Str(s)

End Sub

找出满足各位数字之和等于5的所有三位数可采用的算法是（）。

A . 解析算法 B . 冒泡排序 C . 枚举算法 D . 选择排序

下列说法符合枚举算法的是（）

A . 逐一判断，强调不遗漏且不重复地验证条件 B . 根据条件判断是否合适，保留合适的，舍弃不合适的 C . 为了提高解决问题的效率，使可能解的范围将至最小 D . 可作为某类问题时间性能的底线，用来引出同样问题的更高效率的算法

在一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”。即一个数除以3余2，除以5余3，除以7余2，求这个数。

while (i%3!=2 i%5!=3 or i%7!=2):

print(i)

用火柴棒，摆出下面的的自然数。

下列说法正确的是（）

A . 可以用6根火柴棒摆放出0、9、13 B . 可以用6根火柴棒摆放出0、8 C . 6根火柴棒能摆放的最大数是111 D . 可以用6根火柴棒摆放出0、6、5

[二进制枚举法]小明在玩一个翻转棋盘的游戏，其中棋子只有黑白两面，界面如图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代码如下，请回答下列问题。

（1）若某方案用十进制表示为137，则总共选择了个棋子。
（2）完成程序中填空。
Dim a(16) As Integer, b(16) As Integer, min_ _c As Long

'a数组储存棋盘原状态，b数组储存翻转后的棋盘状态

Function check() As Boolean    '判断棋盘是否纯色

   Dim flag As Boolean, i As Integer

    flag= True

    For i=1 To 15

        If b(i) <> b(i+1) Then flag= False

    Next i

    check = flag

End Function

Private Sub Command1_Click()

Dim k As Integer, c As Integer, i As Long, j As Long

    For i=0 To 2^16- 1

        For j=1 To 16     '初始化棋盘

            b(j)=a(j)

        Next j

        k=16

        c=0

        j=i

        Do While j>0

            If Then

                b(k)=1- b(k)

                If k> 4 Then b(k-4)=1-b(k-4)

                If k< 13 Then b(k+4)=1- b(k+4)

                If k Mod 4 <> 0 Then b(k+1)=1- b(k+1)

                If Then b(k-1)=1-b(k- 1)

                c=c+ 1

            End If

            j=j\2

            k=k- 1

        Loop

        If Then

            min_ c= c

        End If

    Next i

    If min_ c=17 Then Label1. Caption= "无法翻转为纯色！" Else Label1. Caption= Label 1. Caption+Str(min_c)

End Sub

Private Sub Form_ Load()

    '生成棋盘状态，用数组a(1)~a(16)表示，代码略

    For i=1 To 16

        s=s+Str(a(i))

        If i Mod 4=0 Then List1. AddItem s : s=" "

    Next i

End Sub

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

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