noip初賽閱讀程序遞歸題該如何做？

01-08

我做初賽的閱讀程序遞歸題的時候，總感覺有暈暈乎乎的，不知道return到底返回什麼，比如這道題
裡面有個return 0和return 1，是不是結果最終返回的是0或1，還有return lps(seq,i+1,j-1）+2也不是很清楚，懇請大神可以說說這類遞歸題該如何做

一般的閱讀程序寫結果都是一些經典的演算法的實現，只要見過的比較多，好多都能一眼看出來這個是幹嘛的。如果不能一眼看出來，就分析分析變數名，分析分析語義，也能看出來他在幹什麼，不過這個也需要一些經驗吧，比如你對設計動態規劃的轉移特別熟悉的話，上面那個是能很明顯看出來的。

如果實在看不出來的，一般都是一些較好模擬的，用一張大點的紙就行了，注意記好傳入的值和傳出的

謝不邀。

這個題應該是去年提高組看程序寫結果第三題，當時考場上包括我周圍大部分人都一眼秒了。

看到這種遞歸上來就直接模擬不是很明智，最後可能都沒時間檢查，而且原題字元串比較短，如果稍微長一點也是要佔用一點時間的，所以碰到遞歸的問題無論是普及組還是提高組最好還是弄清楚遞歸的含義。

比如這個題看到lps，看到一個字元串，看到i，j兩個變數模擬指針，而且i遞增j遞減，就應該能猜到這個是想在字元串頭尾找什麼東西，再看到s[i]==s[j]就能反應過來這個可能是在找字元串最長迴文子序列了。不放心還能再驗證一下，頭尾指針相同的答案明顯是1，頭指針超過了尾指針答案明顯是0，如果當前頭指針指的字母和尾指針指的字母相等就順著移一下，不然一定有一個字母取不了，就移其中一個然後取個max。所有題目做完如果還有時間就再人工模擬遞歸過程是最好的（一般來說初賽題目做完都能剩下一半時間

初賽裡面大部分的遞歸都是有意義的，沒有意義的毒瘤模擬題我也遇到過，這種就只能畫個棧了

有些遞歸題可以用記憶化的技巧。

即，當遞歸程序不改變全局變數/指針/引用/靜態變數等時，遞歸函數返回值只和參數有關。

調用一次以後，你就把參數對應的返回值記下來，下次調用相同的參數就可以直接用，不用再模擬一遍。

lps這個題，參數只有i和j，可以畫一張二維的表，每個格子代表一種可能的參數(i,j)，然後按順序填表就行了。

模仿一下rxz

我是 @Mike He

匿名防止被競賽班同學看到然後再次發到競賽群里d我。

----分割線---

同意吉司機的說法。

從非競賽角度來看，出題就是讓人看不懂的，然而事實上以後你寫程序讓別人看懂是很重要的。

從競賽角度來講:

1. 觀察函數名字和代碼特點

用這個方法能解決很多顯然的問題。比如題主這個題，lps，去年考試的時候我的第一反應是longest palindromic string或者longest palindromic subsequence....然後再看看發現字母並不一定連續，好那就是子序列了。然後做完了。

當然，這只是投機取巧的解題方法。

2. 理解程序含義

直接模擬確實能夠輕鬆得出結果，但是在這之前如果理解這個程序的目的是什麼，那在模擬的時候就非常輕鬆了。

3. 畫樹狀圖模擬

一般遞歸相關的題目畫樹狀圖模擬整個遞歸過程是最直接的解法，如何畫？已經有dalao發出來了，我就不多說了。

瀉藥

這種題大概就是看清楚程序是在幹嘛吧

或者在紙上寫幾層

謝邀。

遞歸題還是腦容量大好做一些，要不腦子裡存不下那麼多變數，遞歸就會暈。

其實對於題主所給的去年那道題 @OFShare 同學的答案已經解釋的很詳細了，我想就模擬遞歸這個問題說一下我個人的做法，可能不適用於所有人，大家謹慎選用。

每次return的東西不一樣的問題。程序返回的值是啥就是啥，比如說邊界條件返回0或者1。而如果返回的是一個遞歸式，比如說lps(seq,i+1,j-1) + 2，那就按照這個函數計算的規則繼續算lps(seq,i+1,j-1) 就好，直到算出來沒有其他式子，此可謂「遞」。

我們在每一層都算出了相應的值，按照規則，應該把值返回到上一層（可以藉助在草稿紙上畫圖來感性的認知一下這個過程，如果你對遞歸的過程不了解），一層一層返回，一直返回到第一層就是答案了。此之曰「歸」。

說的具體一點，拿到一個遞歸題，仍然是要保持清醒，在腦內模擬這個過程，利用好草稿紙，把每一層的中間變數都記錄一下，換句話說，就是模擬系統棧了。這樣做應該是沒有問題的。

沒法講得很具體，因為有很多技巧只能說是「只可意會不可言傳」，沒法用準確的語言去表述，想要掌握還是得需要不斷的摸索和練習才行2333

嗯差不多就是這些了

手動模擬即可吧

一般這種東西層數又不會多

或者你可以找到規律

一眼看出來這是最長迴文子串

再一眼看出答案

我沒有搞過noip，這裡只能說下我對遞歸這類題的做法(ps:因為曾經的我也看不懂這類遞歸題，更是不會寫遞歸的題，所以深有同感。。。我覺得新手編程的最大攔路虎就是遞歸了，後面的dfs回溯記憶化搜索等各種搜索都是遞歸的直接體現，我個人認為遞歸理解的清楚，碼力會有極大提高，當然這是後話了)

我理解這類題，是以"狀態"入手的（個人認為"狀態「這個詞，它是理解很多概念和演算法的關鍵）

上面就是我模擬這個遞歸程序寫的程序。

這裡的（0,10）就是一個狀態(seq在所有狀態都是不變的，所以省略了)

還有左邊部分的(1,9)算出來是5，所以右邊部分的(1,9)就直接知道也是5了(這就是記憶化搜索，記住某個狀態的值，當再算這個狀態時，直接返回，當然你給的程序這部分沒寫)

還有我算到(6,9)直接知道答案是1了，這又是怎麼回事，前面沒有相同的狀態呀，其實你在模擬這個過程的時候就會發現規律的(提示:字元seq[6],seq[7],seq[8],seq[9]都不相同)

最後說一下如何寫遞歸程序(個人感覺就是找到」狀態「，遞歸邊界，和狀態如何轉移，這聽起來好像動態規劃DP呀23333333就是這麼回事)，你給的程序就是標準的遞歸寫法，一般先寫轉移部分，最後寫邊界，邊界寫在前面。

大概5-10分鐘可以做完(不知道你們noip考多久)

題主加油，多看書，多刷題b(￣▽￣)d

常見演算法一眼看出直接寫答案

一下看不出來的，寫出遞歸棧，一步一步來

如果真的想不清楚的話，不妨嘗試在紙上模擬

現在進行到了第幾層，這一層的幾個變數都是什麼

返回之後按照在紙上的記錄回到上一層處理

這其實就是在紙上仿照計算機運行遞歸程序吧

人腦模擬不能的話可能是大腦內存不夠導致爆棧（就是腦中不能同時裝太多變數233

謝邀。簡單的閱讀程序(那種一下就能看懂的)可以不用打草稿直接出結果，而像去年lps這種題，有兩條路可以走，要麼老實畫出遞歸圖來，要麼尋找規律。後者只要找到一定規律，整個程序根本不需要走，只看main函數輸入就可以很快算出輸出來。

畫遞歸圖什麼的就不再贅述了，其他回答也有提到，在這裡我就簡單說一下找規律的做法。

就拿題主的lps這道題來說吧，不要看到代碼就頭大，先別管臨界值，看看普通情況。所謂普通情況就是：

len1 = lps(seq, i, j-1); len2 = lps(seq, i+1, j); if (len1 &> len2) return len1; return len2;

一句話：這個串的lps，不算特殊情況的話，就是左邊截去一個和右邊截去一個的lps中較大的那個。

這時候我們再去看特殊情況：

if (seq[i] == seq[j]) return lps(seq, i+1, j-1) + 2;

這句代碼就有點意思了。如果串的兩頭的字母是一樣的，那麼就是把兩頭截去之後的lps再+2。

這時候再來看臨界值的處理：

if (i &> j) return 0;

再回顧之前的代碼，發現i&>j的情況只有seq[i]=seq[j]的時候才會出現。所以這行代碼是專為這個特殊情況做的處理。而什麼時候會遇到i&>j呢？顯然，當i+1=j的時候（即串的兩頭之間沒有任何字母了），

return lps(seq, i+1, j-1) + 2;

這裡帶入的i+1就會大於j-1，這是這個遞歸裡面唯一一種遇到i&>j的時候。

此時我們可以發現第一個規律：

規律一：當串的兩頭為同樣字母且串的長度只有2的時候，此串的lps為2。

舉個簡單的這樣的串：

aa

此時lps("aa",0,1) = lps("aa",1,0)+2 = 0+2 = 2

我們接著看代碼：

if (i == j) return 1;

很顯然，i=j的情況，就是在

len1 = lps(seq, i, j-1); len2 = lps(seq, i+1, j);

這裡會碰到。當i+1=j的時候，上面兩個lps里就會出現i=j的情況。

規律二：當串的兩頭為不同字母且串的長度只有2的時候，此串的lps為1。

舉例，

ab

這裡lps("ab",0,1) = max{ lps("ab",1,1), lps("ab",0,0) } = max{ 1, 1 } = 1

只要你能舉一反三，你就會發現：

規律三：無論這個串多長，只要其中沒有相同的字母，它的lps總為1。

如：

abfvdce

遞歸下去，最終總會達到規律二的狀態。

這時我們會想，當規律一和規律三相加，是否成立呢？

舉例：

aba

或者

abfvda

這種兩頭為一個字母，但串不只有這兩個字母的時候，lps(seq, i+1, j-1)就會進入規律三的狀態。於是，

規律四：當串的兩頭為相同字母，串的長度大於2，且串的中間沒有重複字母的時候，此串的lps為3。

就像剛才那個例子，lps("abfvda",0,5) = lps("abfvda",1,4) + 2

lps("abfvda",1,4)不就是規律三嗎？

根據規律三，lps("abfvda",1,4) = 1，所以lps("abfvda",0,5) = 1 + 2 = 3

至此，規律差不多探索完了。仍需要關注的是這段max

if (len1 &> len2) return len1; return len2;

由於遞歸層數越多，剩下的串越短。例如對於一個串abcde，總會遞歸到abcd,abc,ab,bcde,cde,de,bcd,bc,......而abcde最終的lps是所有這些子串的lps的最大值。

規律五：該串的lps值為該串所包含的所有子串lps的最大值

這時候，我們差不多可以來看看題目給出的輸入輸出了：

string seq = "acmerandacm"; int n = seq.size(); cout &<&< lps(seq, 0, n-1) &<&< endl;

其實就是對於acmerandacm這個串取lps值。好了，套用規律一至五，答案顯得很簡單了。

這時候還需要一個技巧就是，我們應集中注意相同的字母。因為不相同的字母lps總是1，它們也就對結果沒有什麼影響了。看到串中有3個a，2個c，2個m。分類討論那所有相同字母「包圍」出的子串的情況，求出lps，最後再比較出最大值即可。

acmera

此時lps = 3（規律四）；

anda

此時lps = 3；

cmerandac

這時有兩層同樣字母的「包圍」，所以lps = 3 + 2 = 5

acmeranda

此時lps = 3

merandacm

此時lps = 3 + 2 = 5

取最大，所以原字元串的lps = 5。問題解決。

雖然說起來比較複雜，實際在腦子中想卻是非常快的。重點在於意識到兩頭為相同字母時的特殊情況，以此為突破口，並且判斷哪些是無用的（在這裡，無相同字母的串就不需要考慮），遞歸題就變得十分簡單。

最後必然出現了重疊子問題，所以當手寫動態規劃就行了

拿一張大點的草稿紙一層層寫出來……

雖然很煩但是如果靠想腦子要炸

我一般是畫一顆搜索樹，但是可以運用一下記憶化。