美团网笔试题

1. 利用stack计算整数表达式.
2. 硬币正面朝下, 第一次全部翻转, 第2次反转2的倍数(2,4,6,...), 第3次反转3的倍数(3,6,9...), 这样一直进行下去,操作100次, 问有多少正面朝上.

是1-2006之间的完全平方数，数的奇偶性，可以发现这个硬币号码的约数有几个，就会被翻动几次，翻动奇数次，硬币正面向下，只有完全平方数的约数是奇数个，所以找到1-2006之间的完全平方数即可。

3. 两个数的异或与两个数的和,能否确定这两个数.

不能.

比如x=2,y=9与x=1,y=10这两种情况下,和都为11, 异或以后也是11

4. 1000条直线最多将平面分成多少个部分.

1条直线最多分成2个部分
2条直线最多分成4个部分
3条直线最多分成7个部分
有n-1条直线时，增加一条直线，最多与原来的n-1条直线都相交，增加n部分
所以，
n条直线最多分成 1+1+2+3+4....+n=1+n*(n+1)/2

扩展:n个圆最多可以把平面分成多少部分？

设n个圆最多可以把平面分成S(n)个部分。
则可得：
S(1)=2；
S(2)=4；
...
前n-1个圆最多将平面分成S(n-1)个部分，此时，对于第n个圆来说，它与先前的n-1个圆最多有2(n-1)个交点，即此第n个圆最多被这2(n-1)个交点分成2(n-1)条圆弧段。

由于每增加一个圆弧段，便可将原来的某个区域分为两个区域（此处最好看图分析）。因此，第n个圆使平面增加了2(n-1)个区域。因此可得递推关系式：
S(n)=S(n-1)+2(n-1), 其中n大于等于2。
由此递推关系式得到：
S(n)=S(1)+2*1+2*2+...+2*(n-1)=2+n*(n-1)=n^2-n+2；
即n个圆最多可以把平面分成(n^2-n+2)个部分。