C++ 课堂见闻（2）

什么保留节目

不知道为什么 MathJax 在这里跑的很失败，所以对原文（written in Typora）进行了一定程度的删改以正确显示内容。

关于 ++ 类运算符

结论：++i 是左值，返回的是 i 的地址；i++ 是右值，返回的是 i 的数值。

由于 i++ 会需要开辟临时空间，效率上应该会稍慢。

关于内联函数

见此页，简而言之，inline 会在编译时“建议”编译器会把该函数的代码在调用点复制展开，以减少开销。

据说，如果已定义的函数多于一行，编译器会忽略 inline 限定符。 // 虽然，我无脑inline

一条经验准则：内联那些包含循环或 switch 语句的函数常常是得不偿失（除非在大多数情况下，这些循环或 switch 语句从不被执行）

虚函数和递归函数就不会被正常内联。

• 通常，递归函数不应该声明成内联函数（递归调用堆栈的展开并不像循环那么简单，比如递归层数在编译时可能是未知的，大多数编译器都不支持内联递归函数）。

• 虚函数内联的主要原因则是想把它的函数体放在类定义内，为了图个方便，抑或是当作文档描述其行为，比如精短的存取函数。

关键字 auto

It is said that, 关键字 auto 可以表示一个变量具有自动的生存周期，同级别的关键字还有 static。

但是，auto 的另一个新特性（我记得比上面那个更新）是自动指定数据类型。

根据我的测试，auto 在现在大多数编译器都会解释为自动数据类型，因此已经不再可以显式的定义一个变量的生存周期了。

从 Fibonacci 开始

“求 Fibonacci 数列有四种方法，你晓得么？”——PRJ

锐评下老师的知乎文章啊（

int fib(int n) {
    if (n < 2) return n;
    return fib(n-1) + fib(n-2);
}

所以我们说说尾递归

什么是尾递归？太长不看版

下面参考的是这篇博文。

可以把尾递归看作是可以优化为迭代的递归，条件是递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分。

原理：当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

因此，Fibonacci 数列的递归写法可以用尾递归优化：

int fib_tail(int N, int a, int b){
    if(N == 0) return b;
    return fib_tail(N - 1, a + b, a);
}

时间复杂度和迭代一致，但空间复杂度为O(1)

动态规划？

“动态规划就是记忆化搜索”，我觉得不对。

首先提《算法导论》中的一点：dynamic programming 中的 programming 指的是一种表格法，而非编程。

回到这个命题，我觉得这个回答就是我对这个问题的看法。

DP 并不就是 MS，哪怕 MS 可以解决一部分 DP 的问题。

通项公式好！好……好？

f_n=f_{n-1} + f_{n-2}

Fibonacci 数列的特征根方程为：x^2=x+1，解得 x_1=\frac{1+\sqrt{5}}{2}, x_2=\frac{1-\sqrt{5}}{2}

那么，通项公式可写为 f_n=A·x_1^n+B·x_2^n，通过前两项可待定出 A 和 B 的值。

于是 f_n=\frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]

这只是特征根法求二阶递推式的过程，更加本质，更加线性代数的内容，参见此篇。

由于有 n 次幂，因此直接求解其实不算太快。

不过我又想到了两个东西。

快速平方根

准确的说，应该是快速平方根倒数算法。算法届的传奇，中文维基介绍见此。

简而言之，就是一次迭代牛顿法的产物。深究还有很多内容尚待学习。

详解见此。

矩阵快速幂

高一的时候学的，怎么想也不是特别复杂的东西。

“通常当问题抽象为：f(x)=k_{1}f(n-c_{1})+k_{2}f(n-c_{2})+k_{3}f(n-c_{3})+\dots ，k_{n} 、c_{n} 为常数，而n又较大时，应使用矩阵快速幂。这使得通过有限个状态即可用快速幂求出f(n)的值。”——摘自当时的博客

\begin{bmatrix} f(n) \\\ f(n-1) \end{bmatrix}=\begin{bmatrix} 1 & 1 \\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f(n-1) \\\ f(n-2) \end{bmatrix}

以 Fibonacci 数列为例，可以得到上面这个矩阵形式的递推式。

所以没什么好说的，附上当时的代码。

struct matrix{
    int  mat[MAXN][MAXN];
    void clear(){memset(mat,0,sizeof(mat));}
    void print(){
        for(int i = 1; i <= MAXN; ++i){
            for(int j = 1; j < MAXN; ++j)printf("%d ", mat[i][j]);
            printf("%d\n", mat[i][MAXN]);
        }
    }
}

// 在结构体外重载操作符
// 虽然写法并不好但是能用，毕竟高一时候写的
matrix operator *(matrix A, matrix B){
    matrix C;C.clear();
    for(int i=1;i<=MAXN;i++)for(int j=1;j<=MAXN;j++)for(int tmp=1;tmp<=MAXN;tmp++)
        C.mat[i][j] += A.mat[i][tmp] * B.mat[tmp][j];
    return C;
}

宏定义

• #define toChar(x) #@x，效果就是给 x 加上单引号。
• #define toString(x) #x，效果就是加上双引号。
• #ifdef DEBUG 与 #endif 搭配使用，使得它们框住的代码仅在 #define DEBUG 存在时执行。
• 用 #if，#ifdef，#ifndef，#else，#elif，#endif 完成基本的逻辑控制。

缺省形参

函数声明时，在参数表中加入初始值，该初始值就是该变量的缺省值。

例如：int sum(int a, int b = 10);

注意：缺省值的设置必须从右至左，换言之，int sum(int a = 10, int b); 是不合法的。

泛型编程 / 模板元编程

作为个人开发者使用不多，但是非常重要的特性。

具体参见这篇博客就够了。