2013百度笔考试题（北京研发）
2013百度笔试题（北京研发）
今年百度的笔试题出来了。其中最后一题是：
有8个8，可以使用运算符（+，-，*，/）和括号组成一个表达式，使这个表达式的值为100。注意以下几点：
1，每两个8之间必须了运算符，不能出现88,888等这类的数。
2，优化结果：比如8*8+（8*8+8）/((8+8)/8)和+（8*8+8）/((8+8)/8)+8*8可以视为是等价的，只要保存一个就好。
3，写出算法原理和伪代码。
我想了一下。可能的方法：
1.穷举法，首先不考虑括号。但是运算符，就有4的7次方的可能了（16k的可能）。关键是要考虑括号。括号中又可能包括括号。这样一来。关于穷举括号的可能，有没有比较好的思路？
2.后推法：
设能使x个8等于sum的表达式为F(x,sum)。我们要求的则是能使8个8等于100的表达式的为F(8,100)。
F(8,100)= (1) 8+F(7,92)
(2) 8*F(7,12.5)
(3) F(7,800)/8
(4) F(7,108)-8
(5) 8/F(7,0.08)
(6) 8-F(7,-92)
这样下去一步一步推。这种算法与解决经典的难题：24点难题算法的思路是一样的。不过！24点难题中有一个很重要的结果，就是计算的临时结果必须也是整数！则上述中的8*F(7,12.5)，8/F(7,0.08)都不需要考虑。就是凭着这一点，才可以删除大量的不必要的可能分支。否则，这种后推的方法也与穷举法无异了。
但是如果没有临时结果必须是整数这个前提怎么办？？题目我是从网上搞到的。不知道有没有谁亲眼见过今年的题目。有没有临时结果必须是整数这个条件？
这就是我的想法。不过其实都挺麻烦的，而且最后还要结果进行优化。是不是还有其他的思路呢？个人水平有限，求各位大侠指导。
------解决方案--------------------
表达式生成树
------解决方案--------------------
编程之美上面的题目好吧,亲
今年百度的笔试题出来了。其中最后一题是：
有8个8，可以使用运算符（+，-，*，/）和括号组成一个表达式，使这个表达式的值为100。注意以下几点：
1，每两个8之间必须了运算符，不能出现88,888等这类的数。
2，优化结果：比如8*8+（8*8+8）/((8+8)/8)和+（8*8+8）/((8+8)/8)+8*8可以视为是等价的，只要保存一个就好。
3，写出算法原理和伪代码。
我想了一下。可能的方法：
1.穷举法，首先不考虑括号。但是运算符，就有4的7次方的可能了（16k的可能）。关键是要考虑括号。括号中又可能包括括号。这样一来。关于穷举括号的可能，有没有比较好的思路？
2.后推法：
设能使x个8等于sum的表达式为F(x,sum)。我们要求的则是能使8个8等于100的表达式的为F(8,100)。
F(8,100)= (1) 8+F(7,92)
(2) 8*F(7,12.5)
(3) F(7,800)/8
(4) F(7,108)-8
(5) 8/F(7,0.08)
(6) 8-F(7,-92)
这样下去一步一步推。这种算法与解决经典的难题：24点难题算法的思路是一样的。不过！24点难题中有一个很重要的结果，就是计算的临时结果必须也是整数！则上述中的8*F(7,12.5)，8/F(7,0.08)都不需要考虑。就是凭着这一点，才可以删除大量的不必要的可能分支。否则，这种后推的方法也与穷举法无异了。
但是如果没有临时结果必须是整数这个前提怎么办？？题目我是从网上搞到的。不知道有没有谁亲眼见过今年的题目。有没有临时结果必须是整数这个条件？
这就是我的想法。不过其实都挺麻烦的，而且最后还要结果进行优化。是不是还有其他的思路呢？个人水平有限，求各位大侠指导。
------解决方案--------------------
表达式生成树
------解决方案--------------------
编程之美上面的题目好吧,亲