例:（2050）折线分割平面
问题描述：
平面上有n条折线，问这些折线最多能将平面分割成多少块?
样例输入
1
2
样例输出
2
7
平面上有n条折线，问这些折线最多能将平面分割成多少块?
解： 折线反向延伸就是相交线 ，n条相交线分割平面的块数最多为 F(n) =2n(2n+)/ +
由于反向延伸而增加的平面数为 g(n)= +(n-) - =2n
所以 f(n)= F(n)- g(n) =2n^ -n +
.“佐罗”的烦恼
说起佐罗，大家首先想到的除了他脸上的面具，恐怕还有他每次刻下的“Z”字。我们知道，一个“Z”可以把平面分为2部分，两个“Z”可以把平面分为12部分，那么，现在的问题是：如果平面上有n个“Z”,平面最多可以分割为几部分呢？
说明1：“Z”的两端应看成射线
说明2：“Z”的两条射线规定为平行的
解：先将"z"的线段和射线进行延伸处理，形成两平行线加一斜相交直线
n+ 个这样的组合可将平面最多分割成 F(n+) = F(n)+(3n+) +3n+ =F(n)+9n+
F(n+) =Sum(9i+)+F() i: ->n
=n(n+)/ +5n +
F(n) =n(n-)/ +5n +
所以 f(n)= F(n) -4n =n(n-)/ +n +
思考题：平面分割方法
问题的提出：
设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
平面分割方法
设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
解：
如图可得 F()=
F(n)=F(n-) +(n-)
解得 F(n) =n(n-) +
1465 不容易系列之一
某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。
分析思路：
1、当有N封信的时候，前面N-1封信可以有N-1或者 N-2封错装
2、前者，对于每一种错装，可以从N-1封信中任意取一封和第 N封错装，故=F(N-1) * (N-1)
3、后者简单，只能是没装错的那封信和第N封信交换信封，没装错的那封信可以是前面N-1封信中的任意一个，故= F(N-2) * (N-1)
得到如下递推公式：
基本形式：d[1]=0; d[2]=1
递归式：d[n]= (n-1)*( d[n-1] + d[n-2])
这就是著名的错排公式
思考： 为什么只有两种情况？前面N-1封信可以有N-1或者 N-2封错装 ---更多的错装已经包含在N-1封错装中
F(N-1) * (N-1) ： 表示对于每一种错装，有 N-1 种替换选择
F(N-2) * (N-1) ： 从N-1 封中选出一封是装对的（这样的选择数有（N-1）种），余下的 N-2封有F(N-2)种错装情况，乘以选择数 （N-1) 即得。。
最后一个思考题（有点难度）
HDOJ1297
Children’s Queue
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9798 Accepted Submission(s): 3117
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?
2
3
2
4
解题分析：
按照最后一个人的性别分析，他要么是男，要么是女，所以可以分两大类讨论：<br>1、如果n个人的合法队列的最后一个人是男，则对前面n-1个人的队列没有任何限制，他只要站在最后即可，所以，这种情况一共有F(n-1); |
2、如果n个人的合法队列的最后一个人是女，则要求队列的第n-1个人务必也是女生，这就是说，限定了最后两个人必须都是女生，这又可以分两种情况：<br>2.1、如果队列的前n-2个人是合法的队列，则显然后面再加两个女生，也一定是合法的，这种情况有F(n-2);<br>2.2、但是，难点在于，即使前面n-2个人不是合法的队列，加上两个女生也有可能是合法的，当然，这种长度为n-2的不合法队列，不合法的地方必须是尾巴，就是说，<br>这里说的长度是n-2的不合法串的形式必须是“F(n-4)+男+女”，这种情况一共有F(n-4).<br>注意：这里的数字很大，存储需使用数组 |
#include<iostream>
using namespace std;
int main()
{
int arr[][]={};
arr[][]=;
arr[][]=;
arr[][]=;
arr[][]=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
arr[i][j]+=arr[i-][j]+arr[i-][j]+arr[i-][j];//
arr[i][j+]+=arr[i][j]/;//
arr[i][j]=arr[i][j]%;//
}
}
int num;
while(cin>>num)
{
int k=;
for(;arr[num][k]==;k--);
cout<<arr[num][k];
for(;k>;)
{
k--;
cout.width();
cout.fill('');
cout<<arr[num][k];
}
cout<<endl;
}
}