题型:综合题 题类:常考题 难易度:困难
【bj】高中信息技术综合库——枚举算法及程序实现1
有一种火柴棒游戏,将火柴棒摆成形如“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(1) |
a(2) |
a(3) |
a(4) |
a(5) |
a(6) |
a(7) |
a(8) |
a(9) |
9 |
6 |
8 |
5 |
3 |
4 |
7 |
2 |
1 |
现有一算法把一个无序数组改造成大根堆。例如:我们在上图的大根堆中再增加一个值为8的新元素,如下图所示。
数组存储为:
a(2) |
a(3) |
a(4) |
a(5) |
a(6) |
a(7) |
a(8) |
a(9) |
a(10) |
6 |
8 |
5 |
3 |
4 |
7 |
2 |
1 |
8 |
具体操作方法如下:
第一步:因为a(10)大于它的双亲结点a(5),故需交换a(10)和a(5)的值;
数组存储为:
第二步:因为a(5)大于它的双亲结点a(2),故需交换a(5)和a(2)(t)值;
数组存储为:
a(1) |
a(2) |
a(3) |
a(4) |
a(5) |
a(6) |
a(7) |
a(8) |
a(9) |
a(10) |
9 |
8 |
8 |
5 |
6 |
4 |
7 |
2 |
1 |
3 |
第3步:因为a(2)不大于它的双亲结点a(1),故无需做交换操作。此时新元素已经放到了正确的位置,新的大根堆构造完成,上移行动结束。
试题篮