第九单元 算法的程序实现
单元小结
知识系统构建
/
第九单元 算法的程序实现
单元检测题组
/时间:40分钟 /分值:50分
一、选择题(每题3分,共27分)
1.对包含100个元素递增排序的数组a,采用对分查找法找某关键字,若查找不成功,则关键字的比较次数最多是( )
A.100 B.6 C.7 D.8
答案 C 本题考查对分查找的基本原理。n个元素中查找不成功的最多比较次数为[log2n]+1。
2.有如下某排序算法程序段:
For i=1 To 3
k=i
For j=i+1 To 6
If a(j) > a(k) Then k=j
Next j
t=a(i):a(i)=a(k):a(k)=t
Next i
数组元素a(1)到a(6)的值依次为“8,2,9,3,5,1”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为( )
A.8,2,9,3,5,1 B.9,2,8,3,5,1
C.9,8,5,2,3,1 D.9,8,5,3,2,1
答案 D 本题考查排序算法及其程序的实现。i=1时,代入循环体,计算得到数组元素的值依次为9,2,8,3,5,1。i=2时,代入循环体,计算得到数组元素的值依次为9,8,2,3,5,1。i=3时,代入循环体,计算得到数组元素的值依次为9,8,5,3,2,1。
3.某VB程序段如下:
For i=1 To 6
j=7
Do While j > i
If a(j)>a(j-1) Then
a(j)=a(j)+a(j-1)
a(j-1)=a(j)-a(j–1)
a(j)=a(j)-a(j-1)
End If
j=j-1
Loop
Next i
For i=3 To 6
s=s+a(i)
Next i
Label1. Caption=Str(s)
已知数组元素a(l)到a(7)的值依次为“8, 2, 3, 7, 10, 6, 5”,则执行该程序段后,标签Label1中显示的是( )
A.21 B.26 C.41 D.18
答案 A 首先理解 a(j)=a(j)+a(j-1),a(j-1)=a(j)-a(j-1),a(j)=a(j)-a(j-1)这三个语句实际上就是将a(j)与 a(j-1)两数据交换。两数交换的经典写法是:t=a,a=b,b=t。程序首先实现数组a中的数据降序,得到“10,8,7,6,5,3,2”,而后将 a(3),a(4),a(5),a(6)的值相加输出。
4.有如下程序段:
Dim a(4) As Integer
Private Sub Command1_Click()
Dim s As String
a(1)=10:a(2)=30:a(3)=20:a(4)=40
s=doit(4)
Label1.Caption=s
End Sub
Function doit(k As Integer) As String
If k=1 Then
doit=Str(a(1))
Else
doit=doit(k-1) & Str(a(k))
End If
End Function
程序运行后,标签Label1中显示的内容是( )
A.10 20 30 40 B.10 30 20 40
C.40 30 20 10 D.40 20 30 10
答案 B 本题考查递归程序。递归调用过程如下:
/
5.用以下对分查找算法:在一个包含有重复元素且从小到大排序(相等元素排在一起)的整数数组a中,查找某个重复出现的整数key,其中数组元素的总个数是n。
i=1: j=n
Do While i <=j
m=(i+j) 2
If a(m) < key Then i=m+1
Else
j=m-1
End If
Loop
那么执行该程序后,下列说法正确的是( )
A.程序可以找到重复元素key最开始出现的位置,该位置信息由变量i指示
B.程序可以找到重复元素key最后出现的位置,该位置信息由变量i指示
C.程序可以找到重复元素key最开始出现的位置,该位置信息由变量j指示
D.程序可以找到重复元素key最后出现的位置,该位置信息由变量j指示
答案 A 本题考查对分查找算法的理解和应用。由程序可知,当i≤j时程序要循环,而循环时,当a(m)≥key时,变量j移动,这就表明当找到key时,指示变量j势必会跑到key所在位置的前面去,key所在位置由i来指示。由升序排序和j的移动方向可知,这是起始位置。
6.有以下VB程序段
i=1: j=10: flag=True: cs=0
Key=Int(Rnd()*10)+28
Do While i <=j And flag=True
m=(i+j) 2 : cs=cs+1
If a (m)=Key Then
flag=False
Else If a(m) < Key Then
i=m+1
Else
j=m-1
End If
Loop
数组元素a(1)到a(10)依次是3 10 17 23 27 30 35 40 45 50,变量cs的值可能是( )
A.1或2 B.2或3
C.3或4 D.4或5
答案 C 本题考查对分查找,key=Int(Rnd() * 10)+28即产生[28,37]的随机整数。cs表示查找次数,10个数查找过程如下(只需要考虑28至37范围内的数):
3
10
17
23
27
30
35
40
45
50
①
③
④
②
因此三次(如30)、四次(如35)都可能,找不到的情况也可能是三次(如28)或四次(如33),10个数不管找不找得到,最多查找次数不超过int(log210)+1=4次。
7.有如下程序段:
For i=1 To 2
k=i
For j=i+1 To 5
If d(k) < d(j) Then k=j
Next j
If k <> i Then t=d(k): d(k)=d(i) :d(i)=t
Next i
经过该程序段“加工”后,数组元素d(1)到d(5)的值依次为“44, 35, 30, 11,7”,则数组元素d(1)到d(5)的原始数据依次为( )
A.30,44,7,11,35 B.30,11,44,7,35
C.44,30,11,7,35 D.30,7,44,11,35
答案 D 该段程序仅进行了两趟排序,数据就已完成降序排序。而选项 A 需要三趟,B、C两个选项都需要四趟才能使数据完成降序排序。 所以答案选 D。
8.有如下VB程序段:
i=1
j=6
s=“”
Key=Text1. Text
Do While i <=j
m=Int((i+j) / 2+0. 5)
s=s+“ ”+a(m)
If Key > a(m) Then
i=m+1
Else
j=m-1
End If
Loop
Text1. Text=s
数组元素a(1)到a(6)的值分别为“Beijing”“Guangdong”“Jiangsu” “Jiangxi”“Shanghai” “Zhejiang”,己按字典序排序。当key的值为“Zhejiang”时,单击命令按钮Command1,文本框Text1中显示的内容为( )
A.Jiangxi Zhejiang
B.Jiangsu Shanghai Jiangxi Zhejiang
C.Jiangxi Zhejiang Shanghai
D.Jiangsu Shanghai Zhejiang
答案 C 本题考查对分查找,第一次查找时i=1,j=6,得到m=4,因此s=“Jiangxi”,因为key>a(m),因此第二次查找时i=5,j=6,得到m=6,因此s=“Jiangxi Zhejiang”,此时key=a(m),执行j=m-1=5;因此第三次查找时i=5,j=5,得到m=5,因此s=“Jiangxi Zhejiang Shanghai”,此时key>a(m),因此执行i=m+1=6,此时i>j,退出循环。所以答案选择C。
9.有如下VB程序段:
s=“7218634594” : n=Len(s): c=0
For i=1 To n-1
a(i)=Val(Mid(s, i, 2))
Next i
For i=1 To n-2 Step 2
k=i
For j=i+2 To n-1 Step 2
If a(j) < a(k) Then k=j
Next j
If k <> i Then
t=a(i): a(i)=a(k): a(k)=t: c=c+1
End If
Next i
Text1.Text=Str(c)
该程序段运行后,Text1中显示的内容是( )
A.1 B.2 C.3 D.4
答案 B 首先获取 a数组的各元素为72,21,18,86,63,34,45,59,94。然后从外层For i=1 To n-2 Step 2看出,仅对奇数位上的数据排序。变量c统计排序过程中数据交换的次数。第一趟排序,数据“ 72 ”与“ 18 ”交换。第二趟排序,数据“ 72 ”与“ 45 ”交换。而后奇数位上的数据已有序。 所以答案选 B。
二、非选择题(共23分)
10.现有n根棍子,第i根棍子的长度为ai。想要从中选出三根棍子组成周长尽可能长的三角形,输出最大的周长;若无法组成三角形,则输出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
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=max(longest, c) ’①
rest=c-longest ’rest 保存最短的两条边的和
If ans > c Then ’②
ans=max(ans , c)
End If
Next k
Next j
Next i
Print ans
End Sub
答案 ①max(a(i), max(a(j), a(k)))(或其他写法) ②rest > longest
解析 由三重For循环和变量c的组成可以判断这是一个枚举算法,c是当前枚举到的周长。而由程序的输出可知ans是最长的周长,显然要找到最大值,需要比较,还有一个很重要的条件就是三条边可以组成三角形。大小比较的任务已经由ans=max(ans,c)来完成,那么第②空就是判断能否成为三角形的条件。这里可以写成a(i)+a(j)>a(k)&a(i)+a(k)>a(j) &a(j)+a(k)>a(i)的复合表达式,但由前面的rest=c-longest可以猜测出longest保存了最长边,而rest是剩余两边之和。于是第②空的条件可以简单地变成最短两边之和大于最长边,即rest>longest。而第①空就是a(i),a(j),a(k)三者的最大值,可以迭代调用函数max(),即现调用任意两个,再调用第3个,如max(max(a(i),a(j)),a(k))或者任意交换这三个变量的书写位置都可以。
11.小王编写“合并区间” VB程序,功能如下:窗体加载时,获取并存储合并前的区间数据,并显示在列表框List1中。单击“合并”按钮后,以区间左端点数值对区间进行升序排序,然后相邻区间的相交进行合并,最后在列表框List2上显示合并后的区间。程序运行如图所示:
/
实现以上功能的VB程序如下,在横处填入合适的代码。
Dim a(1 To 20) As Integer ??存储区间的左端点数值
Dim b(1 To 20) As Integer ??存储区间的右端点数值
Private Sub Form_Load()
’将区间左端点存入数组a,区间右端点存入数组b,并在列表框List1显示,代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim curL As Integer, curR As Integer
For i=1 To n-1
For j=l To n-i
If ① Then?
t=a(j): a(j)=a(j+1): a(j+1)=t
t=b(j): b(j)=b(j+1): b(j+1)=t
End If
Next j
Next i
curL=a(1): curR=b(1)
For i=2 To n
If ② Then?
If curR < b(i) Then ③ ?
Else
List2.AddItem“["+Str(curL)+Str(curR)+"]”
curL=a(i): curR=b(i)
End If
Next i
List2. AddItem “[”+Str(curL)+Str(curR)+“]”
End Sub
答案 ①a(j) > a(j+1) ②a(i) <=curR ③curR=b(i)
解析 第①空,以区间左端点数值,即数组a,对区间进行升序排序。
第②空和第③空,这是需要合并区间的情况,首先理解变量 curR 的含义,curR 表示第i个区间的上一个区间的右端点数值。因此如果当前区间的左端点数值即a(i)<=curR,而当前区间的右端点数值即b(i)>curR时,上一个区间与当前区间就可以合并。因此第②空填a(i) <=curR。第③空是合并后,右区间curR则等于第 i 个区间右端点数值。
12.插数。输入一个整数x,要将x插入到n(n<50)个有序(按降序排列)数据中,并使数据序列仍保持有序,试求出x应插入的位置。界面设计如图所示。
/
程序说明:
(1)其中n由文本框Text1中数据得到,x由文本框Text2中数据得到,插入位置显示在文本框Text3中。
(2)其中n个有序数据将通过随机函数Rnd产生,并对n个数进行降序排序后存入数组a中,同时显示在列表框List1中。
为了实现这一目标,完善下面的VB程序,在横线处填入合适的语句或表达式,完成程序设计。
Private Sub Command1_Click()
Dim a(1 To 50)As Integer
Dim n As Integer,i As Integer
Dim x As Integer,temp As Integer
Randomize
List1.Clear
n=Val(Text1.Text)
x=Val(Text2.Text)
’随机产生n个数,并存放至a数组中
For i=1 To n
a(i)=Rnd*200+1
Next i
’将数组a中的数按降序排序
For i=2 To n
For j=n To i Step-1
If (1) Then?
temp=a(j):a(j)=a(j-1):a(j-1)=temp
Next j
Next i
’将排序后的数组元素显示在列表框List1中
For i=1 To n
List1.AddItem Str(a(i))
Next i
’插入操作
If (2) Then?
i=n+1
Else
(3) ?
Do While x i=i+1
Loop
End if
’在文本框Text3中显示插入位置
Text3 Text=Str(i)
End Sub
(1) 。?
(2) 。?
(3) 。?
答案 (1)a(j)>a(j-1) (2)x<=a(n) (3)i=1
解析 本题主要考查排序算法的程序实现。
(1)本题采用了冒泡排序。冒泡排序的算法特点是相邻两个元素的两两比较,并根据需要交换,代码中a(j)与a(j-1)的交换语句说明该程序采用了冒泡排序。因为是降序排序,因此大的数在前,小的数在后,如果次序反了,则需要交换两数。因此该处应该填:a(j)>a(j-1)。
(2)变量i用于存储x应该插入的位置。由于数据源是从大到小排列,因此如果x小于或等于数据源中最后一个数据,则它应该插在最后面,这是最简单的情况。该数据源总共有n个数,最后一个数据是a(n)。因此如果x≤a(n),则i=n+1。
(3)如果x比数据源中最后一个数据要大,那么就要寻找它合适的位置。方法是通过循环语句,将x与该数列中的每一个数据a(i)比较,如果xa(i),则当前的i值就是x该插入的位置。
13.n个数据的冒泡升序排序需要经过n-1遍的加工,每一遍加工自下而上比较相邻两个数据,把较小者交换到上面,在第i遍加工过程中需要进行n-i对数据的比较。在某些情况下,第i遍加工过程中,在上面部分较小数据已经有序的情况下,不需要再进行n-i对数据的比较。如对“17, 18,19, 24, 23, 20”这6个数据排序中,第1遍排序结束后数据为“17, 18,19, 20, 24, 23”,第2遍排序时不再需要对20及其前面3个数据进行比较。以下程序实现了冒泡排序的优化,在横处填入合适的代码。
Dim n As Integer
Dim a(1 To 100) As Integer
’n=10,排序前生成的数据存储在数组a中,并在列表框List1中显示,代码略
Private Sub Command1_Click()
Dim i As Integer, j As Integer, start As Integer, t As Integer
i=2
Do While i < n start=n
For j=n To i Step-1
If ① Then?
t=a(j):a(j)=a(j-1):a(j-1)=t
② ?
End If
Next j
i=start+1
Loop
For i=1 To n
List2.AddItem ③ ?
Next i
End Sub
答案 ①a(j) < a(j-1) ② start=j ③ Str(a(i))
解析 第①空,从图中得知程序要实现升序排序,所以只有当后面的数据小于前面的数据时才需要数据交换,而从后面交换的语句中可以看出是 a(j) 与 a(j-1)交换,所以填 a(j) < a(j-1)。
第②空,冒泡升序排序优化即每一趟排序记录下最后一个数据交换的位置,那么下一趟排序时就不需要对该位置前面的数据进行比较了。因此把每一趟的最后一个数据交换的位置定义为下一趟排序时的结束位置,所以 start=j 。
第③空, 列表框中输出排序好的数组 a,同时注意列表框输出结果是字符串类型。
14.查找最接近的数。编写一个查找最接近的数的VB程序:程序运行时,在文本框Text1中输入产生随机数的个数(1到100之间),单击命令按钮“产生随机数并升序排列”后,在列表框List1中显示已经按升序排列后的随机整数。然后在文本框Text2中输入要查找的整数,单击命令按钮“查找”后,在标签Label3中显示随机整数序列中与待查找数最接近的整数(当最接近的数有2个时,输出较大的一个)。程序运行效果如图所示。实现上述功能的VB代码如下,请在横线处填入合适代码。
/
Dim n As Integer ’存储随机数的个数
Dim f(1 To 100) As Boolean ’f (i)为true时表示随机整数i已经产生过
Dim a(1 To 100) As Integer ’依次存放升序排序后的n个随机数
Private Sub Command1_Click()’命令按钮“产生随机数并升序排列”的单击事件
Dim i As Integer
Randomize
For i=1 To 100
f(i)=False
Next i
n=Val(Text1. Text)
For i=1 To n
t=Int(Rnd * 100+1)
Do While f(i)=True
t=Int (Rnd * 100+1)
Loop
① ?
Next i
j=0
For i=1 To 100??实现排序并输出
If f(i)=True Then
② ?
a(j)=i
List1.AddItem Str(i)
End If
Next i
End Sub
Private Sub Command2_Click()??命令按钮“查找”的单击事件
Dim key As Integer
key=Val(Text2. Text)
If key <=a(1) Then Label3. Caption=Str(a(1)) : Exit Sub
If key >=a(n) Then Label3. Caption=Str(a(n)) : Exit Sub
L=1: R=n
Do While L <=R??找到与key较为接近的两个数a(R)和a(L)
m=(L+R) 2
If key <=a(m) Then
R=m-1
Else
L=m+1
End If
Loop
If ③ Then ??在a(R)和a(L)中选出更接近key的数?
Label3. Caption=Str(a(R))
Else
Label3. Caption=Str(a(L))
End If
End Sub
答案 ① f(t)=True ②j=j+1 ③Abs(a(R)-key) < Abs(a(L)-key)
解析 ①处根据题干可知该处为产生不重复的随机数,产生之后将对应的f数组内的值改为 True,标记该数字已产生,故①f(t)=True,②将产生的数依次输出,故②j=j+1,③通过对分查找到二个数 a(R)、 a(L),判别更接近key的数。故③Abs(a(R)-key) < Abs(a(L)-key)。
15.有100个大小形状一样的玻璃球,其中有1个玻璃球的重量轻于其他99个玻璃球,如何用一台无砝码的天平,以最快的速度找出这个轻玻璃球?运用“三分筛选”法来模拟“寻找”这个轻玻璃球的算法如下:
步骤1:如果待筛选的玻璃球个数<3,则认定己经找出了这个玻璃球(认定方法参照步骤2中描述), 停止筛选,并输出经过的筛选总次数;否则,重复执行步骤2。
步骤2:按编号依次将玻璃球均分成3份,如果有多余的放入第3份中;比较第1、2份的玻璃球重量:
①如果第1份等于第2份的重量,则选取第3份的玻璃球作为下一次筛选的对象;
②如果第1份小于第2份的重量,则选取第1份的玻璃球作为下一次筛选的对象;
③如果第1份大于第2份的重量,则选取第2份的玻璃球作为下一次筛选的对象;
重复执行步骤1。
例如:第1次筛选的小球编号区间是1~100,均分成三份的待称重小球编号分别是1~33、34~66、67~100;第 2次则选取以上3份中的一份进行再筛选、再均分……直至找到。
解决上述问题的VB程序功能如下:运行程序,在列表框List1中显示100组数据,分别代表每个编号及对应的小球重量(其中有且只有一个小球的重量与其他小球不同),单击“筛选”按钮Command1,在列表框 List2中显示每次筛选的编号区间和完成筛选的总次数。程序运行界面如图。
(1)如果编号为88的小球是最轻的,按照题中给定算法,找到此小球需经历的筛选次数是
次。?
(2)实现上述功能的VB程序如下,请在横线处填入合适的代码。
/
Const maxn=100
Dim a(1 To maxn) As Integer
Dim w(1 To 2) As Integer ??数组w用来存储第1份和第2份小球的重量
Private Sub Form Load()
??此处代码用来模拟产生100个小球的重量,分别存储在数组元素a(1)~a(100)中;
??其中只有1个小球的重量为8,随机存储在数组a的某元素中,其余重量均为10;
??此处代码略
End Sub
Private Sub Command1_Click()
Dim left As Integer, right As Integer ??left 为起始编号,right 为结束编号
Dim s As Integer, c As Integer ??s为每次查找的区间长度
left=1: right=maxn
c=1: s=right: i=0
List2. AddItem Str (i+1)+“--->”+Str(maxn)
Do While right-left > 3
w(1)=0: w(2)=0: k=1
i=left
s= ① ?
Do While i<=(s 3) * 2+left-1??Do语句用于将待筛选的数据进行区域划分
w(k)=w(k)+a(i)
If i=(s 3) * k+left-1 Then k=k+1
i=i+1
Loop
If w(1)=w(2) Then
left=left+(s 3) * 2
Elself w(1) < w(2) Then
② ?
Else
right=left+(s 3) *2-1
left=s 3+left
End If
③ ?
List2. AddItem Str(left) &“--->” & Str(right)
Loop
List2. AddItem “经过” +Str (c)+“次后找到”
End Sub
答案 (1)5 (2) ①right-left+1 ②right=s 3+(left-1) ③c=c+1
解析 (1)处根据题干第一次查找范围[1,100],第二次查找范围[67,100],第三次查找范围[78,88],第四次查找范围[84,88],第五次查找范围[86,88],区间长度小于等于3,结束,故为5次。(2)①处为赋值区间长度的初始值,故①right-left+1,②为当第一份小于第二份的情况,待查找在第一份里找,赋值右端点值,故②right=s 3+(left-1),③为满足一次区间相关次数加1故③c=c+1。
16.活动课上,n个学生要两两组队进行拔河比赛,要求每个小组总体重不超过120kg,小林想知道最多可以组成多少个队伍,并希望得到可行的组队方案。于是设计了如下界面的程序,在文本框Text1中输入n 个学生的体重(数字之间用逗号隔开),单击“队伍”按钮Command1后在标签Label1上显示最多可组队数量,同时在列表框List1输出方案。
/
实现上述功能程序如下,在横线处填入合适的代码。
Dim n As Integer
Dim a(1 To 50) As Integer
Sub makedata(s As String) ??该过程实现将输入的体重分别存入数组a中
Dim in As Long, x As Long, c As String, i As Integer
m=Len (s) : n=0
For i=1 To m
c=Mid(s, i, 1)
If c >=“0” And c <=“9” Then
① ?
x=x+Asc(c)-Asc(“0”)
Else
If x > 0 Then n=n+1: a(n)=x
x=0
End If
Next i
n=n+1: a(n)=x
End Sub
Private Sub Command1_Click()
Dim s As String, i As Integer, j As Integer, t As Integer
Dim cnt As Integer, st As Integer, ed As Integer
s=Text1.Text Call makedata(s) ??调用过程
For i=1 To n-1??实现降序排序
For j=n To i+1 Step-1
If ② Then?
a(j)=a(j)+a(j-l) : a(j-l)=a(j)-a(j-l) : ③ ?
End If
Next j
Next i
??下列程序段实现计算最多可组队伍
cnt=0: st=1: ed=n
Do While st < ed
If a(st)+a(ecl) <=120 Then
List1. AddItem Str(a(st))+“和”+Str(a(ed))+“组队”
cnt=cnt+1
st=st+1
④ ?
Else
st=st+1
End If
Loop
Label2. Caption=“最多可以组”+Str (cnt)+“组队伍”
End Sub
答案 ① x=x * 10 ② a(j) > a(j-1) ③ a(j)=a(j)-a(j-1) ④ ed=ed-1
解析 第①空,变量 c 为文本框中截取下来的每一个字符,如果截取下来的字符是数字,那么通过它的ASCII 码值减去数字“0”的 ASCII 码值求得该数值存储在变量 x 中,x=x+Asc(c)-Asc(“0”),如果截取下来的下一个字符还是数字,那么 x 需要乘以 10 变成十位上的一个数,即 x=x * 10,然后与新截取下来的数值相加 x=x+Asc(c)-Asc(“0”),得到一个两位数的体重存储在变量 x 中。
第②空,冒泡排序,降序,从后往前,相邻两数比较大小,后面的数大于前面的数时需要交换,即 a(j) > a(j-1)。
第③空,数据 a(j) 与 a(j-1)交换。
第④空, 组队伍, 第一个数据与最后一个数据加起来如果小于 120 那么可以组一队。 组队后组数加 1,即 cnt=cnt+1,同时指向下一组数据的位置,即起始位置往后移一个 st=st+1,终止位置往前移一个 ed=ed-1。
教师备用题库
1.火柴算术游戏,给定n(n<=24)根火柴,恰好用尽n根火柴拼凑出A+B=C形式的算式,问一共有多少种可行方案,请输出方案的总数,已知0~9每个数字所需的火柴根数如下表所示:
/
注意:(1)其中A+B=C 等式中的“+”“=”需要用去4根火柴。
(2)0+4=4 与4+0=4算作一种方案。
例如 n=18,符合条件的算式共有5个:0+4=4,0+11=11,1+10=11,2+2=4,2+7=9。
小明设计了一个程序,在Text1中输入火柴数量,单击“计算”按钮,在Label1中输出总的可行方案数,并在List1中输出所有可行的算式。
/
程序代码如下,加框处代码有误,请修改。
Dim s(0 To 9) As Integer
Private Sub Command1_Click()
Dim n As Integer, a As Integer, b As Integer, count As Integer
count=0
n=Val(Text1.Text)
For a=0 To 999 Step 1
For b=a To 999 Step 1
If a+b+4=n Then '①
List1.AddItem Str(a)+"+"+Str(b)+"="+Str(a+b)
count=count+1
End If
Next b
Next a
Label2.Caption="共"+Str(count)+"种方案"
End Sub
Function gs(ByVal x As Integer) As Integer
Dim tmp As Integer
tmp=0
If x=0 Then tmp=s(0)
Do While x > 0
tmp=x Mod 10 '②
x=x 10
Loop
gs=tmp
End Function
Private Sub Form_Load()
s(0)=6: s(1)=2: s(2)=5: s(3)=5: s(4)=4
s(5)=5: s(6)=6: s(7)=3: s(8)=7: s(9)=6
End Sub
答案 ①gs(a)+gs(b)+gs(a+b)+4=n ②tmp=tmp+s(x Mod 10)
解析 ①处枚举所有A+B=C的算式,在满足算式成立条件下,对A,B,A+B分别调用gs自定义函数以得到它们各自的火柴数量,然后判断火柴总消耗量是否恰好等于n。
②处gs自定义函数内部,为了得到参数x的火柴数量,需先分离x的各位数字,然后提取对应数字所需的火柴数s(x Mod 10),再累加得到x所需的火柴数量tmp,故该处代码为“tmp=tmp+s(x Mod 10)”。
2.(2015浙江高考模拟)下列程序的功能是将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 integer) As Boolean
f=True
For i=2 To Sqr(x)
If x Mod i=0 Then (1) ?
Next i
End Function
Private Sub Command1_Click()
n= (2) ?
For a1=2 To n
For a2=a1 To n
For a3=a2 To n
If (3) 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
答案 (1)f=False (2)Val(Text1.Text) (3)n=a1+a2+a3
解析 (1)函数f(x)的功能是判断x是否为质数,如果是质数则返回值为true,否则返回值为false。如果2到Sqr(x)中有一个数能被x整除,则x就不是质数,也就是函数返回值为false。因此此处填f=False。
(2)变量n是待分解的自然数,该值从文本框text1中输入。因此该处填x=Val(Text1.Text)。
(3)符合条件的解需要满足两个条件:a1、a2和a3都是质数;a1、a2和a3的和等于被分解的自然数。
第1节 枚举算法及程序实现
模拟演练
1.一个十进制整数的二进制表示中,如果数字“1”的个数多于数字“0”的个数,则称该整数为A类数。如十进制整数26的二进制表示为11010,26是一个A类数。下列VB程序的功能是:寻找前1 000个自然数中所有A类数在List1中输出,并将统计个数在Text1中输出。
请回答以下问题。
(1)十进制数37 (选填:是/不是)A类数。?
(2)请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim i As Integer, n As Integer
Dim s As Integer 's为A类数的个数
Dim t As Integer 't为二进制数中“1”的个数
Dim k As Integer 'k为二进制数中“0”的个数
s=0
For i=1 To 1000
n=i:t=0:k=0
Do While n > 0
If ① Then t=t+1 Else k=k+1?
② ?
Loop
If t>k Then
List1.Additem str(i)
s=s+1
End If
Next i
Text1.Text=Str(s)
End Sub
答案 (1) 不是 (2)① n mod 2 <>0 或n mod 2=1 ② n=n2
解析 本题主要考查算法的基础知识。
(1)根据计算,十进制数37转换为二进制为100101,不是A类数。
(2)①从程序代码可以得知,由于变量t保存二进制数中“1”的个数,因此前面的条件必然是n mod 2=1。②根据十进制转换为二进制的“除2取余倒排法”的运算法则,n的值将被2整除,故n=n2 。
2.(2016温州3月选考模拟,16,4分)如果两个质数的差为2,则这两个质数称为孪生质数对。编写VB程序,实现如下功能:单击“显示孪生质数对”按钮Command1,在列表框list1中显示100以内的所有孪生质数对(运行效果如图所示)。
/
实现上述功能的VB代码如下,但加框处代码有错,请改正。
Dim a(1 To 50)As Integer
Private Sub Command1_Click()
Dim i As Integer
k=0:i=3
Do While i<=100
If prime(i) Then ??(1)
k=k+1
a(k)=i
End If
i=i+2
Loop
For i=2 To k
If a(i)=a(i+1)+2 Then ??(2)
List1.AddItem Str(a(i-1))+“和”+Str(a(i))
End If
Next i
End Sub
Function prime(x As Integer)As Boolean
prime=False
For i=2 To Int(Sqr(x))
If x Mod i=0 Then
prime=True
Exit For
End If
Next i
End Function
答案 (1)Not prime(i)或 prime(i)=False
(2)a(i)=a(i-1)+2
解析 本题考查的是程序阅读能力和函数知识。通过阅读不难发现函数prime的功能是质数的判断,如果是质数,则返回值为False,否则返回值为True。在Do循环中,通过观察发现(1)处正确答案为Not prime(i)或 prime(i)=False。a(i)存储100以内的所有质数,在For循环中,循环变量初始值为2,所以(2)处正确的语句为a(i)=a(i-1)+2。
3.珠心算是在大脑中以算珠表象作为载体,运用珠算法则所进行的计算。某学校的珠心算老师采用一种快速考查珠心算加法能力的测验方法。他随机给出一个正整数集合,集合中的数各不相同,然后要求学生回答:其中共有多少个数恰好等于集合中另外两个(不同的)数之和?例如对于集合{1,2,3,4},一共有2个数等于集合中另外两个数之和,它们是3、4(4=3+1,3=2+1)。将上述算法编写成程序,其功能如下:程序运行时产生n个范围在[1,100]内的不同的随机整数存储在数组a中,并在列表框List1中显示。单击按钮Command1后,在标签Label1上输出结果,如图所示。
/
(1)对于集合{1,2,3,4,5,6},一共有 个数等于集合中另外两个数之和。?
(2)实现上述功能的VB程序如下,请在划线处填入合适代码。
Const n=12
Dim a(1 To n) As Integer
Dim flag(1 To 100) As Boolean
Private Sub Form_Load()
Dim i As Integer, t As Integer
For i=1 To 100
flag(i)=False
Next i
i=1
Do While i <=n
t=Int(Rnd * 100)+1
If Not flag(t) Then
① ?
List1.AddItem Str(t)
flag(t)=True
i=i+1
End If
Loop
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, ans As Integer
ans=0
For i=1 To n
For j=i+1 To n
If a(i)+a(j) <=100 Then
If ② Then?
ans=ans+1
flag(a(i)+a(j))=False
End If
③ ?
Next j
Next i
Label1.Caption="共有"+Str(ans)+"个数!"
End Sub
答案 (1)4 (2)①a(i)=t ②flag(a(i)+a(j))或flag(a(i)+a(j))=True ③End If
解析 本题解题的关键在于理解标记数组flag的作用。逻辑类型数组flag用于标记集合中的某个数是否存在,flag(i)=True,表示i是集合的一个元素。①如果产生的随机整数t在数组中还未存在,则将该随机数存储到数组a中,所以①处答案为a(i)=t。②通过双循环穷举任意两个元素之和,如果两数之和等于数组中的某个数,那么就找到一个数,计数器ans累加1。a(i)+a(j)的值是否等于集合中
的某个数,可以通过flag(a(i)+a(j)) 来判断,如果flag(a(i)+a(j))=True表示
存在这个数。③分析语法结构,两个If语句块需要两个End If。
第1节 枚举算法及程序实现
真题再现
学考题组
1.(2018浙江4月学考+选考,14,5分)某种编码以 4 位二进制码为一组,每组前两位表示方向,后两位表示距离。编写一个程序,将编码翻译成方向和距离,距离值为每组编码后两位二进制码转换为十进制数的值。具体功能如下:在文本框Text1中输入连续多组编码,单击“翻译”按钮Commandl,结果显示在列表框 List1 中。程序运行界面如图所示。
/
要使程序运行时,文本框 Text1的Width属性值为2018,可在 Form_Load事
件过程中添加语句 (单选,填字母:A.Width=2018/B.Text1. Width=2018/C.Width.Text1=2018) 。?
(2)实现上述功能的 VB 程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s As String, c As String, d As String
Dim n As Integer, b1 As Integer, b2 As Integer, v As Integer, i As Integer
s=Text1.Text: n=Len(s):i=1
Do While i<=n
c=Mid(s,i,2)
If c=“00”Then
d=“东”
ElseIf c=“01” Then
d=“南”
ElseIf c=“10” Then
d=“西”
Else
d=“北”
End If
b1=Val(Mid(s,i+2,1))
b2=Val(Mid(s,i+3,1))
v= ① ?
List1.AddItem d+“”+Str(v)
② ?
Loop
End Sub
(3)若文本框 Text1 中输入的内容为“1111”,单击“翻译”按钮后,列表框 List1 中显示的内容是 。?
答案 (1)B (2)①b1*2+b2 ②i=i+4 (3)北 3
解析 (1)设置控件的属性,基本格式为:对象名.属性名=属性值。
(2)①根据题意,4位一组,前两位是方向,后两位是距离,b1是第3位,b2是第4位,将后两位转换成十进制值方法为按权相加法:b1*2+b2。②4位一组,本组起点i,下一组起点i+4。
(3)“1111”的前两位是“11”,根据代码,是代表方向“北”。后两位“11”转换成十进制是3。
2.(2016浙江10月选考,14,5分)编写“加法练习题生成器”程序,实现如下功能:在文本框Text1中输入题数n,单击“生成”按钮Command1.在列表框List1中显示n个两数之和小于100的加法练习题,程序运行界面如图a所示。
/
(1)在设计程序界面时,应使用图b所示“控件工具箱”中的 (填写相应编号)添加“生成”按钮。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim n As Integer,i As Integer,a As Integer,b As Integer
Randomize
n=Val(Text1.text)
i= ① ?
Do While i<=n
a=Int(Rnd*100)
b=Int(Rnd*100)
If ② Then?
List1.AddItem“(“+Str(i)+”)”+Str(a)+“+”+Str(b)+“=”
i=i+1
End If
Loop
End Sub
(3)运行该程序,在文本框中输入5,单击“生成”按钮后,对语句“a=Int(Rnd*100)”执行次数的描述,最合理的是 (单选,填字母:A.执行次数等于在5/B.执行次数大于等于5/C.执行次数小于等于5)。?
答案 (1)3
(2)①1 ②a+b<100或其他等价表达式
(3)B
解析 本题主要考查VB的综合应用。
(1)本小题考查如何选择控件创建对象。这里使用的是命令按钮CommandButton。
(2)本小题考查如何利用循环语句实现枚举算法。循环变量i的初值为1,终值为n。枚举算法要求将每一个可能的解经过检验后确认是不是真正的解,此处的检验条件为a,b两数之和小于100,转换成VB表达式为a+b<100。
(3)本小题考查对循环结构的程序执行过程的理解。当文本框中输入5时,即要求程序完成的任务是:采用枚举算法,从若干个a和b的组合中找出5组,使其满足a+b<100条件。故随机生成的a,b的个数必须大于等于5。即对于枚举算法而言,
其列举的可能解的数量一定是大于等于其真正解的数量。
