保安门无优先级问题

2021年1月5日发(作者：邢球痕)

皖西学院信息工程系

实 验 报 告




姓名＿＿王礼＿ 学号
院系＿信息工程系 专业 计算机科学与技术
年级 2007级 班级＿ 0702班 ＿
小组实验任务分工＿ 独立完成
实验时间 2010 年＿9＿月 20＿日
实验名称
无优先级运算问题

指导老师及职称 苏守宝 教授







1 11

皖西学院信息工程系

实验课程：算法分析与设计
实验名称：无优先级运算问题 （综设型实验）


第一部分 实验内容

1．实验目标
对于给定的n个正整数，设计一个优先队列式分支限界法用最少的无
优先级运算次数产生整数m 。

2. 实验任务

（1）从所给定的题目中选择一题，使用分支限界法求解之。
（2）用文字来描述你的算法思路，包括解空间、限界函数、算法主
要步骤等。
（3）在Windows环境下使用CC++语言编程实现算法。
（4）记录运行结果，包括输入数据，问题解答及运行时间。
（5）分析算法最坏情况下时间复杂度和空间复杂度。
（6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的
2 11
建议。

3. 实验设备及环境

PC；CC++等编程语言。

4. 实验主要步骤

(1) 根据实验目标，明确实验的具体任务；
(2) 设计求解问题的算法，并编写程序实现算法；
(3) 设计实验数据并运行程序、记录运行的结果；
(4) 分析算法时空性能；
(5) 实验后的心得体会。

第二部分 问题及算法

1. 问题描述：给定n 个正整数和4个运算符+，-，*，，且运算符无
优先级，如2+3×5=25。对于任意给定的整数m ，试设计一个算法，
用以上给出的n个数和4个运算符，产生整数m，且用的运算次数最
少。给 出的n个数中每个数最多只能用1次，但每种运算符可以任意
使用

3 11
2. 算法设计：对于给定的n个正整数，设计一个算法，用最少的无
优先级运算次数产生整数m。

3. 数据输入
由文件给出输入数据。第一行有两个正整数n和m。第二
行是给定的用于运算的n个正整数。

4. 结果输出
将计算出的产生整数的m的最少无优先级运算次数以及最优无先级
运算表达式输出到文件。
输入文件示例 输出文件示例

5 25 2
5 2 3 6 7 2 + 3 * 5

第三部分 实验结果与分析

1. 实验数据及结果
4 11


2. 实验分析及结论
针对该实验我做了仔细分析，刚看到这个题目 ，不知所云，后
来分析后才知道，给定n个正整数和4个运算符+，-，*，，且运算
符无优先 级，如2+3×5=25。对于任意给定的整数m，试设计一个算
法，用以上给出的n个数和4个运算符 ，产生整数m，且用的运算次
数最少。给出的n个数中每个数最多只能用1次，但每种运算符可以
任意使用。

第四部分 心得与展望

1. 自我评价及心得体会 < br>分析无优先级算法问题时候一开始有点无从下手，经过我查资料以
后，再加上自己的分析和见解， 以及老师的帮助，最终得出了答案，
5 11
让我明白了只要自己 从分利用自己掌握的技术和周边的坏境比如我
们学校的老师，网络资源等，大多问题都可以解决的。

2. 展望
对算法产生了浓厚的兴趣，打算以后可能会从事算法设计。

第五部分 附录
1. 源程序
#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; 给定的用于运算n个
正整数的存放位置
int* num; 存放运算的产生整数m
int* operate;
6 11

int* flag;
char* ptr; 存储结果中的运符
};
用迭代加深的回溯法
bool readin::search(int depth) depth:递归深度
{
if(depth>k)
{
if(found())
return true; 判断结点是否满足件，即是否
找到解
else
return false;
}
else
for(int i=0;i if(flag[i]==0)
{
num[depth]=a[i];
flag[i]=1;
for(int j=0;j<4;j++)
{
7 11
operate[depth]=j;
if(search(depth+1))
return true;
}
flag[i]=0;
}
return false;
}
bool readin::found()
{
int x=num[0];
for(int i=0;i {
switch (operate[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);
8 11
}
读入初始数据
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;
e=operate;
=flag;
=num;
=ptr;
cout<<给定的用于运算的n个正整数：
for(int i=0;i {
cin>>a[i];
flag[i]=0;
9 11

}
cout<<给定的运算结果 整数m：
for(k=0;k if((0))
{
cout<<计算的产生整数m的最少无优先级运算次数：

cout< cout<<计算的产生整数m的最少无优先级运表达式：

for(i=0;i<=k;i++)
{
cout< }
cout< return 0;
}
cout<<
return 0;
}
void main()
{
10 11
int n;
int m;
cout<<输入给定的用于运算的n个正整数和给定的运算结果整
数m：
cin>>n>>m;
nreadin(n,m);
system(
}
参考文献
1．
2．余祥宣 崔国华 邹海明.计算机算法基础[M]. 武汉：华中科技大学
出版社，2005-10

11 11