一、前言

  本文适合对算法处于朦胧期的初学者，文字浅显易懂，并且配有生动有趣的动图，也是作者呕心沥血之作，希望对刚入大学，或者职场上想要涉足算法的青年同僚有所启示。
  学习算法，任何时候都不嫌晚，大不了就是大器晚成而已，所以无论你是30岁，40岁，50岁，甚至60岁，只要下了决心，就已经成功了一半！本文的故事发生在 ❤️学姐教你 10 道题搞定 c 语言❤️ 的两年后，剧情扑朔迷离，作者至今回忆起来还历历在目。

二、朝思暮想

• 自从上次一别，不知何时才能相见，不免有些感伤。于是，那天晚上，我，辗转反侧，彻夜难眠，寝不安席，食无甘味。
  不太聪明的亚子
• 从来没有一个女孩子可以让我如此朝思暮想，魂牵梦萦。
• 可能是因为她还没有把她的毕生算法教会给我，怎么一声不吭就人间蒸发了呢！我不甘心！
• 就算是天涯海角，我也要找到你！
  
• 终于，在一个夜黑风高的晚上，让我在睡梦中见到了她，梦里的她比现实中还要逗比。竟然给我写下了八行代码！
  
• 也就是因为那个晚上，成就了我后来的 ❤️《夜深人静写算法》❤️
• 她告诉我，一行代码代表一个算法！我觉得她在侮辱我的智商！
• 那天晚上大致是这样的 … …

三、南柯一梦

四、梦中的梦中

• 哎，越想越不对劲！
• 所以我打算继续睡，看看能不能继续梦到学姐。
• 果然……功夫不负有心人……
  
• 学姐出现了！！！

• 学姐还是像往常一样，心思缜密，替人着想，越来越崇拜她了。

五、梦中人的梦中

算法一

【例题1】给定 $n(n\le 65535)$，求 ${\sum }_{i=1}^{n}i=1+2+...+n$。

• 这是一个等差数列！
• 我直接用等差数列的求和公式就行了。

int sum(int n) {
    return n * (n + 1) / 2;
}

• 然后我调试了一下，发现：
  
• 当 $n=65535$ 时，输出的竟然是负数！

原因是因为 $n\ast (n+1)=65535\ast 65536=(2^{16}-1)2^{16}=2^{32}-2^{16}$，而 $int$ 能够表示的最大值为 $2^{31}-1$，所以产生了溢出。就变成了负数。至于为什么溢出会变成负数，可以了解补码相关的知识：c++ 补码详解。

• 这里只需要对 $n$ 进行奇偶性判定，将除法放在乘法之前，就可以防止溢出了。即：
• $$sum(n)=\{\begin{array}{ll}(n+1)/2\times n& n为奇数\\ n/2\times (n+1)& n为偶数\end{array}$$
• c++ 实现如下：

int sum(int n) {
    if(n % 2 == 1) {
        return (n + 1) / 2 * n;
    }else {
        return n / 2 * (n + 1);
    }
}

• 然后我们再通过三目运算符写成一行代码，如下：

int sum(int n) {
    return (n%2) ? (n+1)/2*n : n/2*(n+1);
}

这里的 condition ? a : b是 c/c++ 中的三目运算符，含义是根据表达式condition的值的真或假，选择返回 a还是 b。由于对于一个数 $x$，$x$ 非0就是真，为0就是假，所以可以直接省略 x == 0的判断。

• 通过这段代码，我了解了 32位整数的溢出、补码表示、三目运算符、表达式真值的省略写法。

算法二

【例题2】给定 $n(n<16)$，求 ${\prod }_{i=1}^{n}i=1\times 2\times ...\times n$。

• 由于 $n$ 比较小，所以我打算直接暴力枚举，大概可以写成这样：

int sum(int n) {
    int s = 1;
    for(int i = 1; i <= n; ++i) {
        s *= i;
    }
    return s;
}

• 但是学姐说的一行代码好像比较难办到，我继续压缩，把 s这个变量放到循环体内和i一起初始化，并且把乘法和循环放到同一行，变成了下面这副样子。

int sum(int n) {
    for(int s = 1, i = 1; i <= n; ++i) s *= i;
    return s;
}

• 这时候发现编译不过！！！
  
• 原因是：s的作用域在循环体内，所以无法在循环体外部进行使用，但是我们这个函数有需要有一个返回值，总不能把函数体给返回吧？这可如何是好！

• 由于那时候，我对递归还没有什么概念，所以一脸懵逼。

• 我还是听不懂……

• 这下我就懂了！
• 我们可以定义这么一个函数 $f(x)=1\times 2\times 3\times ...\times x$，其中 $x\ge 0$。
• 当 $x>0$ 时，代入 $(x-1)$，显然有 $f(x-1)=1\times 2\times 3\times ...\times (x-1)$；
• 于是，可以得到：
• $$\frac{f(x)}{f(x-1)}=x$$
• 由于 $f(x-1)>0$， 等式两边可以同时乘上 $f(x-1)$，很容易得出递推公式如下：
• $$f(x)=\{\begin{array}{ll}1& (x=0)\\ f(x-1)\times x& (x>0)\end{array}$$
• 所以，翻译成 c/c++ 的语言，就可以写成这样：

int f(int x) {
    if(x == 0) {
        return 1;
    }else {
        return f(x-1) * x;
    }
}

• 然后利用三目运算符，改成一行代码，得到：

int f(int x) {
    return x ? f(x-1) * x : 1;
}

• 通过这段代码，我了解了 递推公式 和 递归调用。

算法三

【例题3】现在有一个 $n(n\le 10000)$ 个元素的数组 $a[i]$，但是我们已知的是前 $i$ 个元素的和 $f_{[}i](1\le i\le n,1\le f[i]\le 100000)$，然后给出 $Q(Q\le 1000000)$ 次询问 $(l,r)(1\le l\le r\le n)$，求 ${\sum }_{i=l}^{r}a[i]$。

• 首先根据题意，得知：$$a[i]=f[i]-f[i-1]$$
• 可以用一个for循环计算出所有a[i]的值。

const int maxn = 100005;
void preCalculate(int f[maxn]) {
    int a[maxn];
    for(int i = 1; i <= n; ++i) {
        a[i] = f[i] - f[i-1];
    }
}

• 然后对于每次循环，循环统计 $a[i]$ 的累加和，返回答案。

int get(int a[], int l, int r) {
    int s = 0;
    for(int i = l; i <= r; ++i) {
        s += a[i];
    }
    return s;
}

• 事实的确如此，如果每个询问都是 1 到 $n$ 的话，时间复杂度就会变成 $O(nQ)$，总的数量级在 $10^{10}$，比较难承受了。
• 再仔细想想，不难发现。我们可以将要求的结果定义为函数 $g(l,r)$，则有：
• $$\begin{array}{rl}g(l,r)& =a[l]+a[l+1]+...+a[r]\\ & =(f[l]-f[l-1])+(f[l+1]-f[l])+...+(f[r]-f[r-1])\\ & =f[r]-f[l-1]\end{array}$$
• 而 $f[l]$ 和 $f[r]$ 都是题目给出的，神奇！
• 直接得到一行代码求解：

int g(int l, int r) {
    return f[r] - f[l-1];
}

• 学姐估计是太激动，本来想夸我 “数学底子不错”，结果说成了 “数学底子不过” …… 只要她不尴尬，尴尬的就是我 ……
• 通过这段代码，我了解了 前缀和 和 差分法。

算法四

【定义1】对于一个数 $a$，如果有数 $b$ 能够整除 $a$，则称 $a$ 是 $b$ 的倍数，$b$ 是 $a$ 的约数。
【定义2】如果一个数 $c$ 同时是数 $a$ 和 数 $b$ 的约数，则称 $c$ 是 $a$ 和 $b$ 的公约数。
【定义3】如果 $c$ 是 $a$ 和 $b$ 中最大的公约数，则称 $c$ 为 $a$ 和 $b$ 的最大公约数，记为 $c=gcd(a,b)$。

• 例如，1，2，4 均为 8 和 12 的公约数，最大的公约数就是 4。
  

• 我可以枚举所有 $a$ 的约数，然后再判断它是不是 $b$ 的约数，从而找到最大的那个满足条件的约数就是答案了。算法实现如下：

int gcd(int a, int b) {
    int maxret = 1;
    for(int i = 2; i <= a; ++i) {
        if(a % i == 0 && b % i == 0)
            maxret = max(maxret, i);
    }
}

• 这个算法的时间复杂度是 $O(n)$ 的。

• 以下这段话出自当年学姐的口中：

  首先，当 $b\ne 0$ 时，我们令 $a=kb+r$，其中 $k=\lfloor \frac{a}{b}\rfloor$，$r=amodb$，并且满足 $(0\le r<b)$，当一个数 $c$，是 $a$ 的约数，也是 $b$ 的约数，则必然也是 $a-kb$ 的约数，即 $r$ 的约数。自然 $a$ 和 $b$ 的公约数 也就是 $b$ 和 $r$ 的公约数。
  所以，$a$ 和 $b$ 的最大公约数 $=$ $b$ 和 $r$ 的最大公约数。表示为：$$gcd(a,b)=gcd(b,amodb)$$

• 但是我们的假设是建立在 $b\ne 0$ 上的，而 $b=0$ 的情况，答案显然就是 $a$ 了。于是对于上面的 $gcd$ 函数，我们可以表示成如下递归式：
• $$gcd(a,b)=\{\begin{array}{ll}a& b=0\\ gcd(b,amodb)& b\ne 0\end{array}$$
• 写成 c++ 代码就是：

int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

• 这里 !是 c/c++ 中的表达式取非的意思，即 真变假，假变真，且 c/c++ 中 0 为假，非0为真；%是取模，即 $mod$ 的程序语法。
• 学姐真是太装逼牛逼了！又是一行代码让我学到了这么多知识，满满的干货！

• 这时候，天上掉下来一座长城！
  
• 果然是说曹操，曹操就到啊！
• 难道，这个梦是在暗示我赶紧把学姐的算法学完吗？？？

六、梦不到，被吹散

• 充满求知欲的我不甘心，还想继续睡。可再也梦不到学姐了。
  
  
• 我逐渐陷入沉思，等我反应过来的时候，已然到了晚上，今天的课又没去上！
• 我不甘心啊！ 学姐快把算法传授给我吧！

七、往事如风

• 十年后的今天再回首，恍如隔世，学姐当时托梦，的确让我受益匪浅，这也是我后来誓要写成❤️《夜深人静写算法》❤️系列最大的动力。这个系列目前还在紧锣密鼓的更新中，适合高中IOer，大学Acmer，以及职场的有志青年学习算法之用。
• 至于学姐后来到底有没有托梦于我，我会在 《❤️学姐说她用 8 行代码写了 8 个算法（下）❤️》 里继续更新，如果有想帮我想剧情的，亦或是对学姐的钦慕之情，都可以在评论区留言告诉我， 学姐是我的，也是你的。

• 本文通过一些简单的算法，对 c/c++ 的语言性质进行了一些温故而知新，希望对各位初学者有所帮助。
• 以下是本文涉及到的知识点，最后再进行一个总结归纳。

1、知识点回顾

2、温故而知新

// 算法1：求和公式
int sum(int n) {
    return (n%2) ? (n+1)/2*n : n/2*(n+1);
}
// 算法2：递归求阶乘
int f(int x) {
    return x ? f(x-1) * x : 1;
}
// 算法3：差分法求部分和
int g(int l, int r) {
    return f[r] - f[l-1];
}
// 算法4：递归求最大公约数
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

原文链接:https://blog.csdn.net/WhereIsHeroFrom/article/details/117596791