某ETC(Electronic Toll Collection,不停车收费)系统在高速公路沿线的特定位置上设置一个横跨道路上空的龙门架(Toll gantry),龙门架下包括6条车道(Traffic lanes),每条车道上安装有雷达传感器(Radar sensor)、无线传输器(Radio transceiver)和数码相机(Digital Camera)等用于不停车收费的设备,以完成正常行驶速度下的收费工作。该系统的基本工作过程如下:
(1)每辆汽车上安装有车载器,驾驶员(Driver)将一张具有唯一识别码的磁卡插入车载器中。磁卡中还包含有驾驶员账户的当前信用记录。
(2)当汽车通过某条车道时,不停车收费设备识别车载器内的特有编码,判断车型,将收集到的相关信息发送到该路段所属的区域系统(Regional center)中,计算通行费用,创建收费交易(Transaction),从驾驶员的专用账户中扣除通行费用。如果驾驶员账户透支,则记录透支账户交易信息。区域系统再将交易后的账户信息发送到维护驾驶员账户信息的中心系统(Central system)。
(3)车载器中的磁卡可以使用邮局的付款机进行充值。充值信息会传送至中心系统,以更新驾驶员账户的余额。
(4)当没有安装车载器或者车载器发生故障的车辆通过车道时,车道上的数码相机将对车辆进行拍照,并将车辆照片及拍摄时间发送到区域系统,记录失败的交易信息;并将该交易信息发送到中心系统。
(5)区域系统会获取不停车收费设备所记录的交通事件(Traffic events);交通广播电台(Traffic advice center)根据这些交通事件进行路况分析并播报路况。
现采用面向对象方法对上述系统进行分析与设计,得到如表3-1所示的用例列表以及如图3-1所示的用例图和图3-2所示的分析类图。
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为整英寸。已知价格表p,其中pi(i=l,2,...,m)表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。
求解此切割方案的算法基本思想如下:
假设长钢条的长度为n英寸,最佳切割方案的最左边切割段长度为i英寸,则继续求解剩余长度为n-i英寸钢条的最佳切割方案。考虑所有可能的i,得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下:
算法采用的设计策略是动态规划。
自顶向下方法的时间复杂度为O(2n)。
自底向上方法的时间复杂度为O(n2)。