hd acm2025

问题:平面上有n条折线,问这些折线最多能将平面分割成多少块?

思路:像这种平面被线段分割成几部分的问题,80%用递推解决,因为n条线段与(n-1)条线段能建立联系。

     你可以作图观察一下,会发现新增加的折线被分割成几个区段,平面就会增加几部分,而区段的增加又与新增折线与原有折线的交点数有关,这便建立了关系,即:

   f(n)=f(n-1)+4*n-3,这样便可以使用递推解决。

代码: 

#include <stdio.h>
#include <stdlib.h>
int seg(int x);

int main()
{
  int C,i,x;
  scanf("%d",&C);
  for(i=0;i<C;i++)

  {
  scanf("%d",&x);
  printf("%d ",seg(x));
  }
  return 0;
}
int seg(int x)
{
  if(x==1) return 2;
    else return seg(x-1)+4*x-3;
}

原文地址:https://www.cnblogs.com/clljs/p/7428603.html