CS106B Assignment3

Foreword

记录2022 winter的CS106B Assignment3

The Sierpinski Triangle

递归画出分形

void drawSierpinskiTriangle(GWindow& window,
                            double x0, double y0,
                            double x1, double y1,
                            double x2, double y2,
                            int order) {
    if (order < 0) {
        error ("The order should be greater than or equal to zero.");
    } else if (order == 0) {
        drawTriangle(window, x0, y0, x1, y1, x2, y2);
    } else {
        drawSierpinskiTriangle(window, x0, y0, (x0 + x1) / 2, (y0 + y1) / 2, (x0 + x2) / 2, (y0 + y2) / 2, order - 1);
        drawSierpinskiTriangle(window, (x1 + x0) / 2, (y1 + y0) / 2, x1, y1, (x1 + x2) / 2, (y1 + y2) / 2, order - 1);
        drawSierpinskiTriangle(window, (x2 + x0) / 2, (y2 + y0) / 2, (x2 + x1) / 2, (y2 + y1) / 2, x2, y2, order - 1);
    }
    return;
}

Human Pyramids

需要记忆化的递归

Map<pair<int, int>, int> memo;

double weightOnBackOf(int row, int col, int pyramidHeight) {
    if (row < 0 || col < 0 || col > row || row >= pyramidHeight || pyramidHeight <= 0) {
        error("out of bounds");
    } else if (row == 0 && col == 0) {
        return 0.0;
    } else if (memo.containsKey({row, col})) {
        return memo[{row, col}];
    } else {
        double up = 0.0, upLeft = 0.0;
        if (row - 1 >= col) {
            up = 160 + weightOnBackOf(row - 1, col, pyramidHeight);
        }
        if (row >= col && col >= 1) {
            upLeft = 160 + weightOnBackOf(row - 1, col - 1, pyramidHeight);
        }
        return memo[{row, col}] = (up + upLeft) / 2.0;
    }
}

What Are YOU Doing?

枚举子集的递归

Set<string> allEmphasesOf(const string& sentence) {
    auto words = tokenize(sentence);
    Set<string> res;
    auto dfs = [&](auto self, int u, string cur) -> void {
        if (u == words.size()) {
            res.add(cur);
            return;
        }
        auto word = words[u];
        if (!isalpha(word[0])) {
            self(self, u + 1, cur + word);
            return;
        } else {
            self(self, u + 1, cur + toLowerCase(word));
            self(self, u + 1, cur + toUpperCase(word));
            return;
        }
    };
    dfs(dfs, 0, "");
    return res;
}

Shift Scheduling

递归找最佳排班方案，需要边递归边对时间限制和重叠限制进行剪枝不然大Case会卡死

写的有点丑，不是很懂为什么参数里$shifts$要用$Set$存

Set<Shift> highestValueScheduleFor(const Set<Shift>& shifts, int maxHours) {
    if (maxHours < 0) {
        error("The maxHour should be greater than or equal to zero.");
    }
    Vector<Shift> shiftsList;
    for (auto shift : shifts) {
        shiftsList.add(shift);
    }
    Set<Shift> res;
    Vector<Shift> tmp;
    int best = 0;
    auto dfs = [&](auto self, int u, int curTime) -> void {
        if (u == shiftsList.size()) {
            int val = 0, time = 0;
            for (int i = 0; i < tmp.size(); ++i) {
                val += valueOf(tmp[i]);
                time += lengthOf(tmp[i]);
                if (time > maxHours) {
                    return;
                }
            }
            if (val > best) {
                best = val;
                res.clear();
                for (auto shift : tmp) {
                    res.add(shift);
                }
            }
            return;
        }
        self(self, u + 1, curTime);
        bool ok = true;
        for (int i = 0; i < tmp.size(); ++i) {
            if (overlapsWith(shiftsList[u], tmp[i])) {
                ok = false;
                break;
            }
        }
        if (ok && curTime + lengthOf(shiftsList[u]) <= maxHours) {
            tmp.add(shiftsList[u]);
            self(self, u + 1, curTime + lengthOf(shiftsList[u]));
            tmp.remove(tmp.size() - 1);
        }
        return;
    };
    dfs(dfs, 0, 0);
    return res;
}

效果