学进去

小娜想在高三暑假完成一次毕业旅行。她了解到旅行社对10个热门旅游城市进行了编号，每个城市有相应的名胜值，到达某个城市即可获得该城市的名胜值。旅行社还提供各城市之间的航线信息，她发现航线都是从编号小的城市到编号大的城市。已知小娜旅行会从1号城市出发，终点站（家）在11号城市，她想自己设计一条名胜值最大的游路线，为此小娜设计了一个算法来制定路线。设计思路是：
1）依次计算每个城市的路线名胜值。设到达某城市的n条路径的中，每条路径上的城市名胜值之和分别为{x₁，x₂…x_n}，该集合中的最大值xmax即为该城市的路线名胜值。路线名胜值的具体算法：该城市的名胜值加上能直接到达该城市的所有城市中最大的路线名胜值，同时记录下该前一城市的编号。
如图a所示，1、2、3、4、5、6号城市名胜值依次为5、6、5、4、9、8。
1号城市可到达2、3、4号城市，2、3号城市均可到达6号城市，则2号城市的路线名胜值为自身名胜值6加上1号城市的名胜值5，等于11；同理，3号城市的路线名胜值为5+5=10。6号城市路线名胜值为自身名胜值8加上2号城市的路线名胜值11，等于19，途经城市为1、2、6，而非途径1、3、6号城市。
2）依次遍历所有城市的路线名胜值，在能到达11号城市的城市中，存储最大路线名胜值的城市编号。若最大路线名胜值有并列，则这些城市编号全部存储。
3）输出最大路线名胜值对应的最佳旅游路线，若有多条，则全部输出。

图a

图b

程序界面如图a所示。在Text l中输入航线信息，如“3→6”，表示可以从3号城市到6号城市。
（1）若1~10号城市的名胜值分别为5，6，5，7，4，3，7，5，6，8，航线如图a所示，则最佳旅游路线为：1、________、11号城市（填城市编号）。
（2）实现上述功能的VB程序如下，请在划线处填入合适的代码。
Const n=10
Dim map（1 To n * n）As Boolean
Dim isBack（1 To n）As Boolean                    '表示1~n号城市是否有航线可以回到11号城市（家）。其值为True则表示可回家
Dim cityPoint（1 To n）As Integer
Dim pathPoints（1 To n）As Integer                  '到达1～n号城市时的路线名胜值
Dim maxPoints As Integer                                 '最终路线方案的最大名胜值
Private Sub Form_Load()

'初始化各城市名胜值，并在List l中输出，代码略。

'从Text 1中读取航线信息，存储到map数组，isBack数组，代码略。

'map（1）-map（10）分别表示1号城市到1~10号城市的航线情况。

'map（11）~map（20）分别表示2号城市到1~10号城市的航线情况，以此类推。

'16题图a中的航线信息在map数组中的表示如第16题图b所示。T表示值为True，空表示值为False。

'可知map（2）、map（3）、map（4）、map（15）……等元素的值为True

End Sub

Private Sub Command1_Click()

Dim endCity（1To n）As Integer

Dim prev（1 To n）As Integer

Dim tour As String

Dim cnt As Integer

For i=2 To n   '计算每个城市的路线名胜值

For j=1Toi-1

tmp=_____

If map（tmp）And pathPoints（i）<pathPoints（j）+cityPoint（i）Then

pathPoints（i）=pathPoints（j）+cityPoint（i）

prev（i）=j

End If

Next j

Next i

cnt=1：maxPoints=0       '找出符合条件的路线

For i=1To n

If isBack（i）And pathPoints（i）>maxPoints Then

maxPoints=pathPoints（i）

cnt=1

Elself isBack（i）And pathPoints（i）=maxPoints Then

cnt=cnt+1

End If

_________

Next i

ct=0：flag=False   '输出路线

maxPoints=maxPoints +cityPoint（1）

For i=1 To cnt

city=endCity（i）

tour=""

Do While city<>0

tour=Str（city）+"→"+tour

ct=city

________

Loop

tour="路线"+CStr（i）+"："+tour+"11，路线名胜值："+CStr（maxPoints）

If ct=1Then List2.Addltem tour:flag=True

Next i

If Not flag Then List2.Addltem"无符合要求的线路”

End Sub