n条直线最多可以把一个圆分成多少块?一共有多少种块数不同的分法？

n条直线最多可以把一个圆分成多少块?

 

这是个动态规划的简单题。

在圆中划两条线，显然他们相交时能分成4块。

划第3条线，显然，第3条线与其他两条都有交点（3条线不交于一点）时，划分的区域最多。

每增加一条线。至少能增加一个区域（把一个区域分成两半），然后和之前的直线，每多一个交点，就多分出一个区域。在最多情况下，若已有n条直线，增加一条直线，最多

所以有

f(n) = f(n-1) + 1 + (n-1) = f(n-1) + n;

 

一共有多少种块数不同的分法？

这一问是我自己添的，比上一问要复杂不少。

显然n=1时 g(n) =1. 只有一条线时只能将一个圆分成两半。这是唯一的分法。

当n=2时，增加的直线，当与上一条直线没有交点时，只增加了一个区域，就是 分成3份。

最多只能有1个交点，额外增加一个区域即 4份。 共有这两种分法

 

假设有n条直线时，有g(n) = m种分法。显然，所有直线无交点时，其区域个数最少，为n+1个.每增加一个交点，区域增加一个。当交点数最多的时候，区域最多。所以取值范围是（n+1 .. m);

当n+1条直线时，增加的这条直线，至少增加一个区域。最少情况是n条直线不相交，有n+1个区域，再增加的这条直线，区域至少有n+2个。所以区域最少个数是n+2,比n条直线的情况，n+1个区域是不可能的。

其余的m-1种情况，只需要新直线与之前的无交点，都是可能的。

然后，增加的直线，与之前的n条直线，可能的交点数为(0..n),所以，在n条直线交点最多的情况下，即有m个区域，每增加一个交点，增加一个区域。所以可能的范围为(m+1..m+n+1)，相当于增加了n+1种分法。

所以

g(n+1) = g(n) - 1 + (n+1) = g(n) + n;

 

代码比较简单。

$lines = 10;
@maxfields;
$maxfields[0] = 1;

@maxsol;
$maxsol[0] = 1;

for(1..$lines){
    $maxfields[$_] = $maxfields[$_-1]+$_;
    $maxsol[$_] = $maxsol[$_-1] -1 + $_ ;
}

print "@maxfields \n";

print "@maxsol \n";