最長指數 - 遞歸

我需要編寫代碼爲這項任務，研究的主題是遞歸的方法：最長指數 - 遞歸

例子：考慮ARR = {0,5,1,1,2}。指數0,2和3放置良好：

指數0自P0 = 0以來就處於良好位置。
因爲P1 = 5> 1，所以索引1的位置不好。由於所有元素都爲正，這是不可能找到一個序列起始於該可以歸納爲1
索引2索引1處於有利地位，因爲P2 + P3 = 2
索引3處於有利地位，因爲P3 + P4 = 3.
索引4的位置不正確：我們無法找到從索引開始的可以加到4的序列 - 這是因爲P4是數組中的最後一個元素，它只有2。

我們定義一個放置好的索引的'放置好的長度'爲j-i + 1 - 當求和時表示索引放置得很好的序列的長度。有可能一個索引與多於一個單一的元素序列相配合。在這種情況下，「良好放置的長度」是定義索引爲「良好放置」的各種序列的最大長度。

實施例：看前面的例子：

索引0以及放置長度爲1（I = 0，J = 0，J-I + 1 = 1）。
索引2合適的長度是2（i = 2，j = 3，j-i + 1 = 2）。
索引3合適的長度是2（i = 3，j = 4，j-i + 1 = 2）。
對於指數1和4，沒有定義好位置的長度，因爲指數沒有很好的放置。
考慮arr = {0,5,1,1,2,0} - 索引3良好的長度現在是3（i = 3，j = 5，j-i + 1 = 3）。定義索引3的另一個序列與以前一樣是（i = 3，j = 4，j-i + 1 = 2），但是我們已經將定位良好的長度定義爲索引的最大值。

「最大放置長度」是arr中所有放置好的索引的放置良好長度之間的最大值。如果數組中的索引沒有正確放置，則最大放置長度被認爲是零。

該函數應返回最大放置長度。

示例：對於前面的示例，longestIndex的返回值應爲2，因爲這是數組中任何放置良好的索引的最大放置長度。

限制：您不允許更改數組;您不得使用可從longestIndex獲得的超過1個附加（輔助）功能。不允許迭代。

這是我寫的代碼：

int longestIndexHelper(int arr[], int length, int old) 
{ 
    if(length==0) 
    return 0; 
    if((arr[length]+arr[length-1]==length-1)|| 
     (arr[0]==0)&&(old!=0)&&(old-length==1)) 
     return (longestIndexHelper(arr, --length, length)+1); 
} 

int longestIndex(int arr[], int length) 
{ 
    return longestIndexHelper(arr, length, length); 
}

很顯然，這是行不通的:) 可能有人請盡力幫助？

來源

2009-12-14 shanshan

你寫的代碼顯然不會編譯 - 你的if語句沒有別的用例。如果你編輯它以表明你已經嘗試過了，我或其他人可能會呃 – 2009-12-14 10:15:27

從什麼時候開始每個if語句塊都必須有'else'的情況......？ – 2009-12-14 15:44:26

不允許迭代。

這是一個完全人爲的限制，它將我們推向遞歸，當它在這種情況下顯然是劣等的解決方案時。大學教授什麼時候開始爲想要這些作業提供遞歸解決方案（比如樹行走）？

我會親自做這個，通過編寫迭代版本並將其轉換爲尾調用遞歸函數。只是爲了滿足這個任意的要求。將迭代版本留在那裏就是因爲。

反正你不工作的原因是，它永遠只檢查長度的精心佈置的匹配2.

編輯：這是我的遞歸解決方案的快速概要：

int longestIndex(int arr[], int length) { 
    if(length == 0) return 0; 
    int thisLongestIndex = longestIndexHelper(
     /*whatever parameters you need in order to call it on the first element 
        in the array*/ 
     ); 
    return max(thisLongestIndex, longestIndex(arr+1,length-1)); 
}

其中，longestIndexHelper將計算出陣列中第一個元素的最長匹配。

來源

2009-12-14 10:14:34

我不打算調試您的整個功能，但一個明顯的潛在缺陷是，在某些情況下，您的幫助函數不會返回任何值。

您需要考慮if()測試失敗時遞歸如何繼續。

來源

2009-12-14 10:15:45 Alnitak

最長指數 - 遞歸

回答

相關問題