数据结构课程设计报告：在表达式“123456789=100”中左边的适当位置插入运算符“+”或“-”,以使等式成立.doc

课程设计报告设计题：在表达式“123456789=100”中的左边的适当位置插入运算符“+”或“-”，以使等式成立。例如123+45-67+8-9=100.问题分析：1、 输出表达式时应作为字符串输出，方便得到结果，因此应该定义一个函数实现把int变量转化为string型。（用string类是为了便于表达，即可直接用cout，+等。2、 123456789中间有8个“空”，每个“空”有“+”“-”“空格”三种选择，故一共有38种可能。又需要所得到的表达式满足结果为100，即类似于有约束条件的进行深度优先遍历。设计所用软件及运行环境： Visual C+6.0 Windows 7操作系统算法设计概要：1、 要利用递归。递归出口即满足表达式的运算结果为100并且完成了一遍从1到9的过程，满足条件则输出结果，并且记录满足的记录个数。否则，对三种可能情况写对应的三个递归函数，一直到满足条件为止。2、 输出函数要注意消除字符串数组中无用字符。程序运行结果：运行结果一共171个。（因屏幕有限故截取前后两部分图片） 程序调试：1、 最开始出来的程序是这个样子。即表达式前边出现了一些无用的字符。而根据我自己的分析应该是使用递归函数时可能往字符串数组里存入了一些无用的字符。所以应该在每次输出表达式的时候都要删掉那些无用的字符。2、 关于三个递归函数的顺序。调整三个函数的顺序总的结果不会改变，但是表达式出现的位置会发生变化。这个源于递归尤其是嵌套的递归实现的内部过程是一种折线型的。递归可以避免大量重复的运算，但是也要注意其顺序问题。幸而这道题里面不用考虑表达式的顺序。观察前面25个记录。 合并、减法、加法 加法、合并、减法 减法、加法、合并设计总结与体会：在学习数据结构这门课的时候一直不知道学的东西应该怎么使用，比如链表、树、图等存储结构，但是通过这次的课程设计，我终于对它们有所体会了。收获最深的一是关于递归的使用，二是C+程序设计关于string类的使用。刚拿到题目的时候觉得跟做24点很相似，分析了一下又有不同。除开24点的规则跟这道题的规则不一样外，比较重要的一点就是24点的四个数的位置可以变换，而这道题里的9个数则不可以。之前看过一些24点的相关算法，有暴力穷举这样最直接却也最简单的算法。所以我也自然而然地想采用这种算法。况且跟24点的四种运算比起来，38=6561种可能并不算太多。但是事实证明这并不是个好点子，至少对我的脑子来说，光考虑设置怎样的函数将这些可能都包含进来就够令我头疼，还莫谈它们还有顺序。遇到瓶颈的时候在网上查资料看到有用递归的思想做的算法，顿时有种豁然开朗的感觉。照这样的想法做下来，程序也相当简单。在程序编译运行的过程中也遇到一些问题，尤其是关于string类的相关运用，比如string属于C+标准库，不能使用.h的C头文件，而必须使用命名空间std来声明。总的来说通过这次课程设计弥补了之前数据结构课程学习中的缺陷，让我受益良多。附录：源程序#include#includeusing namespace std;int total=1;void print(string str)couttotal+: ;int i=0,length=str.length();while(ilength&stri!=1) i+;/去掉前面无用字符 for(;ilength;i+) coutstri;cout=1000)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&cur10)/搜索到最后一个数9print(str);/输出符合条件的表达式else if(cur10) return;else function(cur+1,pre*10+cur,str,result);/与前一个数合并function(cur+1,cur,str+atos(pre),result+pre);/与前一个数做加法,str+atos(pre)表示表达式。function