随笔-19  评论-1  文章-0  trackbacks-0
问题是这样的:问用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 孟起 阅读(310) 评论(0)  编辑 收藏 引用 所属分类: 递推 递归

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理