这是我第一次在这里发帖,我是 c++ 的新手,正在尝试实现最大子数组问题
问题:当函数 max_subarray 被调用时,它永远不会返回导致没有输出
我尝试了什么:我已经将问题缩小到 cross_max_subarray 函数,因为当我从 max_subarray 函数中删除函数调用或注释掉 cross_max_subarray 中的所有代码时,输出正常打印
我想知道的: 如果我尝试在函数..它仍然没有输出..它不能执行那个打印命令吗?
我希望我在正确提出问题方面做得很好,这是我的代码:
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector<int> cross_max_subarray(vector<int> v,int low,int high,int mid){
int lt_sum = -20000;
int sum = 0;
int lt_index = mid;
for(int i = mid; i>=low; i--){
sum += v[i];
if(sum > lt_sum){
i = lt_index;
sum = lt_sum;
}
}
int rt_sum = -20000;
sum = 0;
int rt_index = mid;
for(int i = mid; i<=high; i++){
sum += v[i];
if(sum > rt_sum){
i = rt_index;
sum = rt_sum;
}
}
std::vector<int> a = {lt_index, rt_index, lt_sum+rt_sum};
return a;
}
vector<int> max_subarray(vector<int> v,int low,int high){
cout << "gkjreor";
if(low == high){
std::vector<int> a = {low, high, a[low]};
return a;
}
int mid = (low+high)/2;
vector<int> ll_lh_ls = max_subarray(v, low, mid);
vector<int> rl_rh_rs = max_subarray(v, mid+1, high);
vector<int> cl_ch_cs = cross_max_subarray(v, low, high, mid);
int ls = ll_lh_ls[2];
int rs = rl_rh_rs[2];
int cs = cl_ch_cs[2];
if(ls>=rs && ls>=cs){
std::vector<int> a = {ll_lh_ls[0], ll_lh_ls[1], ls};
return a;
} else if(rs>=ls && rs>=cs){
std::vector<int> a = {rl_rh_rs[0], rl_rh_rs[1], rs};
return a;
} else{
std::vector<int> a = {cl_ch_cs[0], cl_ch_cs[1], cs};
return a;
}
}
int main(){
//number of elements
int n;
cin >> n;
std::vector<int> v(n);
// taking input
for(int i = 0; i<n; i++){
cin >> v[i];
}
// test print
for(int i = 0; i<n; i++){
cout << v[i] << " ";
}
// tried to flush output buffer
cout << endl;
// this is the function call that does not exit
std::vector<int> l_h_s = max_subarray(v, 0, n-1);
cout << l_h_s[2] << "\n";
return 0;
}
最佳答案
有一些错误加在一起使调试程序变得有点困难。一个快速提示是尝试将代码构建成尽可能多的小块,并在编写时测试每个小块。这有助于您及早发现问题。
我必须更改的第一个问题是我在使用 {}
分配 vector 时遇到了问题。出于某种原因,我的编译器不喜欢它。如果您没有遇到此问题,请忽略此问题。我还注意到您正在使用 std::vector
尽管您在顶部声明了 using namespace std
所以我通过删除 std::
在所有 vectors
的前面。
我遇到的第二个主要问题是在 cross_max_subarray
中。问题是你在错误的方向分配变量。 i = lt_index
让你总是改变 i
而不是你想要的 lt_index
。这可能导致无限循环,因为 i
在每个循环中不断地被 = 到 mid
。当我在那个函数中时,我注意到你在两个求和中对 mid
数字求和,所以它最终将它相加了两次。为了解决这个问题,我将右侧从 mid+1
开始。
我注意到的另一个问题是您最终分配了 a[2] = a[low]
。这是一个问题,因为 a
还没有填充任何东西,所以 a[low]
只是垃圾数据。我很确定您只是想执行 a[2] = v[low]
因为 v
是实际保存数据的 vector 。
你所有的错误似乎都很容易犯,我经常犯这些错误。 C++ 有时会让人很困惑,但不要气馁。
这是工作代码:
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector<int> cross_max_subarray(vector<int> v,int low,int high,int mid){
int lt_sum = -20000;
int sum = 0;
int lt_index = mid;
for(int i = mid; i>=low; i--){
sum += v[i];
if(sum > lt_sum){
lt_index = i;
lt_sum = sum;
}
}
int rt_sum = -20000;
sum = 0;
int rt_index = mid;
for(int i = mid+1; i<=high; i++){
sum += v[i];
if(sum > rt_sum){
rt_index = i;
rt_sum = sum;
}
}
vector<int> a(3);
a[0]= lt_index;
a[1]= rt_index;
a[2]= lt_sum+rt_sum;
return a;
}
vector<int> max_subarray(vector<int> v,int low,int high){
// cout << "gkjreor";
vector<int> a(3);
if(low == high){
a[0]= low;
a[1]= high;
a[2]= v[low];
return a;
}
int mid = (low+high)/2;
vector<int> ll_lh_ls = max_subarray(v, low, mid);
vector<int> rl_rh_rs = max_subarray(v, mid+1, high);
vector<int> cl_ch_cs = cross_max_subarray(v, low, high, mid);
int ls = ll_lh_ls[2];
int rs = rl_rh_rs[2];
int cs = cl_ch_cs[2];
if(ls>=rs && ls>=cs){
a[0]= ll_lh_ls[0];
a[1]= ll_lh_ls[1];
a[2]= ls;
} else if(rs>=ls && rs>=cs){
a[0]= rl_rh_rs[0];
a[1]= rl_rh_rs[1];
a[2]= rs;
} else{
a[0]= cl_ch_cs[0];
a[1]= cl_ch_cs[1];
a[2]= cs;
}
return a;
}
int main(){
//number of elements
int n;
cin >> n;
vector<int> v(n);
// taking input
for(int i = 0; i<n; i++){
cin >> v[i];
}
// test print
for(int i = 0; i<n; i++){
cout << v[i] << " ";
}
// tried to flush output buffer
cout << endl;
// this is the function call that does not exit
std::vector<int> l_h_s = max_subarray(v, 0, n-1);
cout << l_h_s[2] << "\n";
return 0;
}
这是我得到的输出:
bash-4.3$ ./a.out
5
1
2
-20
3
4
1 2 -20 3 4
7
关于c++ - 函数调用导致无输出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61896666/