信号放大器

1) 问题描述 天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。 2) 基本要求 (1) 建立模型，设计数据结构； (2) 设计算法完成放大器的放置； (3) 分析算法的时间复杂度。 3) 设计思想 为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。