1290 献给杭电五十周年校庆的礼物
题目
分析
我们首先应该熟知二维的分割问题,如有疑问请参考上一篇blog2050
折线分割平面问题。
平面分割与交点有关。我们可以猜想在三维中空间数是否与平面的交线有关呢?
当有n-1个平面时,分割的空间数为f(n-1)。要有最多的空间数,则第n个平面需与前n-1个平面相交,且所有交线不重合,即最多有n-1 条交线。反过来思考,这n-1条交线把第n个平面最多分割成g(n-1)个区域。(g(n)为n条直线分平面的个数 )。
此时,第n个平面上每个区域将原有的空间一分为二,故最多增加g(n-1)个空间
所以,有公式: f(n) = f(n-1) + g(n-1)
其中,g(n) = g(n-1) + n,求出其通项公式为g(n) = n(n+1)/2+1。代入化简,有f(n) = f(n-1) + n(n-1)/2 + 1
代码
#include <stdio.h> int main() { int n, i; long long surface, space, pre_space; while (scanf("%d", &n) != EOF) { if (n < 1 || n > 1000) return ; pre_space = 2; space = 4; if (n == 1) printf("%lld\n", pre_space); else { for(i = 2; i <= n; i++) { space = pre_space + i*(i-1)/2 + 1; pre_space = space; } printf("%lld\n", space); } } return 0; }