两道递推公式题的解题报告

Bertha 。 2021-12-24 19:19 221阅读 0赞

# T1（阿牛的EOF牛肉串） #

*  题意：一串由EOF三个字母组成的长度为\\(n\\)的字母串，不能出现连续的OO，求字符串种类数\\(f\[n\]\\)
 *  答案：\\(f\[n\]=2f\[n-1\]+2f\[n-2\]\\) ——①
 *  注解：
    
        如果a[n]取E，该情况下种类为f[n-1]；
        
              如果a[n]取F，该情况下种类为f[n-1];
        
              如果a[n]取O，则只能取a[n-1]为E或F，分别有f[n-2]种。
        
              综上，一共有f[n-1]+f[n-1]+f[n-2]+f[n-2]种。

# T2 （原题找不到了，恳请见过的巨佬提供线索） #

*  题意：一串由WAC三个字母组成的长度为\\(n\\)的字母串，不能出现连续的WA，求字符串种类数\\(f\[n\]\\)
 *  答案：\\(f\[n\]=3f\[n-1\]-f\[n-2\]\\) ——②
 *  注解：
    
        先假设没有非法字符串，那么很明显，总数是3f[n-1];
        
              再去掉a[n-1]和a[n]组成非法串的情况，此时等价于固定a[n-1]与a[n]，求前面n-2个的排序，为f[n-2];
        
              综上，一共有3f[n-1]-f[n-2]种。

> 数学课讲题的话到这里为止吧

# 比较 #

这两题看似相似，其题解分别看来也都很有道理，为什么其结果却大相径庭呢？

# 为什么T1不适合用②式： #

**因为去掉的含非法字符串的情况不是f\[n-2\]。**

因为在求f\[n\]时我们已经事先使前n-1项合法，所以在f\[n-1\]（我们用来乘以三作为总数的）中a\[n-1\]为O的可能性比T2中a\[n-1\]为W的可能性小。

这是因为，a\[n-1\]中的O可以作为非法串的尾，与a\[n-2\]组成OO。因此，在求f\[n-1\]时已经有一部分a\[n-1\] 为O的情况被筛掉了。

但对于T2，在求f\[n-1\]时不可能把a\[n-1\]为W的情况筛掉，因为W只能做头，不能做尾。

# 为什么T2不适合用①式： #

# 我的理解当中比较重要的点 #

*  求f\[n\]时对a\[n\]的假设是在保证a\[1\]~a\[n-1\]合法的基础上的，并在此基础上对a\[n-1\]进行分类讨论。在求f\[n\]时实际上是对a\[n\]的放置，我们要避免的是a\[n-1\]与a\[n\]形成非法字符串。
 *  T1中的O既可以当非法子串的头，也可以当尾，这应该是这两种情况不同的根本原因。
 *  由上述分析可见n>=3时T1的f\[n\]总比T2大，因为我们先假设没有非法串求其总数，之后要去掉含有非法串的情况，对于T1来说同一个O既可以当头又可以当尾，因此它的去除具有“简并性”（逃。

# 注 #

*  时间关系，懒得举特例来具体对照了，以后补。
 *  另外，以上的比较与分析，只是本蒟蒻因为某些奇奇怪怪的原因(讲数学题去找递推题后，发现的疑惑以及自己的解惑思路。像我这样菜的人对递推还没有更深刻的理解，因此本文中还有很多不恰当的误解和错误，在语言组织与文章结构方面也显得很不成熟，恳请屏幕前的巨佬不吝赐教，一起交流这些奇奇怪怪(毒瘤的想法。

转载于:https://www.cnblogs.com/Y15BeTa/p/11013624.html