该类问题所推得的公式通常为f(n)=f(n-a)+f(n-b)+f(n-c)。方法通常适用于排队现象并且在排队的时候有一定的限制条件。
注意：只分析正确的情况，错误的不分析，从最后一个数向前分析当达到某个数一定是X的时候便是结果得出的时候。
排序的要求是女生们必须一个以上的人站在一起，男生可以单个站，求n个学生的一共排队方案。
设符合以上要求设为安全，人数增加可以在队列的后面添加男生或女生来判断添加后是否为安全。
计算F（n）:
一：当最后一个是男孩M时候，前面n-1个随便排出来，只要符合规则就可以，即是F（n-1）；
二：当最后一个是女孩F时候，第n-1个肯定是女孩F，这时候又有两种情况：
1）前面n-2个可以按n-2个的时候的规则来，完全可以，即是F（n-2）；
2）但是即使前面n-2个人不是合法的队列，加上两个女生也有可能是合法的。当第n-2是女孩而n-3是男孩的情况，可能合法，情况总数为F（n-4）;
综上所述：总数F(n)=F(n-1)+F（n-2）+F(n-4);并且，F（0）=1，F(1)=1，F(2)=2，F（3）=4。
在n达到1000时，F（n）的大小一定会超出内存，故需要考虑大数的解决。
同样，使用此方法的还有之后的题目：Queuing
也是男女孩排队，不过不能出现fff,fmf的子序列。
可以假设前n-1项都是符合要求的，那么前两项可能为：1、ff 2、mm 3、fm 4、mf
1、最后一项是m则方法都适用，为f(n-1)。
2、最后一项是f，那么只能为2、4。而1、3情况是不安全的。
一、第2种情况，第n-3项的选择是不受打扰的，即只要前n-3项安全，加上mm后也是安全的，故有f（n-3）种情况。
二、第4种情况，若加上mf后仍旧安全，第m-3项必须为m，而在安全的队伍后加上mmf仍旧是安全的，故方案有f（n-4）。
所有情况分析完毕，得出公式：f(n)=f(n-1)+f(n-3)+f(n-4)。
网友评论