期望正好等于那个平均

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

随机快排的期望比较次数（expect(5)），和「固定取第一个」在全部 120 种输入上的平均，把这两个数比一比。用分数算，别用浮点。输出「期望的分子/分母/相等或不等」。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 最坏输入里就有有序的期望不随输入而变 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

#include <numeric>

struct Frac {
    long long p, q;                          // 分数 p/q，始终约到最简
};

Frac make(long long p, long long q) {
    long long g = std::gcd(p, q);
    return {p / g, q / g};
}

Frac add(Frac a, Frac b) { return make(a.p * b.q + b.p * a.q, a.q * b.q); }

Frac expect(int k) {                          // 随机枢轴快排的期望比较次数（精确分数）
    static vector<Frac> memo(20, Frac{-1, 1});
    if (k <= 1) return {0, 1};
    if (memo[k].p >= 0) return memo[k];
    Frac s = {0, 1};
    for (int t = 0; t < k; t++) s = add(s, add(expect(t), expect(k - 1 - t)));
    return memo[k] = add(make(k - 1, 1), make(s.p, s.q * k));
}

void qs_go(const vector<int>& x, int& c) {
    if (x.size() <= 1) return;
    int p = x[0];                            // 总是拿第一个当枢轴
    c += (int)x.size() - 1;
    vector<int> lo, hi;
    for (size_t k = 1; k < x.size(); k++) (x[k] < p ? lo : hi).push_back(x[k]);
    qs_go(lo, c);
    qs_go(hi, c);
}

int qs_cmp(const vector<int>& a) {
    int c = 0;
    qs_go(a, c);
    return c;
}

vector<vector<int>> all_perms() {
    vector<int> p = {0, 1, 2, 3, 4};
    vector<vector<int>> out;
    do { out.push_back(p); } while (next_permutation(p.begin(), p.end()));
    return out;
}

int main() {
    // TODO: 固定枢轴在全部 120 种输入上的平均（用 make(总和, 120)，别用浮点）
    Frac avg = {0, 1}, e = expect(5);
    // TODO: 两个分数相等就输出「相等」，否则「不等」
    string verdict = "不等";
    (void)avg;
    cout << e.p << "/" << e.q << "/" << verdict << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

期望正好等于那个平均

更多题目

全部评论