小木棍课程设计报告.doc

小木棍课程设计报告.doc: .
小木棍课程设计报告
数据结构课程设计报告
一：题目
名称：小木棍
内容：有一堆数量为n的木棍。他们的长度和重量是已知的。这些棍子将以一个接一个 的形式被一台木工机床处理。木工机床为处理一根木棍所需要的准备时间称为装配时间。 装配时间与机器复位和转换工具及外形有关。装备时间服从以下几条规律：
(a) 处理第一根木棒的装配时间是1分钟
(b) 正确地处理好一根长度为1重量为w的木棍后，如果机器处理的下一根木棒的长 度r和重量w‘符合i<=r和w〈=w‘那么处理下一根木棒将不需要装配时间。否则将需要1 分钟的装配时间。
你的任务是找出处理一堆木棍所需的最小装配时间。例如，如果你有5根木棍，长度和 重量分别为(4, 9), (5, 2), (2,1), (3, 5),和(1, 4)。那么最小的装配时间将是2分钟, 当以这种顺序装配时:(1,4), (3, 5), (4, 9), (2, 1), (5, 2) „
要求：
(1) 输入：本题一共有T组数据。第一行有一个整数T,代表数据组数。每一组数据由 两行组成：第一行包含一个整数n, l<=n<=5000,代表木棍的数量；第二行包含2*n个正整 数11, wl, 12, w2, .... In, wn,每个数都不超过10000,代表每根木棍的长度和重量。 每两个数之间可能有一个或多个空格。
(2) 输出：输出每组数据的最小装配时间。
(3) 所设计的数据结构应尽可能节省存储空间。
(4) 程序的运行时间应尽可能少。
二：问题分析
根据题目要求，有n根木棍，每根木棍有不同的长度和重量。用一台机器来处理这些木 棍，当第i+1根木棍的长度〉=第i根木棍的长度并且第i+1根木棍的重量〉=第i根木棍 的重量时，机器处理木棍的时间加1,求出处理完n根木棍所需要的最少时间。输入数据 有T堆，要求分别输出机器分别处理这T堆木棍所需的最少时间。
基本思路:
刚开始想到了用树来处理问题，把木棍的长度和重量看成为树的左右孩子结点，但过程 过于麻烦。后来想到了用快速排序来处理即：按木棍的长度从小到大排序，当木棍长度相 等时，按重量小到大排序。然后依次选择比当前长度大并且重量也大的木棍（已经对木棍 进行排序，每次选择都是对后面影响最小的），对选过的木棍进行标记，这些木棒就是被 处理的木棒。一轮之后，启动时间+1,再对剩下的木棍进行选择，即可得到最优解。
（1）数据的输入:
输入
（2）数据的输出：
输出每堆木棍所需的最少处理时间三：数据结构的选择和概要设计
1、数据结构的选择：
该算法采用算法是贪心算法。
2、概要设计:
程序主要分为下列4个部分：
(1) •定义结构图存储木棍的信息
(2) .对木棍按长度和重量的升序进行排序
(3) .用贪心算法求有多少个序列个数
(4) .定义主函数
该程序包括以下函数
Main()//库函数
四、 算法思想
将大问题转变为小的问题解决，将复杂的问题转换为简单的问题解决。为了使用动态规 划算法，问题还必须具备最优子结构，即问题的最优解包含了子问题的最优解。在此