我該如何擺脫固定的哨兵值（-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）？

回答

相關問題