做题感悟:
一开始的想法是找规律,但是后来没坚持下来。应该多思考一下的!!
题意:
给你 n 条折线能把一个平面分成几部分。
解题思路:
方法一:先看N条直线能把一个平面分成几部分,当添加第N条只直线时,为了使平面最多,则第N条直线要与前面的N-1条直线都相交,且没有任何三条直线交于一个点。则第N条直线有N-1个交点。由于每增加N个交点,就增加N+1个平面,所以用N条直线来分隔平面,最多的数1+1+2+3……+n=1+(n+1)*n/2 ;再看每次增加两条相互平行的直线,当第N次添加时,前面已经有2N-2条直线了,所以第N次添加时,第2N-1条直线和第2N条直线都各能增加2*(n-1)+1 个平面。所以总平面为:1+4*n(n+1)/2-2*n=2*n*n+1
;如果把每次加进来的平行边让它们一头相交每一组平行线相交后,就会减少一个面,所以所求就是平行线分割平面数减去N,为2*n*n-n+1,利用上述总结公式 f( n ) = 2*n*n - n + 1 。
方法二:分割平面的个数=交点个数+顶点个数+1。令f(n-1)为前n-1条折线分割的平面数,当添加第n条折线时。因为每一条边与前n-1条折线的两条边都相交,故增加的交点数为2*2*(n-1),顶点增加1,故 f(n)=f(n-1)+4(n-1)+1。
代码:(方法二)
#include<stdio.h> int f[10005] ; int main() { int T,n ; f[1]=2 ; for(int i=2 ;i<=10000 ;i++) f[i]=f[i-1]+4*(i-1)+1 ; scanf("%d",&T) ; while(T--) { scanf("%d",&n) ; printf("%d\n",f[n]) ; } return 0 ; }