第9节 环问题
模拟演练
1.某监狱人满为患,由于牢房太小,而囚犯太多,大家只能站着睡觉。因此囚犯们只好采取抓阄的策略来改善自身的生存环境:n个囚犯(n<=50)围成一圈,按顺序从1到n编好号。从第1个人开始报数,报到3的人自杀,下一个人从1开始报数,报到3的人自杀。如此下去,直到留下最后一个人。请按退出顺序输出自杀的人的编号。程序运行时,单击“抓阄”按钮,结果显示在列表框List1中,程序运行界面如图所示。
/
实现上述功能的 VB 程序如下,请回答下列问题。
(1)当总人数为 7 时,对应的自杀序列编号为 。?
(2)请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim i As Integer, n As Integer
Dim num As Integer, t As Integer
Dim a(1 To 50) As Boolean
List1.Clear
n = Val(Text1.Text)
For i = 1 To n
a(i) = True
Next i
t = n
Do While ① ?
For i = 1 To n
If a(i) Then
② ?
End If
If num = 3 Then
a(i) = False
t = t - 1
③ ?
List1.AddItem Str(i)
End If
Next i
Loop
End Sub
答案 (1)3、6、2、7、5、1
(2)①t>1 ②num = num+1 ③num = 0
解析 本题综合考查算法及其程序实现(约瑟夫问题)。(1)根据规则可以推断,当人数为7时,其自杀的编号序列是3、6、2、7、5、1。(2)①根据题意和程序代码可知,变量t存储剩余人数,因此最后要剩下一人,答案为t>1。②根据“从1到3报数”,变量num用于保存报数序号,知本处的代码是num=num+1。③由于编号需要按照“1、2、3”的规律周而复始地循环,因此当num=3时,num需要清零,所以答案是num=0。
2.字符环上的最长公共字符串。将字符串首尾相接后可以得到一个环,图1和图2分别是由字符串“ABCUVKLM”和“MADJKLUVKL”首尾相接后得到的环。在图1和图2所示的两个环中,最长的公共字符串为“UVKLMA”(图中带背景圆圈表示)。
/
编写VB程序,实现如下功能:在文本框Text1和Text2中分别输入一个字符串(仅由大写字母构成,每个字符串长度不超过100),单击命令按钮Command1后,在标签Label3中输出两个字符串构成的环的最长公共字符串长度(字符串在环中必须连续)。程序运行效果如图所示。
/
实现上述功能的VB程序如下,请回答下列问题:
(1)根据题意描述,字符串“BCEFGK”和“GKBLMCKEF”的最长公共字符串长度为 。?
(2)请在划线处填入合适的代码。
Function getmin(a As Integer, b As Integer) ’获取两个整数的较小者
If a < b Then getmin = a Else getmin = b
End Function
Private Sub Command1_Click()
Dim s1 As String, s2 As String, i As Integer, j As Integer, x As Integer, y As Integer
Dim cnt As Integer, ans As Integer, len1 As Integer, len2 As Integer
s1=Text1.Text
s2=Text2.Text
len1=Len(s1)
len2=Len(s2)
minlen = ① ’minlen中保存s1和s2中较短字符串的长度?
ans = 0
For i = 1 To len1
For j = 1 To len2
cnt = 0: x = i: y = j
Do While ② And cnt < minlen?
cnt = cnt + 1
x = x Mod len1 + 1
y = y Mod len2 + 1
Loop
If ③ Then ans = cnt?
Next j
Next i
Label3. Caption = Str(ans)
End Sub
答案 (1)5 (2)① getmin(len1, len2) ② Mid(s1,x,1) =Mid(s2,y,1) ③ cnt > ans
解析 (1)字符串“BCEFGK” 和“GKBLMCKEF” 的最长公共字符串为“EFGKB” 。
(2)本题较难理解的是 Do While 循环体内的一段代码,程序分别用 x 和 y 记录 s1 和 s2 中正在比较的字符的位置,通过对字符串长度求余,巧妙地回到第一个字符的位置,实现了字符环的功能。注意:因为字符串的下标从 1 开始,故不能写作 x = (x + 1) Mod len1。
3.平面上有N(3≤N≤100)个房间围成一圈,按顺时针方向分别编号为1…N,相邻的两个房间之间均有一扇门,第i个房间居住人数为a(i)。初始时选择一个房间,将所有人都聚集在该房间,接着每个人都按顺时针方向走到相邻的房间,直至走到居住的房间。一个人每经过一扇门花费1能量,请确定初始房间,使得所有人花费的能量和最小。例如:N=5,a(1)=4,a(2)=7, a(3)=8, a(4)=6, a(5)=4。
最佳方案:初始时所有人聚集在2号房间,花费的能量和:7*0+8*1+6*2+4*3+4*4=48。为了解决这个问题,小明编写了一个VB程序。在窗体加载时,从数据库中读取N的值和编号为1到N的房间的居住人数,人数存储在数组a中。点击窗体上的按钮Command1,程序枚举每一种方案(不同的初始房间),计算该方案的能量和,在文本框Text1中输出最优方案的初始房间编号,在文本框Text2中输出最小能量和。
实现上述功能的VB代码如下,请在划线处填入合适代码。
Dim a(1 To 100) As Integer ’依次存储编号为1到100的房间的居住人数
Private Sub Form_Load()
’本过程从数据库中读取N的值和每个房间居住人数,存储在数组a中
’代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, w As Integer , k as Integer
Dim t As Long, ans As Long
k=0 : ans = 32767 ’ans初始化为最大的Integer数据
For i = 1 To n
t = 0
For j = 0 To n - 1
w= ① ?
If w = 0 Then w = n
t= ② ?
Next j
If t < ans Then
k= i
ans = t
End If
Next i
Text1.Text = Str (k) ’起始房间编号
Text2.Text = ③ ?
End Sub
答案 ①(i+j) Mod n ② t+a(w)*j ③Str(ans)
解析 ①变量i是选中的房间号,用枚举算法将所有的房间号都尝试一遍。变量j需要走的门的扇数是0扇到n-1扇。变量w是房间号,因此此处填w=(i+j) Mod n。②变量a(w)是w号房间的人数,变量t是能量和,因此此处填t=t+a(w)*j。将所有房间所需的能量加起来。③输出最小能量,在变量ans中。
课件4张PPT。
第9节 环问题环的问题,一般通过Mod运算来解决。
1.n个人围成一圈,编号分别是1~n,第1次走到1号,第2次走到2号,依次类 推,第m次走到哪号?有以下写法。教材研读 2.n个人围成一圈,编码分别是1~n,第1次走到1号,第2次走2步走到3 号,第3次走3步走到6号,依次类推,第m次走到哪号?
j=0
For i=1 to m
j=(j+i) mod n
if j=0 then j=n
next
3.30个人围成一圈,编码分别是1~30,从1号开始报数,报到4的人出列,请输出出列顺序。
