存档

文章标签 ‘数字序列和为0’

再谈数字序列和为0

2013年5月8日 4 条评论

---

之前研究过一道微策略的笔试题-数字序列和为零,当时采用DFS做的,深感别扭,后来在Tutu_Lux的帮助下,得到一个不错的方案,思路简单,说白了就是暴搜,但实现巧妙,代码灰常漂亮。感谢Tutu_Lux

先说一下大致思路,然后贴代码,之后分析代码中的各个函数,实现充分展现了Tutu_Lux扎实的基本功和灵动的脑瓜子,哈,:-) 。

思路:

  1. 由于N是从3至9的范围,解决方案就是针对每个N的取值,先计算三个分隔符“_ + -”填入序列1-N的所有可能组合的情况总数
  2. 设置所有情况的组合序列(采用3进制的思想,即set函数)
  3. 对每种组合计算表达式值,如果为0则输出(利用栈&状态机,calculate函数)

代码如下:

阅读全文...

微策略笔试题一道:数字序列和为0

2013年3月5日 10 条评论

---

这道深搜的题目写的我心情好别扭,代码也感觉别扭。希望路过的爱动手的牛牛们指导,不管是代码还是思路方面的建议都行;/握手

题目:序列123...N,N介于3和9之间,在其中加入+、-或者空格,使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问,如何获得所有组合?

我代码的思路就是深搜,处理空格时复杂一些,具体参数见注释。

阅读全文...