交付五条验收一起过

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

最后一步：把「设计 + 证明 + 复杂度」收成五条验收条款：对拍、不变式保持、全负数组也对、比较次数正好是 n-1、前四条全成立。输出如 过/过/过/过/过。

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

提交你的答案

请登录后提交答案。

去登录

← 第四步复杂度依据找到反例之后先做什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

int find_max(const vector<int>& a) {          // 自己设计的算法：一趟扫出最大值
    int best = a[0];
    for (size_t i = 1; i < a.size(); i++) {
        if (a[i] > best) best = a[i];
    }
    return best;
}

const vector<int> DATA = {17, 24, 15, 13, 23};
const vector<int> NEG = {-17, -24, -15, -13, -23};

int count_cmp(const vector<int>& a) {
    int c = 0;
    for (size_t i = 1; i < a.size(); i++) c++;
    return c;
}

int main() {
    vector<int> p = DATA;
    sort(p.begin(), p.end());
    bool c1 = true;
    do {
        if (find_max(p) != *max_element(p.begin(), p.end())) c1 = false;
    } while (next_permutation(p.begin(), p.end()));                               // 对拍
    bool c2 = true;
    for (size_t k = 1; k <= DATA.size(); k++) {
        vector<int> pre(DATA.begin(), DATA.begin() + k);
        if (find_max(pre) != *max_element(pre.begin(), pre.end())) c2 = false;  // 不变式保持
    }
    // TODO: c3——全负数组上也对（初始化没写死成 0）
    bool c3 = false;
    // TODO: c4——比较次数正好是 DATA.size() - 1（复杂度依据）
    bool c4 = false;
    // TODO: c5——前四条全部成立
    bool c5 = false;
    bool all[5] = {c1, c2, c3, c4, c5};
    for (int k = 0; k < 5; k++) cout << (k ? "/" : "") << (all[k] ? "过" : "不过");
    cout << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

交付五条验收一起过

更多题目

全部评论