存档

文章标签 ‘三进制’

再谈数字序列和为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函数)

代码如下:

阅读全文...