2

カウント選択を使用して実行中の中央値アルゴリズムを実装しようとしていますが、行き詰まりました。

分析するシーケンスは「mySequence」と呼ばれ、2 つのグローバル変数を作成しました。データとカウントのベクトル。データは mySequence が 1 つずつ転送されるもので、counts は各要素のカウントです。

これを完全に間違っているか、重要なステップを見逃しているのではないかと心配しています。

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;
int maximum = 0;
vector<int> data;
vector<int> counts;
vector<int>::iterator it;

/*
 * A Program that calculates and outputs the running median of a sequence of values
 */

/////////////////////////////////////////////////////////////////////////////
// This function prints the running median of a sequence of values past to it
/////////////////////////////////////////////////////////////////////////////

void runningMedian(int element, int k) { // vector<int> &data
    maximum = data.size(); // finds how many data elements are to be processed  

    for (int i = 0; i <= maximum; i++) // this creates the counts for each element
    {
        counts[element] += 1;
    }

    int c = 0;
    while (k >= 0) {
        k -= counts[c++];
        }
    cout << c - 1;

}

/////////////////////////////////////////////////////////////////
// This main function uses test data to test the above functions
/////////////////////////////////////////////////////////////////

int main(int argc, char** argv) {

    int mySequence [] = {7, 9, 3, 8, 0, 2, 4, 8, 3, 9}; // test sequence
    for (int i = 1; i <= 10; i++) counts.push_back(0); // This initialises the counts vector all to 0

    /// prints out the sequence of the data ///
    cout << "Sequence: ";
    for (int i = 0; i < 10; i++) {
        cout << mySequence[i] << " ";
    }
    cout << endl;
    /// /// /// /// ///


    cout << "Running Medians: ";
    for (int i = 0; i < 10; i++) {
        data.push_back(mySequence[i]); // puts sequence into vector 1 by 1
        runningMedian(mySequence[i], (data.size() / 2));
        cout << " ";
    }

    return 0;
}
4

1 に答える 1

0

これは間違いのようです：

void runningMedian(int element, int k) { // vector<int> &data
    maximum = data.size(); // finds how many data elements are to be processed  

    for (int i = 0; i <= maximum; i++) // this creates the counts for each element
    {
        counts[element] += 1;
    }

forループが繰り返されるのを見ると心配になります。i=0; i<= ...実際には、maximum+1回数ではなく、maximum回数だけ繰り返されます。(イディオムはi=0; i< ....) これは多くの場合、バッファ オーバーフローまたは初期化されていないメモリ アクセスへの迅速なルートですがi、この場合は使用していないため、その影響はありません。私はあなたがi代わりに意味していたと思いますelement-そうでなければ、なぜループを気にするのですか? これは、次のようにループなしで書き直すことができます。

counts[element] += (maximum + 1);

i(おそらく配列インデックスとして使用するつもりだったと思う理由がわかります。)

他に目立ったものは何もありませんが、おそらく私もそれを見落としています。

于 2012-06-12T00:50:36.140 に答える