最长指数 - 递归

我需要编写代码为这项任务，研究的主题是递归的方法：最长指数 - 递归

例子：考虑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

最长指数 - 递归

回答

相关问题