题目来源:微策略2013年校园招聘笔试题
题目描述:

现在有一个序列123......N,其中N介于3和15之间,要求在序列之间加入+、-或者空格,使得该序列组成的数学表达式的运算结果为0。

输入:

输入可能包含多个测试样例。
对于每个测试案例,输入整数N(3<=N<=15),代表这个序列的长度。

输出:

对应每个测试案例,输出所有使得表达式结果为0的组合,当有多个组合时,按字典序进行排序输出。

样例输入:
3
6
样例输出:
1+2-3
1 2+3-4-5-6
提示:

1_2+3-4-5-6相当于12+3-4-5-6(‘_’代表空格)

思路:

  对于3<=n<=15,总共有3^n种情况,当n=15时,总共有14348907种情况,所以对于给定的n,我们都可以在1秒内穷举完。对于穷举,当然用dfs是最方便的,我写的代码基本是对所有的情况都遍历一遍,当然如果觉得效率还不行,可以加些适当的减枝。代码如下:

 #include <stdio.h>

 int n;
int op[]; void print_ans()
{
int i; for (i = ; i < n; i ++)
{
printf("%d", i);
if (op[i] == )
printf(" ");
else if (op[i] == )
printf("+");
else
printf("-");
}
printf("%d\n", i);
}
int is_ok()
{
int i, ans, temp; if (op[] == )
ans = ;
else
ans = ;
i = ;
while (i < n)
{
if (op[i] == )
{
temp = i;
while (i < n && op[i] == )
{
i ++;
if (i >= )
temp *= ;
temp = temp * + i;
}
ans += temp;
}
else if (op[i] == )
{
temp = ++i;
while (i < n && op[i] == )
{
i ++;
if (i >= )
temp *= ;
temp = temp * + i;
}
ans += temp;
}
else
{
temp = ++i;
while (i < n && op[i] == )
{
i ++;
if (i >= )
temp *= ;
temp = temp * + i;
}
ans -= temp;
}
}
return ans;
}
void dfs(int index)
{
if (index == n)
{
if (!is_ok())
print_ans();
return;
}
//空格
op[index] = ;
dfs(index + );
//加
op[index] = ;
dfs(index + );
//减
op[index] = ;
dfs(index + );
}
int main(void)
{
while (scanf("%d", &n) != EOF)
dfs();
return ;
}

  关键的代码是dfs函数,分别对空格,加,减进行穷举,op[index]存放了第index位置存放的是哪种情况(0表示空格,1表示加,2表示减),如果index为n,则说明得到了一种可能,函数is_ok就是用于判断当前的情况是否能使得表达式最终的结果为0,如果为0,则输出并返回,否则直接返回。

  is_ok函数是用于判断放在op数组中的表达式是否满足条件,计算表达式比较麻烦的是为空格的情况,由于空格可以首先出现,在“+”后面出现,在“-”后面出现,is_ok中的代码则依次处理这三种情况。还有就是如果空格后面是个2位数,空格前面组成的数要向左移动两位,如果是1位数,只用移动1位。

最新文章

  1. 【linux】free命令中cached和buffers的区别
  2. C#定义类型转化 及 格式化字符串
  3. 关系型数据之LinQ基本查询
  4. String字符串
  5. windows 说“我爱你”
  6. Week,Month, Year 日期区间辅助类
  7. 用户登录验证例题用的ajax
  8. So easy Webservice 6.使用EndPoint发布webservice服务
  9. hdu 3389 Game 博弈论
  10. Win7下Solr4.10.1和MySql的整合(索引与搜索)
  11. day23 框架之基础加强
  12. PHP验证码的制作教程
  13. 转:rabbitmq——用户管理
  14. mac下 改变了ssh连接的端口 git怎么修改
  15. Spring核心——Bean的定义与控制
  16. 企业级仓库harbor搭建
  17. 基于AC有限状态机的多模匹配算法
  18. Java知多少(6)第一个程序示例
  19. ionic 项目内部更新用到的插件,退出app插件
  20. Bata验收互评

热门文章

  1. iOS调试
  2. JavaScript - call(this)
  3. Kendo UI for ASP.NET MVC 的一些使用经验(转)
  4. python 字符串比较
  5. PySe-002-Py-简单示例及编码设定
  6. childNodes在IE与Firefox中的区别
  7. SpringMvc入门五----文件上传
  8. Hibernate4.x之映射关系--双向1-n
  9. Spring3 MVC Login Interceptor(Spring 拦截器)
  10. java第一章到第四章
  11. [置顶] android之Notification版本兼容性问题
  12. sqlloader外部表
  13. Java I/O---字符与字节转换流---FileReader&amp;FileWriter:
  14. 将 Shiro 作为应用的权限基础 三:基于注解实现的授权认证过程
  15. [LeetCode] Freedom Trail 自由之路
  16. SQL MIN() 函数
  17. 声明寄存器ROM
  18. js将时间戳格式化为HH:ii:ss的格式
  19. ARC 之内存转换
  20. X-009 FriendlyARM tiny4412 uboot移植之SD Card用起来Kernel boot起来