2017-02-14 84 views
1

我有正數X_1,X_2,... x_n的順序,我想找到一個連續的序列,其中:0 < X_I-x_j < IJ,1 < = j的<我< = N所有我,j。將S(t)定義爲以x_t結尾的最長連續序列的長度。如果 S(t)= 3那麼上述成立爲x_t,x_ {t-1},x_ {t-2}有約束的序列號

我試圖找到一個遞歸公式,並且我完全卡住了。爲了找到一些模式,我嘗試了一些與數字有關的遊戲:

S(5)= 2意味着S(5)= 2 + S(4)和S(4)必須是$ 0 $。那麼可能S(3)可能是1,所以當我們發現S(0)= 0,S(1)= 0時,我們必須立即停止S(4)= 0

基礎案例或可能特殊情況。

是否可以用S(k-1)來寫S(k)?

我想構建一個算法,但首先我需要找出一個遞歸公式。

+0

你能給你的意思的例子由「連續子序列」和「數字」?從名字來看,它聽起來應該是連續的整數 - 例如,0,2,3,4,5,4的最大連續子序列應該是2,3,4,5。但是這並不能滿足你提供的定義。 –

+0

在您的重複中,1的序列似乎無效。這是錯誤還是有意?它絕對與通常的序列定義相矛盾。 – Paul

回答

0

S(0)= 0
如果(x_n < = X_ {N-1}或x_n - X_ {N-1}> = 1)=> S(N)= 0
否則,如果S( (n-1)+ 1

+0

不知道結果會是1而不是0在問題'基本情況或可能特殊情況S(0)= 0,S(1)= 0',所以它似乎函數將有0,2,3 ...作爲結果,但從來沒有1 – AnotherGeek

+0

沒有注意到,調整。我想這需要OP的一些澄清。 – Paul

0

在這個問題中不需要動態編程或遞歸由於簡單比較運算符的關係:它是可傳遞的。這意味着:

a < b and b < c => a < c 

我們可以將上述不等式一點:

x_i - x_j < i - j 
x_i - i < x_j - j 

這使得整個問題變得簡單許多:
定義序列y,其中y_i = x_i - i。找到結尾爲y_t的最長嚴格遞減序列。

由於嚴格遞減序列中的傳遞性,您的條件總是成立,反之亦然。實際上,這兩個約束在這種情況下是等價的,因爲不能有一個既不減少又不違反序列約束的約束。所以在這種情況下根本不需要遞歸,因爲線性關係是完全足夠的(傳遞性)。

你當然會這樣搜索的第一個非遞減對轉化爲一個遞歸函數(儘管它更復雜得多,只是去線性路徑):

S(t) = {t = 0:        0 
     t = 1:        1 
     {x_t - t >= x_{t-1} - (t - 1)}: 1 
     else:        1 + S(t - 1)}