首页 > 代码库 > 白书 5.4.4 多少块土地
白书 5.4.4 多少块土地
此题初识欧拉公式 V - E + F = 2.
其中V是顶点(即所有线段的断点数加上交点数),E是边数(即n段椭圆弧加上这些线段被切成的段数),F是面数(即土地块数加上椭圆外那个无穷大的面)。
-------------------------------------------------------------------------------------------------------
有一块椭圆的地,你可以在边界上选n个点,并两两连接得到n(n-1)/2条线段。它们最多能把土地分成多少个部分?
解:
最优方案是不让三条线段交与1点。
欧拉公式:V-E+F=2.其中V是顶点(即所有线段的断点数加上交点数),E是边数(即n段椭圆弧加上这些线段被切成的段数),F是面数(即土地块数加上椭圆外那个无穷大的面)。
换句话说,只需求出V和E,答案就是E-V+1;
不管是定点还是边,计算时都要枚举一条从固定点出发(所以最后要乘以n)的所有对角线。假设该对角线左边有i个点,右边有n-2-i个点,则左右两边的点两两搭配后在这条对角线上形成了i*(n-2-i)个焦点,得到了i*(n-2-i)+1条线段。注意:每个交点被重复计算了4次,而每条线段被重新计算了2次。
//因为形成每个交点需要4个点两两组成2条线段相交于一点,需要2个点形成1条被分割的线段。
公式为
如果将n=1~5的答案写出来得:1、2、4、8、16.可能就会推出n=6时是32,但是不是的,而是31,因此找规律的时候要谨慎!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。