3

AcceleratedC++を読んでいます。現在、私は第3章の終わりにいます。これが、私が行おうとしている演習です。

「整数のセットの四分位数を計算して出力するプログラムを作成してください。」

1番目と2番目の四分位数を見つけましたが、3番目の四分位数を見つける方法がわかりません。これが私のコードです：

 #include <algorithm>
 #include <iostream>
 #include <vector>
 using namespace std;

 int main(){
    cout<<"Enter numbers:";
    int x;
    vector<int>integers;
    while(cin>>x)
        integers.push_back(x);

    typedef vector<int>::size_type vec_sz;
    vec_sz size = integers.size();
    sort(integers.begin(), integers.end());
    vec_sz mid = size/2;
    vec_sz q1 = mid/2;
    double median;
    median = size % 2 == 0 ? ((double)integers[mid] + (double)integers[mid-1]) / 2
: integers[mid];
    double quartOne = ((double)integers[q1] + (double)integers[q1-1])/2; 
    cout<<"The First Quartile is: "<<quartOne<<endl;
    cout<<"The Second Quartile is: "<<median<<endl;
    return 0;
}
4

2 に答える 2

3

1 つの方法は、コレクションを並べ替えてから、3 つの分割項目を取ることです。

vector<int> v = ...;
sort(v.begin(), v.end());
int q12 = v[v.size()*1/4];
int q23 = v[v.size()*2/4];
int q34 = v[v.size()*3/4];

これはデータ数で O(nlogn) です。

もう 1 つの方法は、3 つの区分のデータを個別にバイナリ検索することです。つまり、最初の q12 を提案し、データを渡して正しいかどうかを確認し、間違っている場合は半分ずつ上下に調整し、繰り返します。q23 と q34 についても同様に行います。

これは技術的には O(n) です。これは、32 ビットの int の範囲が固定されており、最大 32 回のパスでバイナリ検索できるためです。

于 2012-05-26T21:17:35.783 に答える
2

このソリューションは、四分位数を計算するためのウィキペディアで説明されている2番目の方法を実装します。奇数と偶数の長さのベクトルの両方に正しい値を提供します。

#include <vector>
#include <tuple>
#include <iostream>
using namespace std;

double median(vector<double>::const_iterator begin,
              vector<double>::const_iterator end) {
    int len = end - begin;
    auto it = begin + len / 2;
    double m = *it;
    if ((len % 2) == 0) m = (m + *(--it)) / 2;
    return m;
}

tuple<double, double, double> quartiles(const vector<double>& v) {
    auto it_second_half = v.cbegin() + v.size() / 2;
    auto it_first_half = it_second_half;
    if ((v.size() % 2) == 0) --it_first_half;

    double q1 = median(v.begin(), it_first_half);
    double q2 = median(v.begin(), v.end());
    double q3 = median(it_second_half, v.end());
    return make_tuple(q1, q2, q3);
}

int main() {
    vector<double> v = {2, 2, 3, 4, 4, 5, 5, 10};
    auto q = quartiles(v);
    cout << get<0>(q) << "," << get<1>(q) << "," << get<2>(q) << endl;
    return 0;
}

実数用に設計されていますが、整数値に簡単に適応できます（値を最も近い整数に丸めるだけです）。

于 2012-05-26T21:59:44.267 に答える