无优先级运算问题.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.15M 资料格式：doc 举报版权申诉

第1页 / 共10页

qq_33569706-9384153-无优先级运算问题.doc.pdf-第2页.png

第2页 / 共10页

qq_33569706-9384153-无优先级运算问题.doc.pdf-第3页.png

第3页 / 共10页

qq_33569706-9384153-无优先级运算问题.doc.pdf-第4页.png

第4页 / 共10页

qq_33569706-9384153-无优先级运算问题.doc.pdf-第5页.png

第5页 / 共10页

qq_33569706-9384153-无优先级运算问题.doc.pdf-第6页.png

第6页 / 共10页

qq_33569706-9384153-无优先级运算问题.doc.pdf-第7页.png

第7页 / 共10页

qq_33569706-9384153-无优先级运算问题.doc.pdf-第8页.png

第8页 / 共10页

附录源程序清单

1.实验目的对于给定的 n 个正整数，设计一个优先队列式分支限界法用最少的无优先级运算次数产生整数 m 用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。在 Windows 环境下使用 C/C++语言编程实现算法。记录运行结果，包括输入数据，问题解答及运行时间。分析算法最坏情况下时间复杂度和空间复杂度。 2.1 问题描述 2.实验内容给定 n 个正整数和 4 个运算符+，-，*，/，且运算符无优先级，如 2+3×5=25。对于任意给定的整数 m，试设计一个算法，用以上给出的 n 个数和 4 个运算符，产生整数 m，且用的运算次数最少。给出的 n 个数中每个数最多只能用 1 次，但每种运算符可以任意使用 2.2 算法设计对于给定的 n 个正整数，设计一个算法，用最少的无优先级运算次数产生整数 m。 3. 数据输入由文件 input.txt 给出输入数据。第一行有两个正整数 n 和 m。第二行是给定的用于运算的 n 个正整数。 4. 结果输出将计算出的产生整数的 m 的最少无优先级运算次数以及最优无先级运算表达式输出到文件 output.txt。

输入文件示例输出文件示例 Input.txt 5 25 output.txt 2 5 2 3 6 7 2 + 3 * 5 3.实验原理 3.1 分支限界法分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3.2 分支限界法的设计思路设求解最大化问题，解向量为 X=(x1,…,xn)，xi 的取值范围为 Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界 [down, up]，然后从根结点出发，扩展根结点的 r1 个孩子结点，从而构成分量 x1 的 r1 种可能的取值方式。对这 r1 个孩子结点分别估算可能的目标函数 bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于 bound(x1)，即：bound(x1)≥bound(x1,x2) ≥…≥ bound(x1,…,xn)若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表 PT 中。再取 PT 表中目标函数极大值结点作为扩展的根结点，重复上述。直到一个叶子结点时的可行解 X=(x1,…,xn)，及目标函数值 bound(x1,…,xn)。 3.3 实验设备及环境

3.3.1 电脑配置 3.3.2 开发环境 4 实验结果与分析 4.1 实验数据及结果

4.2 实验分析及结论针对该实验我做了仔细分析，刚看到这个题目，不知所云，后来分析后才知道，给定 n 个正整数和 4 个运算符+，-，*，/，且运算符无优先级，如 2+3×5=25。对于任意给定的整数 m，试设计一个算法，用以上给出的 n 个数和 4 个运算符，产生整数 m，且用的运算次数最少。给出的 n 个数中每个数最多只能用 1 次，但每种运算符可以任意使用。 4.3 自我评价及心得体会分析无优先级算法问题时候一开始有点无从下手，经过我查资料以后，再加上自己的分析和见解，以及老师的帮助，最终得出了答案，让我明白了只要自己从分利用自己掌握的技术和周边的坏境比如我们学校的老师，网络资源等，大多问题都可以解决的。 5 参考文献 [1] 王晓东．算法设计与分析（第三版）．北京：清华大学出版社，2014.3 [2] 王行言. Java 语言与面向对象程序设计. 北京：清华大学出版社，2013.1 [3] 孙雄勇. Visual C++ 6.0 实用教程. 北京：中国铁道出版社，2004 [4] 谭浩强. C++面向对象程序设计. 北京：清华大学出版社，2006

附录源程序清单 #include using namespace std; int k; class readin { friend int nreadin(int n,int m); private:

bool found(); //found 判断是否找到解 bool search(int t); int n,m,x; int * a; 正整数的存放位置 int* num; int* operate; int* flag; char* ptr; }; //用迭代加深的回溯法 //给定的用于运算 n 个 //存放运算的产生整数 m //存储结果中的运符 bool readin::search(int depth) //depth:递归深度 { if(depth>k) { if(found()) return true; //判断结点是否满足件，即是否找到解 else return false; } else

for(int i=0;i

case 0:x+=num[i+1];ptr[i]='+';break; case 1:x-=num[i+1];ptr[i]='-';break; case 2:x*=num[i+1];ptr[i]='*';break; case 3:x/=num[i+1];ptr[i]='/';break; } } return(x==m); } //读入初始数据 int nreadin(int n,int m) { readin X; int* a=new int[n]; int* num=new int[n]; int* operate=new int[n]; int* flag=new int[n]; char* ptr=new char[n]; X.n=n; X.m=m; X.a=a; X.operate=operate; X.flag=flag;

分享到：

赞收藏

资料库

无优先级运算问题.doc

相关推荐

课程资源

热门标签

最新资料