首页 > 其他 > 详细

D. 蚂蚁平面

时间:2019-08-04 10:36:31      阅读:201      评论:0      收藏:0      [点我收藏+]
D. 蚂蚁平面

单点时限: 2.0 sec

内存限制: 512 MB

平面上有 n只蚂蚁,它走过的路径可以看作一条直线

由这n 条直线定义的某些区域是无界的,而另一些区域则是有界的。

有界区域的最大个数是多少?

比如现在有4条直线,只有下面最左边的图中直线定义的有界区域是最多的

技术分享图片

输入格式

T 组输入, (1T100)

每组一个数 n ,(1n109)

输出格式

对于每组数据,输出一个整数表示有界区域的最大个数。

样例

input
1
4
output
3
 类似问题总结:

1 题目:n 条直线,最多可以把平面分为多少个区域。

    公式:B(n) = n(n+1)/2+1  或者 F(n)=F(n-1)+n

平面上有n个X型不明物体,使得划分形成的平面尽量多

  公式  f=N(2N+1)+1

 

3 .折线分割平面

技术分享图片

从图中可以看到,每多出一条折线,都会多出4*(n-1)个交点,也就是说会 多出4*(n-1)+1个平面,那么我们可以得到递推式:

       f [n] = f [n-1] +4*(n-1)+1或者2*n^2-n+1

 

 

 

 
 
 

D. 蚂蚁平面

原文:https://www.cnblogs.com/Accepting/p/11297205.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!