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