↓ 跳过正文
流萤厨的小窝

丙加·第8章·答案

·1117 字·6 分钟·
教程

  1. 泛型函数
    引用版本：

    template <typename T>
void mySwap(T &a, T &b) {
    T temp = a;
     a = b;
     b = temp;
}

    指针版本：

    template <typename T>
void mySwap(T *a, T *b) {
    T temp = *a;
    *a = *b;
    *b = temp;
}

    区别在于调用方式，引用：

    mySwap(x, y);  // 直接传递变量本身

    指针：

    mySwap(&x, &y);  // 需要传递变量的地址

    碎碎念：因为引用变量必须绑定一个实际的变量，所以使用引用变量的函数版本没有空指针的危害，更加安全。

  2. 阶乘函数
    （因为涉及 int、double 等很多类型，所以也使用了模板）
    递归版本：

    template <typename T>
T factorialR(T n) {
    if (n <= 1) return 1;
    return n * factorialR(n - 1);
}

    循环（迭代）版本：

    template <typename T>
T factorialI(T n) {
    T result = 1;
    for (T i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

  3. 斐波那契数列：

    朴素版本：

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

    上面的方法 return 前进行了加法运算，所以无法尾递归优化。这个方案的缺点是，如果计算 fibonacciR(5) 就会导致这样的效果：

    第八章-答案-fR 调用图

    共计 67 次调用！事实上，调用次数\(Cn\)满足：\(C(n) = 2 × F(n+1) - 1 = C(n) = 2 \times F(n+1) - 1 = 2 \times \frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}} - 1 \approx 2 × \frac{φ^{n + 1}}{ \sqrt{5} } - 1 \text{，其中} \quad \phi = \frac{1+\sqrt{5}}{2}, \quad \psi = \frac{1-\sqrt{5}}{2}\)，是指数关系！时间复杂度（时间随数据量\(n\)的变化情况）可以记作\(O(2^{n})\)——这基本上很坏的情况了！

    而尾递归优化后的版本，增加了参数来保存额外的信息：

    long long fibonacciTR(int n, long long a = 0, long long b = 1) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fibonacciTR(n - 1, b, a + b);
}

    调用关系：

    第八章-答案-fR 调用图

    这样就变成了线性关系了！

    然后是记忆化：

    long long fibonacciRM(int n) {
    // 静态vector用于记忆化存储，避免重复计算
    // 静态变量参见2.4
    // 或者可以使用全局变量（3.6）
    // 不推荐全局变量，这就像把oo挂在公共场所一样
    static vector<long long> fibonacciMem{0, 1, 1};

    if (n < 0) {
        return -1; // 错误处理
    }

    // 如果vector大小不够，调整大小
    if (fibonacciMem.size() <= n) {
        fibonacciMem.resize(n + 1, 0);
    }

    // 如果未计算过，则递归计算
    if (n > 1 && fibonacciMem[n] == 0) {
        fibonacciMem[n] = fibonacciRM(n - 1) + fibonacciRM(n - 2);
    }

    return fibonacciMem[n];
}

    其实 vector 还需要反复扩容耗时间，这个时候用固定数组更好（$f(93)$ 就超过 long long 了）：

    long long fibonacciRM(int n) {
    // 静态数组，自动初始化为0
    static long long fibonacciMem[100] = {0, 1, 1};

    if (n < 0) {
        return -1; // 错误处理
    }

    // 如果未计算过，则递归计算
    if (n > 1 && fibonacciMem[n] == 0) {
        fibonacciMem[n] = fibonacciRM(n - 1) + fibonacciRM(n - 2);
    }

    return fibonacciMem[n];
}

    最后是迭代版本：

    long long fibonacciI(int n) {
    if (n <= 1) return n;

    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

    读者可以自行感受调用时间，也可以使用下面的代码定量测试：

    #include <iostream>
#include <chrono>
#include <functional>

using namespace std;
using namespace std::chrono;

// 迭代版本
long long fibonacciI(int n) {
    if (n <= 1) return n;

    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

// 朴素递归版本
long long fibonacciR(int n) {
    if (n <= 1) return n;
    return fibonacciR(n - 1) + fibonacciR(n - 2);
}

// 尾递归版本
long long fibonacciTR(int n, long long a = 0, long long b = 1) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fibonacciTR(n - 1, b, a + b);
}

// 记忆递归版本
long long fibonacciRM(int n) {
    static long long fibonacciMem[100] = {0, 1, 1};

    if (n < 0) {
        return -1; 
    }

    if (n > 1 && fibonacciMem[n] == 0) {
        fibonacciMem[n] = fibonacciRM(n - 1) + fibonacciRM(n - 2);
    }

    return fibonacciMem[n];
}

// 测试函数模板
void testFibonacci(const string& name, function<long long(int)> func, int n) {
    cout << "测试 " << name << "..." << endl;

    auto start = high_resolution_clock::now();
    long long result = func(n);
    auto end = high_resolution_clock::now();

    auto duration = duration_cast<microseconds>(end - start);

    cout << "f(" << n << ") = " << result << endl;
    cout << "运行时间: " << duration.count() << " 微秒 (" 
         << duration.count() / 1000.0 << " 毫秒)" << endl;
    cout << "----------------------------------------" << endl;
}

int main() {
    const int n = 40;

    // 测试迭代版本
    testFibonacci("迭代算法", fibonacciI, n);

    // 测试尾递归版本
    // 这里因为TR版本是三个参数（尽管两个是默认）
    // 装不进模板所以使用lambda转换了一下
    testFibonacci("尾递归算法", [](int x) { return fibonacciTR(x); }, n);

    // 测试记忆递归版本
    testFibonacci("记忆递归算法", fibonacciRM, n);

    // 测试朴素递归版本
    testFibonacci("朴素递归算法", fibonacciR, n);

    return 0;
}

    笔者电脑上运行的输出：

    （尾递归会被优化为迭代，而这里迭代可以转换为高速的寄存器操作；记忆递归本来每项都只需要算 1 次，所以耗时都是 0，测不出来）

    测试 迭代算法...
f(40) = 102334155
运行时间: 0 微秒 (0 毫秒)
----------------------------------------
测试 尾递归算法...
f(40) = 102334155
运行时间: 0 微秒 (0 毫秒)
----------------------------------------
测试 记忆递归算法...
f(40) = 102334155
运行时间: 0 微秒 (0 毫秒)
----------------------------------------
测试 朴素递归算法...
f(40) = 102334155
运行时间: 984676 微秒 (984.676 毫秒)
----------------------------------------

    事实上改成 n=100 更炸裂（记得给 fibonacciMem[100] 扩容到 101！）：

    测试 迭代算法...
f(100) = 3736710778780434371
运行时间: 0 微秒 (0 毫秒)
----------------------------------------
测试 尾递归算法...
f(100) = 3736710778780434371
运行时间: 0 微秒 (0 毫秒)
----------------------------------------
测试 记忆递归算法...
f(100) = 3736710778780434371
运行时间: 0 微秒 (0 毫秒)
----------------------------------------
测试 朴素递归算法...
^C（我掐了）

    预计朴素递归要花：\(1.13×10^{18}\)秒，也就是\(3.6 \times 10^{10}\)年（约 360 亿年）。PS：宇宙年龄：138 亿年

  4. 字符串反转

    朴素版本：

    // 动-名命名法
string reverse_stringR(string str) {
    if (str.empty()) return "";

    char last_char = str.back();
    str.pop_back();
    return last_char + reverse_stringR(str);
}

    尾递归优化：

    string reverse_stringTR(string str, string result = "") {
    if (str.empty()) return result;

    char last_char = str.back();
    str.pop_back();
    return reverse_stringTR(str, result + last_char);
}

    碎碎念：

    你肯定注意到了，两次尾递归优化都是把一些初始条件和计算结果放到参数里面传递，这样大大减少了计算次数和性能开销，最重要的是，让编译器可以自动转化为迭代版本。

  5. 汉诺塔问题：

    #include <iostream>

// 全局计数器
// 如果不需要步骤也可以删掉
static int count = 0;

void move(int n, char from, char to) {
    count++;
    std::cout << count << ": Move from " << from << " to " << to << "\n";
}

void hanoi(int n, char source, char auxiliary, char target) {
    if (n == 1) {
        move(n, source, target);
    } else {
        hanoi(n - 1, source, target, auxiliary);
        move(n, source, target);
        hanoi(n - 1, auxiliary, source, target);
    }
}

int main() {
    int n = 3;
    count = 0;
    hanoi(n, 'A', 'B', 'C', count);
    return 0;
}

  6. 退出多重循环

    Lambda 版本：

    int main() {
    vector<vector<string>> classes = {
        {"张三", "李四", "王五"},
        {"赵六", "孙七", "周八"},
        {"吴九", "郑十", "刘一"},
        {"陈二", "黄三", "林四"}
    };

    string target = "郑十";

    [&classes, target]() {
        for (int i = 0; i < classes.size(); i++) {
            for (int j = 0; j < classes[i].size(); j++) {
                if (classes[i][j] == target) {
                    cout << "找到 " << target << " 在班级 " << (i + 1) 
                         << ", 位置 " << (j + 1) << endl;
                    return; // 直接退出所有循环
                }
            }
        }
        cout << "未找到 " << target << endl;
    }();

    return 0;
}

    标志变量版本：

    int main() {
    vector<vector<string>> classes = {
        {"张三", "李四", "王五"},
        {"赵六", "孙七", "周八"},
        {"吴九", "郑十", "刘一"},
        {"陈二", "黄三", "林四"}
    };

    string target = "郑十";
    bool found = false;

    for (int i = 0; i < classes.size() && !found; i++) {
        for (int j = 0; j < classes[i].size() && !found; j++) {
            if (classes[i][j] == target) {
                cout << "找到 " << target << " 在班级 " << (i + 1) 
                     << ", 位置 " << (j + 1) << endl;
                found = true;
            }
        }
    }

    if (!found) {
        cout << "未找到 " << target << endl;
    }

    return 0;
}

    对比可以发现 lambda 版本更简洁、符合直觉。这也是 C++带来的便利之处。另外，大多数时候，编译器会直接将这个临时函数内嵌为循环版本，所以也没有函数调用的开销！这基本就是退出多重循环的版本答案了。

命令提示符@CommandPrompt-Wang
作者
命令提示符@CommandPrompt-Wang