學弟問我的一個題目，去年本來做過，但是做的稀里糊涂，今天拿出來重新推導了一遍，特記錄于此。
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2971
先假設a2 = t, 題目給定了遞推關系：An = 2 * t * An-1 - An-2 (n > 2)，初值A1 = 1, A2 = t；題目要求Sn = An ^ 2 + An-1 ^ 2 + ... + A1 ^ 2。
反復應用遞推關系得到：
然后Sn-1利用相同的方式展開，把4tAn-2An-3約去，得到：
這樣就比較容易得出Sn的通項：
當初這個題目之所以沒想到這種方法，就是因為一看到遞推關系，就想著用一般解方程的方法去求解通項，思維被局限了，其實用簡單的方式就可以推出來的。以后對于一個問題，應該從多個方面去想，不能想當然啊。想起最近看到的一段話，以此自勉：
正則表達式非常強大，但是它并不能為每一個問題提供正確的解決方案。你應該學習足夠多的知識，以辨別什么時候它們是合適的，什么時候它們會解決你的問題，什么時候它們產生的問題比要解決的問題還要多。
一些人，遇到一個問題時就想：“我知道，我將使用正則表達式。”現在他有兩個問題了。——Jamie Zawinski
posted on 2010-03-12 13:06
sdfond 閱讀(447)
評論(2) 編輯 收藏 引用 所屬分類:
Algorithm - Combinatorics