趣味数学编程题解之公车座位巧安排
IT商界
本期的数学题是一个很实际的例子，和我们日常生活中常坐的大巴相联系。我们通过N-S图来讲解，在学习的过程中重温一下用N-S图解决问题的过程。
题目：公共汽车问题
老王是公交公司的一名老司机。一天，小李将自己的车段上的情况描述了一下。具体情况如下：公共汽车站包括起始站和终点站共15站。有一辆车，除终点站外，每一站上车的乘客中都恰好有一位到以后的每一站下车，为了使每一位乘客都有座位，问这辆公车至少要有多少个座位？这班车至少售出多少张票？
这下可难坏了老王，能帮老王解出来吗？
N-S图只有三种简单的结构形式，在《车牌号码》中我们有过详细的说明，下面我们还是用N-S图来公析公车问题。
用N-S图分析问题
(1)重点分析输入和输出
问题可分成三大部分，输入、处理和输入，先重点看输入和输出。输出最简单，就是题目中要求的两个数值：座位数和票数。
我们可以先手工将题目来处理一下，找出站点号和上下车人数的情况：
站号i 上车人数s(i) 下车人数x(i)
1 14 0
2 13 1
3 12 2
4 11 3
15 0 14
通过手工执行，输入数据变成了各站上车人数和下车人数。为了表达方便，我们使用了数组s(i)和x(i)。数据输入中的问题有两个(如图1a示)即怎样给各站上车s(i)及下车的人数x(i)放入上下车时的人数，每一个数组可通过一个循环来完成。因为其循环次数是相同的，可将两个合到一个循环中，通过对上面手工分析和观察，可得出图1b所示的图。
(2)处理过程分析
因为本题中目标有两个，即座位数Z和票数T，我们可一个一个进行求解。
两个问题中求票数T较易解决，上车车票应该等于上车或者是下车的总人数，所以我们只要把握二者中的一项，这个问题就解决了。该问题事实上就是一个求和(如图2)。本题中我们是通过计算所有上车的人数来求总人数也即车票数。
求座位数Z稍微复杂一点。我们通过手工处理不难得出Z=车上人数最多时的人数，这和题目中要求每个人都有座位是一致的。我们进一步可将该问题分成两部分(如图3)。现在问题变成了先求解3.1在各站时车上的人数，再求3.2这些人数中的最大值了。为了便于求解，就作了数组R(i)。
通过对在各站时车上人数的手工分析，我们可得到图4，这样，我们只用一个循环就可将问题解决。
前面已经有了在各站时车上的人数，座位数也即车上人数最多时的人数，也就变成了求数组R(1)-R(15)中最大的数了(如图5)。
找到最大的数，将其值给了Z，至此，该题分析完成。
(3)将各部分分解后还要按我们在各个图中所编的代号将它们组合起来，把某些结构相同的部分重新组合，便得出了我们解决问题的总N-S图(如图7)。
语言、界面、源程序
(1)语言
程序中通过Virual BASIC6.0(以下简称VB6.0)语言来实现。
(2)界面
我们要设计成的界面很简单(如图8)。进入VB6.0，建立一标准EXE工程，caption设为“公车问题”，并加入两个命令按钮cmdCalcu和cmdexit，caption改为“计算”和“退出”，输出的结果放在两个文本框txtChair和 txtTarket中。然后再放入两个标签用于说明，caption为“座位数”和“票数”，位置和上面两文本框一一对应。一切OK。我们将主要代码加给cmdcalcu_Click()即计算按钮的单击事件，将来运行时，我们只要用鼠标单击一下按钮，程序就执行了，结果在文本框中输出。
(3)据N-S图写源程序
输出时要和我们编程语言中所用的控件或语句密切相关。在本题中，我们使用了两个文本框控件输出，输出语句也就相应成了：
TxtChair.Text = Str(z)
TxtTarket.Text = Str(t)
上面正是输出部分的代码。
源程序如下：
Dim s(1 To 15) As Integer '各站最少上车人数
Dim x(1 To 15) As Integer '最少下车人数
Dim R(1 To 15) As Integer '车上乘客数
Dim t, z As Integer
Private Sub CmdCalcu_Click() '计算按钮
Dim i, k As Integer
'①输入数据部分
For i = 0 To 14
s(i + 1) = 14 - i
x(i + 1) = i
Next i
'②处理
'②处理的Ⅰ和Ⅱ合并后
t = 0
k = 0
For i = 1 To 15
k = k + s(i) - x(i)
t = t + s(i)
R(i) = k
Next i
'②处理的Ⅲ
z = R(1)
For i = 2 To 15
If z < R(i) Then
z = R(i)
End If
Next i
'③输出
TxtChair.Text = Str(z)
TxtTarket.Text = Str(t)
End Sub
Private Sub CmdExit_Click() '退出按钮
Unload Me
End Sub
(以上程序在VB6.0、WIN98下调试通过)
编程小结
答案出来了，座位数56，票数105。
总结一下，使用N-S图分析问题时请注意如下几点：
1.重视输入输出(原材料和目标)
这是问题搞好的前提，编程之前必须先弄清原题的条件和所求的结果，如果没有这两项，很难想象我们以后的工作如何下手。
2.找出重点问题，各个击破，整体把握，重点思考
从本题中一步步地解题中你应该不难体会这一点。在每一步中，最重要的是我们都会出现一个重点问题，难点也就在其中，将它解决了，阻碍编程前进的绊脚石也就踢开了。