我该如何摆脱固定的哨兵值（-32767）？

下面是我写的从给定的数组中找到一个子数组的总和的程序，但不知何故，我没有得到如何摆脱哨兵值（在这种情况下是-32767）？以及如何优化它？以及如何跟踪最大子阵列的范围？我该如何摆脱固定的哨兵值（-32767）？

#define EVALUE -32767 

using namespace std; 

int findMaxSubArray(vector<int>,int low,int high); 
int findMaxSubArray_Mid(vector<int>,int low,int high); 

int main() 
{ 
    vector<int> v; 
    int j=0; 

    cout << "Enter array values(-32767 to end): "; 
    while(1) 
    { 
     cin >> j; 
     if (EVALUE==j) 
      break; 
     v.push_back(j); 
    } 

if(v.size()!=0) 
    cout << "Max sum is: " << findMaxSubArray(v,0,v.size()-1) << "\n"; 
else 
    cout << "No array elements entered, exiting...\n"; 

system("pause"); 
return 0; 
} 

int findMaxSubArray(vector<int> v, int low, int high) 
{ 
    if(low==high) return v[low]; 

    int max_mid_sum=findMaxSubArray_Mid(v,low,high); 
    int max_left_sum=findMaxSubArray(v,low,(low+high)/2); 
    int max_right_sum=findMaxSubArray(v,(low+high)/2+1,high); 

    if (max_mid_sum>max_left_sum) return (max_mid_sum>max_right_sum?max_mid_sum:max_right_sum); 
    else return(max_left_sum>max_right_sum?max_left_sum:max_right_sum); 
} 

int findMaxSubArray_Mid(vector<int> v,int low,int high) 
{ 
    int mid=high/2; 
    int max_left_sum=0; 
    int max_right_sum=0; 
    int sum=0; 

    for(int i=mid;i>=low;--i) 
    { 
     sum+=v[i]; 
     if(sum>max_left_sum)  
     { 
      max_left_sum=sum; 
     } 
    } 

    sum=0; 
    for(int i=mid+1;i<=high;++i) 
    { 
     sum+=v[i]; 
     if(sum>max_right_sum) 
     { 
      max_right_sum=sum; 
     } 
    } 

    return (max_right_sum+max_left_sum); 
}

来源

2011-08-18 ADJ

您是否试过'j == EVALUE'？ – 2011-08-18 18:27:57

感谢您的评论。但是，我想知道一种避免在这里使用像EVALUE这样的硬编码值的方法。 j == EVALUE不会有任何区别... – ADJ

我不明白任意值的原因，但没有错误，如果这是你打算做的。 – 2011-08-18 18:39:02

从文本文件读取数据时，即CIN将获得最后一个字符是“EOF”字符或文件结束符。您可以使用control + d在命令行中将此字符发送到您的程序。你将要检查这个，而不是-32767。

这是一个基本的程序，应该确定你的问题的简单的解决办法：如果你想获得真正聪明的你可以用下面的

#include <vector> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    vector<int> v; 
    int j; 

    cout << "Enter array values (Control+D (EOF) to end): "; 
    cin >> j; 
    while(cin.good()) 
    { 
     v.push_back(j); 
     cin >> j; 
    } 

    return 0; 
}

，它会直接在CIN将内存中的内容（从开始到EOF）放入你的矢量中。就运行时间而言，这可能会比您的解决方案和上述解决方案更快。

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 

using namespace std; 

int main() 
{ 
    vector<int> v; 
    cout << "Enter array values (Control+D (EOF) to end): "; 

    istream_iterator<int> in(cin); 
    istream_iterator<int> eof; 
    copy(in, eof, back_inserter(v)); 

    ostream_iterator<int> out(cout, "\n"); 
    copy(v.begin(), v.end(), out); 

    return 0; 
}

来源

2011-08-18 18:53:03

谢谢arasmussen，这是一个很棒的技巧。 – ADJ

我想你想要第一个例子是'while（cin >> j）{v.push_back（j）; }'？ – Bill

我相信我的第一个例子是正确的。这可能意味着我写'while（！cin.eof（））'而不是'while（！cin.fail（））' –

关于哨兵，IIRC与Control + D关闭标准输入（可能取决于操作系统）。这将导致< <失败（我不知道如何，可能你会得到一个异常）。

无论如何，其余的代码只是一个递归（二项式）添加的向量。你可以用一个简单的sustitute这一切对

for(int i = 0; i < v.size(); i++) { 
    total += v[i] 
}

约最大子数组的范围问题已经由Vector类管理

来源

2011-08-18 18:49:45 SJuan76

谢谢你，Ctrl + D是一个gr8的想法。 – ADJ

我不认为总和是正确的，因为（我认为）如果数组包含负值，他会得出与您的结果不同的结果。 –

我该如何摆脱固定的哨兵值（-32767）？

回答

相关问题