数据结构专业课程设计方案报告在表达式中左边的适当位置插入运算符或以使等式成立.docx

课程设计汇报
设计题：
在表示式“=100”中左边合适位置插入运算符“+”或“-”，以使等式成立。
比如123+45-67+8-9=100.
问题分析：
1、 输出表示式时应作为字符串输出，方便得到结果，所以应该定义一个函数实现把int变量转化为string型。（用string类是为了便于表示，即可直接用cout，+等。
2、 中间有8个“空”，每个“空”有“+”“-”“空格”三种选择，故一共有3^8种可能。又需要所得到表示式满足结果为100，即类似于有约束条件进行深度优先遍历。
设计所用软件及运行环境：
Visual C++6.0
Windows 7操作系统
算法设计概要：
1、 要利用递归。递归出口即满足表示式运算结果为100而且完成了一遍从1到9过程，满足条件则输出结果，而且统计满足统计个数。不然，对三种可能情况写对应三个递归函数，一直到满足条件为止。
2、 输出函数要注意消除字符串数组中无用字符。
程序运行结果：
运行结果一共171个。
（因屏幕有限故截取前后两部分图片）

程序调试：
1、 最开始出来程序是这个样子。即表示式前边出现了部分无用字符。而依据我自己分析应该是使用递归函数时可能往字符串数组里存入了部分无用字符。所以应该在每次输出表示式时候全部要删掉那些无用字符。

2、 相关三个递归函数次序。
调整三个函数次序总结果不会改变，不过表示式出现位置会发生改变。这个源于递归尤其是嵌套递归实现内部过程是一个折线型。递归能够避免大量反复运算，不过也要注意其次序问题。幸而这道题里面不用考虑表示式次序。
观察前面25个统计。
① 合并、减法、加法

② 加法、合并、减法

③ 减法、加法、合并

设计总结和体会：
在学习数据结构这门课时候一直不知道学东西应该怎么使用，比如链表、树、图等存放结构，不过经过这次课程设计，我最终对它们有所体会了。收获最深一是相关递归使用，二是C++程序设计相关string类使用。
刚拿到题目标时候认为跟做24点很相同，分析了一下又有不一样。除开24点规则跟这道题规则不一样外，比较关键一点就是24点四个数位置能够变换，而这道题里9个数则不能够。之前看过部分24点相关算法，有暴力穷举这么最直接却也最简单算法。所以我也自然而然地想采取这种算法。况且跟24点四种运算比起来，3^8=6561种可能并不算太多。
不过事实证实这并不是个好点子，最少对我脑子来说，光考虑设置怎样函数将这些可能全部包含进来就够令我头疼，还莫谈它们还有次序。碰到瓶颈时候在网上查资料看到有用递归思想做算法，立即有种豁然开朗感觉。照这么想法做下来，程序也相当简单。
在程序编译运行过程中也碰到部分问题，尤其是相关string类相关利用，比如string属于C++标准库，不能使用.hC头文件，而必需使用命名空间std来申明。
总来说经过这次课程设计填补了之前数据结构课程学习中缺点，让我受益良多。
附录：
源程序
#include<iostream>
#include<string>
using namespace std;
int total=1;
void print(string str)
{
cout<<total++<<": ";
int i=0,length=str.length();
while(i<length&&str[i]!='1') i++;//去掉前面无用字符
for(;i<length;i++) cout<<str[i];
cout<<"=100"<<endl;
}
string atos(int n)// 数字转换成字符函数
{
if(n==0) return "0";
string str="";
int N=;//1~9能组成最大数数量级
while(n/N==0) N=N/10;//确定n数量级
while(n>0){
str+=char('0'+n/N);//将n按位取出，转化为字符型
n=n%N;
N=N/10;
}
return str;
}
void function(int cur,int pre,string str,int result)
{
if(result==100&&cur>10)//搜索到最终一个数9
print(str);//输出符合条件表示式
else if(cur>10) return;
else{
function(cur+1,pre*10+cur,str,result);//和前一个数合并
function(cur+1,cur,str+"+"+atos(pre),result+pre);//和前一个数做加法,str+"+"+atos(pre)表示表示式。
function(cur+1,cur,str+"-"+atos(pre),result-pre);//和前一个数做减法，同上。
}
}
main()
{
function(0,0," ",0);
return 0;
}