交付递归分治加记忆化

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

这是这条路线的最终作品。阶乘（记深度）、分治求和求最大、朴素斐波那契（计数）已经写好；补全记忆化斐波那契和循环版阶乘，然后一次验完五条：fact(5) 是 120 且最大深度 5；分治求和求最大都和标准库一致；朴素 fib(6) 是 8、调用 25 次；记忆化 fib(6) 还是 8、只调用 7 次；循环版阶乘结果相同、最大深度只有 1。五条全过输出 验收通过，否则输出 验收失败。

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

提交你的答案

请登录后提交答案。

去登录

← 第四步加上记忆化 check 为什么用随机数据 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

int rec_d = 0, loop_d = 0, naive_calls = 0, memo_calls = 0;
vector<long long> memo(50, -1);

long long fact(int n, int d) {
    if (d > rec_d) rec_d = d;
    if (n <= 1) return 1;
    return n * fact(n - 1, d + 1);
}

long long fact_loop(int n, int d) {
    // TODO: 先拿 d 更新 loop_d，再用循环算 n 的阶乘
    return -1;
}

int dsum(const vector<int>& a, int l, int r) {
    if (r - l == 0) return 0;
    if (r - l == 1) return a[l];
    int m = (l + r) / 2;
    return dsum(a, l, m) + dsum(a, m, r);
}

int dmax(const vector<int>& a, int l, int r) {
    if (r - l == 1) return a[l];
    int m = (l + r) / 2;
    int left = dmax(a, l, m);
    int right = dmax(a, m, r);
    return left > right ? left : right;
}

long long fib_naive(int n) {
    naive_calls++;
    if (n <= 1) return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

long long fib_memo(int n) {
    // TODO: 命中 memo 直接返回（不计数）；没命中 memo_calls 加一，算完存进 memo[n]
    return 0;
}

int main() {
    vector<int> a = {17, 24, 15, 13, 23};
    vector<bool> checks;
    checks.push_back(fact(5, 1) == 120 && rec_d == 5);
    checks.push_back(dsum(a, 0, 5) == accumulate(a.begin(), a.end(), 0) && dmax(a, 0, 5) == *max_element(a.begin(), a.end()));
    checks.push_back(fib_naive(6) == 8 && naive_calls == 25);
    checks.push_back(fib_memo(6) == 8 && memo_calls == 7);
    checks.push_back(fact_loop(5, 1) == 120 && loop_d == 1);
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

🔒 登录并作答后可看讨论