问题是这样的：问用n条直线最多能将平面分成多少个区域？
这也是一个很简单的递归问题： L[n] = L[n-1] + n; (L[0] = 1)
通项公式如下：L[n] = n * (n + 1) / 2 + 1 ( n>= 0 )
如果不用直线的话，用一个一般的折线，那么n个这样的折线最多可以拆分平面:
D[n] = L[2*n] - 2 * n;
D[n] = 2 * n ^ 2 - n + 1;
如果用"Z"字型的线，n个折线最可拆分平面：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=652
Z[n] = Z[n-1] + 9*n - 8;
Z[n] = (9*n^2 - 7*n + 2) / 2;
1 #include<stdio.h>
2 int main()
3 {
4 int n;
5 while(scanf("%d",&n)!=EOF){
6 printf("%d\n",(9*n*n-7*n+2)/2);
7 }
8 return 0;
9 }
posted on 2010-10-11 10:45
孟起 阅读(362)
评论(0) 编辑 收藏 引用 所属分类:
递推 递归