1)将每个人看成是一个钩码,能挂在另一个挂钩底下,自己底下也能挂其他挂钩。
2)如果两个钩码在同一条钩码串上,则为亲戚(如2、3都能找到1)。
3)如果两个是亲戚但不在一串钩码上,则可将其中一串的最上面的钩码挂在另一串的下方。
例如从图a加框处的前三行数据可得到图b所示的钩码串1和钩码串2,从第四行数据可知9、5也为亲戚,则可将两串钩码合并,合并后3为2的顶端,5为3的顶端,其余数据以此类推。
根据算法思想,编写VB程序功能如下:程序初始化时给出6条亲戚关系显示在List1中,单击“理关系”按钮,在List2中显示每个人所在钩码的顶端编号。在Text1和Text2中分别输入两人的编号,单击“询问”按钮,输出两个人是否为亲戚关系。程序运行界面如图a所示。
Const n = 9 ‘总人数
Const m = 6 ‘已知的亲戚关系数
Dim a(1 To n) As String , b(1 To n) As String
Dim f(1 To n) As String ‘记录不同的亲戚钩码串成员,每条亲戚钩码串内互为亲戚
Dim k As Integer ‘亲戚钩码串的数目
Private Sub Form_Load()
‘初始化List1和List2,生成m条亲戚关系,每条亲戚关系的编号对应存储在数组a(i)和b(i) '中,在List1中输出a(i)和b(i),代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, x As Integer, y As Integer
f(1) = a(1) + b(1) ‘利用a(1)、b(1)生成第一条钩码串存储在f(1)中
k = 1 ‘k为钩码串编号
For i = 2 To m
x = root(a(i), 0): y = root(b(i), 0) ‘x为调用函数获取a(i)所在的钩码串编号
If x = 0 And y = 0 Then k = k + 1: ‘根据x与y分类讨论
If x <> 0 And y = 0 Then f(x) = f(x) + b(i)
If x = 0 And y <> 0 Then f(y) = f(y) + a(i)
If x <> y And x <> 0 And y <> 0 Then ‘x、y在不同钩码串则将两条钩码串合并
f(x) = f(x) + f(y): f(y) = f(k): k = k - 1
End If
Next i
For i = 1 To n ‘输出每个人所在钩码的顶端编号
x = root(CStr(i), 0): y = root(CStr(i), 1) ‘Cstr()函数用于去除字符前导空格
If x <> 0 Then
If y = Len(f(x)) Then List2.AddItem Str(i) + " " + CStr(i)
If y <> Len(f(x)) Then List2.AddItem Str(i) + " " +
End If
Next i
End Sub
'按钮Command2的功能为判断输入的两个人是否为亲戚关系,代码略
Function root(a As String, b As Integer) As Integer ‘参数a表示待查找目标,参数b
‘表示返回值类型,0表示返回目标所在钩码串编号,1表示返回目标在该钩码串中的位置
Dim m As Integer, n As Integer, i As Integer, j As Integer
m = 0: n = 0: i = k: j = 0
Do While i > 0
If a = Mid(f(i), Len(f(i)) - j, 1) Then m = i: n = Len(f(i)) - j: Exit Do
j = j + 1
If j = Len(f(i)) Then i = i - 1: j = 0
Loop
If Then root = m Else root = n
End Function