无优先级问题.doc

皖西学院信息工程系实 验 报 告姓名王礼 学号 20072077 院系信息工程系 专业 计算机科学与技术年级 2007级 班级 0702班 小组实验任务分工 独立完成 实验时间 2010 年9月 20日实验名称 无优先级运算问题 指导老师及职称 苏守宝 教授 皖西学院信息工程系实验课程：算法分析与设计 实验名称：无优先级运算问题 （综设型实验）第一部分 实验内容1实验目标对于给定的n个正整数，设计一个优先队列式分支限界法用最少的无优先级运算次数产生整数m 。2. 实验任务（1）从所给定的题目中选择一题，使用分支限界法求解之。（2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。（3）在Windows环境下使用C/C+语言编程实现算法。（4）记录运行结果，包括输入数据，问题解答及运行时间。（5）分析算法最坏情况下时间复杂度和空间复杂度。（6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的建议。3. 实验设备及环境PC；C/C+等编程语言。4. 实验主要步骤(1) 根据实验目标，明确实验的具体任务；(2) 设计求解问题的算法，并编写程序实现算法；(3) 设计实验数据并运行程序、记录运行的结果；(4) 分析算法时空性能；(5) 实验后的心得体会。第二部分 问题及算法1. 问题描述：给定n个正整数和4个运算符+，-，*，/，且运算符无优先级，如2+35=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个运算符+，-，*，/，且运算符无优先级，如2+35=25。对于任意给定的整数m，试设计一个算法，用以上给出的n个数和4个运算符，产生整数m，且用的运算次数最少。给出的n个数中每个数最多只能用1次，但每种运算符可以任意使用。第四部分 心得与展望1. 自我评价及心得体会分析无优先级算法问题时候一开始有点无从下手，经过我查资料以后，再加上自己的分析和见解，以及老师的帮助，最终得出了答案，让我明白了只要自己 从分利用自己掌握的技术和周边的坏境比如我们学校的老师，网络资源等，大多问题都可以解决的。2. 展望对算法产生了浓厚的兴趣，打算以后可能会从事算法设计。第五部分 附录1. 源程序#includeusing namespace std;int k;class readinfriend int nreadin(int n,int m);private:bool found(); /found判断是否找到解bool search(int t);int n,m,x; int * a; /给定的用于运算n个正整数的存放位置int* num; /存放运算的产生整数mint* operate; int* flag; char* ptr; /存储结果中的运符;/用迭代加深的回溯法bool readin:search(int depth) /depth:递归深度if(depthk)if(found() return true; /判断结点是否满足件，即是否找到解elsereturn false;elsefor(int i=0;in;i+)if(flagi=0)numdepth=ai;flagi=1;for(int j=0;j4;j+)operatedepth=j;if(search(depth+1)return true;flagi=0;return false;bool readin:found()int x=num0;for(int i=0;ik;i+)switch (operatei)case 0:x+=numi+1;ptri=+;break;case 1:x-=numi+1;ptri=-;break;case 2:x*=numi+1;ptri=*;break;case 3:x/=numi+1;ptri=/;break;return(x=m);/读入初始数据int nreadin(int n,int m)readin X;int* a=new intn; int* num=new intn; int* operate=new intn; int* flag=new intn;char* ptr=new charn;X.n=n;X.m=m;X.a=a;X.operate=operate;X.flag=flag;X.num=num;X.ptr=ptr;cout给定的用于运算的n个正整数：endl;for(int i=0;iai;flagi=0;cout给定的运算结果 整数m：endl;for(k=0;kn;k+)if(X.search(0)cout计算的产生整数m的最少无优先级运算次数：endl; coutkendl; cout计算的产生整数m的最少无优先级运表达式：endl; for(i=0;i=k;i+)coutnumiptri;coutendl;return 0;coutNo Solution!endl;return 0;void main()int n; int m;cout输入给定的用于运算的n个正整数和给定的运算结果整数m：nm; nreadin(n,m); system(paus