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