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

總結

以上是生活随笔為你收集整理的两道递推公式题的解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。