《编程之美》1.7光影切割问题

由上图可知&＃xff1a;

三条直线最多三个交点&＃xff0c;将平面分成了7个区域&＃xff1b;可以推出&＃xff1a;N条直线 M个交点&＃xff0c;区域数为N&＃43;M&＃43;1。

可以推出&＃xff1a;

每增加一条直线&＃xff0c;如果增加m个交点&＃xff0c;那么这条直线被新增加的m个交点&＃xff0c;分成&＃xff08;m&＃43;1&＃xff09;段。每一段又会将原来的一个区域分成两块&＃xff0c;因此&＃xff0c;新增加了&＃xff08;m&＃43;1&＃xff09;个新区域。增加第N&＃43;1条直线时&＃xff0c;最多与前面N条直线全部相交&＃xff0c;增加n个交点。因此&＃xff0c;最多增加n&＃43;1个区域。由此可得递推式&＃xff1a;

f(n)代表n条直线时的区域的个数。

第n&＃43;1条直线最多和第n条直线 有n个交点。

所以区域数增加n&＃43;1。

解得&＃xff1a;

这里首先用到了一个数学定理&＃xff1a;

已知平面内有n条直线&＃xff0c;这n条直线有m个交点&＃xff08;p条直线交于一点时&＃xff0c;交点数计p-1&＃xff09;。则这n条直线把这个平面分成了n&＃43;m&＃43;1个平面。

这个定理的推论如下&＃xff1a;

已知平面内有n条直线&＃xff0c;则这n条直线最多可以把平面分成1&＃43;n&＃43; &＃xff0c;

更为优雅的一种写法是&＃xff1a;  。

如果换成折线呢&＃xff1f;

增加第N&＃43;1条折线时&＃xff0c;最多与前面的N条折线有 个交点&＃xff0c;最多增加4n&＃43;1个区域&＃xff0c;递推式为&＃xff1a;

解得&＃xff1a;