面试题 - PHP逻辑算法:一张纸最多可以分割成多少块?
程序员文章站
2024-02-02 10:17:34
...
题目:
在一张白纸上画2999条直线,最多可以将白纸分割成多少块?请写出计算函数
答案:
//?
function maxBlock($num)
{
//@todo 如何计算?
}
求算法
maxBlock(2999);
回复内容:
题目:
在一张白纸上画2999条直线,最多可以将白纸分割成多少块?请写出计算函数
答案:
//?
function maxBlock($num)
{
//@todo 如何计算?
}
求算法
maxBlock(2999);
一条线,只要它不跟之前任何的线平行,它就与所有的线都相交。
可以做到这一点,因为线的斜率可以取任何实数和无穷大,是稠密的。
一条线分割了另一条线,就相当于分割了它下方的区域。
这时我们可以得到这样的递推式:S(0) = 1; S(n) = S(n - 1) + n;
S几乎就是一个等差级数的部分何,展开之后是:S(n) = (1+n)n/2 + 1;
好了S(n)
就是你想要的maxBlock(n)
了。
上一篇: Swoole:重新定义PHP