检查数组中所有对的递归函数。
给出了一个int向量，并且我需要找到数序列的最大和，它们之间的距离超过3个位置。举个例子：
Input: 10, 5, 6, 7, 16, 18, 12
Output: 29
Explanation:
candidate "routes":
10-7-12 = 29
10-16 = 26
10-18 = 28
5-16 = 21
5-18 = 23
5-12 = 17
...
16
18
12我想用递归来解决这个问题，我已经到了程序测试所有路径的点，这些路径的位置都在3个以上。但是，它无法测试从同一位数开始的所有路径。这里我的代码：
#include <iostream>
using namespace std;
const int n = 7;
int sum = 0;
int temp=0;
void rec(int (*arr), int ind){
if (ind > n-3){
if(temp > sum)
sum = temp;
temp=0;
return;
}
temp += arr[ind];
cout<<arr[ind]<<" ";
for(int i=3;i<n;i++)
rec(arr, ind+i);
cout<<endl;
}
int main(){
int arr[n] = {10, 9, 9, 9, 8, 8, 7};
for(int i=0;i<n;i++)
rec(arr, i);
cout<<endl<<endl<<"Max: "<<sum;
return 0;}输出：
10 9 7
8
8
7
9 8
8
7
9 8
7
9 7
8
8
7
Max: 26即使在这种情况下，输出是正确的，但您可以看到，它只测试10-9-7，而不测试其他10-8、10-8和10-7。它似乎甚至没有进入我递归调用的第一个for-循环函数。
我是否理解错了什么，或者如何完成它测试所有三个以上位置以外的配对？
回答 1
Stack Overflow用户
发布于 2021-05-06 09:40:16
这里有三个问题：
根据您的输出：
10 9 7
8
8
⋮您的代码实际上遍历了所有可能的路由。与其将第二行8和第三行8视为两条完整的路由，它们实际上是从第一条rout 10 9 7派生出来的。所以你应该这样想：
10 --- 9 --- 7
`- 8
`- 8
`- 7
9 --- 8
`- 8
`- 7
⋮这实际上不是你的输出。插入您的代码，我得到了输出：
10 9
8
9 8
9
9
8
Max: 19它没有经过所有路线的原因是因为你的线路：
if (ind > n-3)
{
⋮
return;
}你的循环结束太早了。相反，您应该只在它超出索引之前结束它。所以应该是：
if (ind > n - 1)
{
⋮
}你的逻辑实际上有缺陷。
因为一旦到达数组中的最后一个可能的数字，您总是将temp设置为0，因此实际上丢失了以前的部分和。您可以轻松地创建一个使其失败的序列，例如：10, 9, 9, 7, 8, 20, 7。
与其将temp设置为全局的，不如将其设置为本地，并传递给每个递归。
为此，您需要添加temp作为rec函数的参数，并将其调用如下：
void rec(int (*arr), int ind, int temp)
{
⋮
rec(arr, i, temp);
⋮
}
int main()
{
⋮
rec(arr, i, 0);
⋮
}或者，如果要在main中保留相同的签名，也可以在rec中添加默认参数。
void rec(int (*arr), int ind, int temp = 0)附带注意，我会考虑使用std::array或std::vector代替c样式数组，以避免在函数中使用全局大小n或传递int (*arr)。此外，您可以轻松地使您的arr作为一个较长的序列。
https://stackoverflow.com/questions/67412534
复制相似问题
腾讯云开发者
