問題是這樣的：問用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
孟起 閱讀(411)
評論(0) 編輯 收藏 引用 所屬分類:
遞推 遞歸