无优先级问题

皖西学院信息工程系 实 验 报 告 姓名＿＿王礼＿ 学号 ******** 院系＿信息工程系 专业 计算机科学与技术 年级 2 0 0 7 级 班级＿ 0 7 0 2 班 ＿ 小组实验任务分工＿ 独立完成 实验时间 2 0 1 0 年＿9 ＿月 2 0 ＿日 实验名称 无优先级运算问题 指导老师及职称 苏守宝 教授 皖西学院信息工程系 实验课程：算法分析与设计 实验名称：无优先级运算问题 （综设型实验） 第一部分 实验内容 1 ．实验目标 对于给定的n 个正整数，设计一个优先队列式分支限界法用最少的无优先级运算次数产生整数m 。 2 . 实验任务 （1）从所给定的题目中选择一题，使用分支限界法求解之。 （2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。 （3）在 Window s 环境下使用C/C++语言编程实现算法。 （4）记录运行结果，包括输入数据，问题解答及运行时间。 （5）分析算法最坏情况下时间复杂度和空间复杂度。 （6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的 建议。 3 . 实验设备及环境 PC；C/C++等编程语言。 4 . 实验主要步骤 (1) 根据实验目标，明确实验的具体任务； (2) 设计求解问题的算法，并编写程序实现算法； (3) 设计实验数据并运行程序、记录运行的结果； (4) 分析算法时空性能； (5) 实验后的心得体会。 第二部分 问题及算法 1. 问题描述：给定 n 个正整数和 4 个运算符+，-，*，/，且运算符无优先级，如 2+3×5=25。对于任意给定的整数m，试设计一个算法，用以上给出的n 个数和 4 个运算符，产生整数m，且用的运算次数最少。给出的n 个数中每个数最多只能用 1 次，但每种运算符可以任意使用 2. 算法设计：对于给定的n个正整数，设计一个算法，用最少的无优先级运算次数产生整数m。 3. 数据输入 由文件 input.txt 给出输入数据。第一行有两个正整数n 和 m。第二行是给定的用于运算的n 个正整数。 4. 结果输出 将计算出的产生整数的m 的最少无优先级运算次数以及最优无先级运算表达式输出到文件 output.txt。 输入文件示例 输出文件示例 Input.txt output.txt 5 25 2 5 2 3 6 7 2 + 3 * 5 第三部分 实验结果与分析 1. 实验数据及结果 2 . 实验分析及结论 针对该实验我做了仔细分析，刚看到这个题目，不知所云，后来分析后才知道，给定n 个正整数和4 个运算符+，-，*，/，且运算...