一、前言

??本文適合對演算法處于朦朧期的初學者，文字淺顯易懂，并且配有生動有趣的動圖，也是作者嘔心瀝血之作，希望對剛入大學，或者職場上想要涉足演算法的青年同僚有所啟示，
??學習演算法，任何時候都不嫌晚，大不了就是大器晚成而已，所以無論你是30歲，40歲，50歲，甚至60歲，只要下了決心，就已經成功了一半！本文的故事發生在 ??學姐教你 10 道題搞定 c 語言?? 的兩年后，劇情撲朔迷離，作者至今回憶起來還歷歷在目，

二、朝思暮想

• 自從上次一別，不知何時才能相見，不免有些感傷，于是，那天晚上，我，輾轉反側，徹夜難眠，寢不安席，食無甘味，
  不太聰明的亞子
• 從來沒有一個女孩子可以讓我如此朝思暮想，魂牽夢縈，
• 可能是因為她還沒有把她的畢生演算法教會給我，怎么一聲不吭就人間蒸發了呢！我不甘心！
• 就算是天涯海角，我也要找到你！
  
• 終于，在一個夜黑風高的晚上，讓我在睡夢中見到了她，夢里的她比現實中還要逗比，竟然給我寫下了八行代碼！
  
• 也就是因為那個晚上，成就了我后來的 ??《夜深人靜寫演算法》??
• 她告訴我，一行代碼代表一個演算法！我覺得她在侮辱我的智商！
• 那天晚上大致是這樣的 … …

三、南柯一夢

四、夢中的夢中

• 哎，越想越不對勁！
• 所以我打算繼續睡，看看能不能繼續夢到學姐，
• 果然……功夫不負有心人……
  
• 學姐出現了！！！

• 學姐還是像往常一樣，心思縝密，替人著想，越來越崇拜她了，

五、夢中人的夢中

演算法一

【例題1】給定 n ( n ≤ 65535 ) n(n \le 65535) n(n≤65535)，求 ∑ i = 1 n i = 1 + 2 + . . . + n \sum_{i=1}^n i = 1 + 2 + ... + n ∑i=1n?i=1+2+...+n，

• 這是一個等引數列！
• 我直接用等引數列的求和公式就行了，

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

• 然后我除錯了一下，發現：
  
• 當 n = 65535 n=65535 n=65535 時，輸出的竟然是負數！

原因是因為 n ? ( n + 1 ) = 65535 ? 65536 = ( 2 16 ? 1 ) 2 16 = 2 32 ? 2 16 n * (n + 1) = 65535 * 65536 = (2^{16}-1)2^{16} = 2^{32} -2^{16} n?(n+1)=65535?65536=(216?1)216=232?216，而 i n t int int 能夠表示的最大值為 2 31 ? 1 2^{31}-1 231?1，所以產生了溢位，就變成了負數，至于為什么溢位會變成負數，可以了解補碼相關的知識：c++ 補碼詳解，

• 這里只需要對 n n n 進行奇偶性判定，將除法放在乘法之前，就可以防止溢位了，即：
• s u m ( n ) = { ( n + 1 ) / 2 × n n 為 奇 數 n / 2 × ( n + 1 ) n 為 偶 數 sum(n) = \begin{cases} (n+1)/2 \times n & n 為奇數 \\ n/2 \times (n+1) & n 為偶數 \end{cases} sum(n)={(n+1)/2×nn/2×(n+1)?n為奇數n為偶數?
• 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 x， x x x 非0就是真，為0就是假，所以可以直接省略 x == 0的判斷，

• 通過這段代碼，我了解了 32位整數的溢位、補碼表示、三目運算子、運算式真值的省略寫法，

演算法二

【例題2】給定 n ( n < 16 ) n(n \lt 16) n(n<16)，求 ∏ i = 1 n i = 1 × 2 × . . . × n \prod_{i=1}^n i = 1 \times 2 \times ... \times n ∏i=1n?i=1×2×...×n，

• 由于 n 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 × 2 × 3 × . . . × x f(x) = 1 \times 2 \times 3 \times ... \times x f(x)=1×2×3×...×x，其中 x ≥ 0 x \ge 0 x≥0，
• 當 x > 0 x > 0 x>0 時，代入 ( x ? 1 ) (x-1) (x?1)，顯然有 f ( x ? 1 ) = 1 × 2 × 3 × . . . × ( x ? 1 ) f(x-1) = 1 \times 2 \times 3 \times ... \times (x-1) f(x?1)=1×2×3×...×(x?1)；
• 于是，可以得到：
• f ( x ) f ( x ? 1 ) = x \frac {f(x)} {f(x-1)} = x f(x?1)f(x)?=x
• 由于 f ( x ? 1 ) > 0 f(x-1) > 0 f(x?1)>0， 等式兩邊可以同時乘上 f ( x ? 1 ) f(x-1) f(x?1)，很容易得出遞推公式如下：
• f ( x ) = { 1 ( x = 0 ) f ( x ? 1 ) × x ( x > 0 ) f(x) = \begin{cases} 1 & (x = 0) \\ f(x-1) \times x & (x > 0)\end{cases} f(x)={1f(x?1)×x?(x=0)(x>0)?
• 所以，翻譯成 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 ≤ 10000 ) n(n \le 10000) n(n≤10000) 個元素的陣列 a [ i ] a[i] a[i]，但是我們已知的是前 i i i 個元素的和 f [ i ] ( 1 ≤ i ≤ n , 1 ≤ f [ i ] ≤ 100000 ) f_[i](1 \le i \le n, 1 \le f[i] \le 100000) f[?i](1≤i≤n,1≤f[i]≤100000)，然后給出 Q ( Q ≤ 1000000 ) Q(Q \le 1000000) Q(Q≤1000000) 次詢問 ( l , r ) ( 1 ≤ l ≤ r ≤ n ) (l, r) (1 \le l \le r \le n) (l,r)(1≤l≤r≤n)，求 ∑ i = l r a [ i ] \sum_{i=l}^r a[i] ∑i=lr?a[i]，

• 首先根據題意，得知： a [ i ] = f [ i ] ? f [ i ? 1 ] a[i] = f[i] - f[i-1] 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 ] a[i] 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 n n 的話，時間復雜度就會變成 O ( n Q ) O(nQ) O(nQ)，總的數量級在 1 0 10 10^{10} 1010，比較難承受了，
• 再仔細想想，不難發現，我們可以將要求的結果定義為函式 g ( l , r ) g(l ,r) g(l,r)，則有：
• 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 ] \begin{aligned}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{aligned} 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]?
• 而 f [ l ] f[l] f[l] 和 f [ r ] f[r] f[r] 都是題目給出的，神奇！
• 直接得到一行代碼求解：

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

• 學姐估計是太激動，本來想夸我 “數學底子不錯”，結果說成了 “數學底子不過” …… 只要她不尷尬，尷尬的就是我 ……
• 通過這段代碼，我了解了 前綴和 和 差分法，

演算法四

【定義1】對于一個數 a a a，如果有數 b b b 能夠整除 a a a，則稱 a a a 是 b b b 的倍數， b b b 是 a a a 的約數，
【定義2】如果一個數 c c c 同時是數 a a a 和 數 b b b 的約數，則稱 c c c 是 a a a 和 b b b 的公約數，
【定義3】如果 c c c 是 a a a 和 b b b 中最大的公約數，則稱 c c c 為 a a a 和 b b b 的最大公約數，記為 c = g c d ( a , b ) c = gcd(a, b) c=gcd(a,b)，

• 例如，1，2，4 均為 8 和 12 的公約數，最大的公約數就是 4，
  

• 我可以列舉所有 a a a 的約數，然后再判斷它是不是 b b 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 ) O(n) O(n) 的，

• 以下這段話出自當年學姐的口中：

??首先，當 b ≠ 0 b \neq 0 b?=0 時，我們令 a = k b + r a = kb + r a=kb+r，其中 k = ? a b ? k = \lfloor \frac a b \rfloor k=?ba??， r = a m o d b r = a \ mod \ b r=a mod b，并且滿足 ( 0 ≤ r < b ) (0 \le r < b) (0≤r<b)，當一個數 c c c，是 a a a 的約數，也是 b b b 的約數，則必然也是 a ? k b a-kb a?kb 的約數，即 r r r 的約數，自然 a a a 和 b b b 的公約數 也就是 b b b 和 r r r 的公約數，
??所以， a a a 和 b b b 的最大公約數 = = = b b b 和 r r r 的最大公約數，表示為： g c d ( a , b ) = g c d ( b , a m o d b ) gcd(a, b) = gcd(b, a \ mod \ b) gcd(a,b)=gcd(b,a mod b)

• 但是我們的假設是建立在 b ≠ 0 b \neq 0 b?=0 上的，而 b = 0 b=0 b=0 的情況，答案顯然就是 a a a 了，于是對于上面的 g c d gcd gcd 函式，我們可以表示成如下遞回式：
• g c d ( a , b ) = { a b = 0 g c d ( b , a m o d b ) b ≠ 0 gcd(a,b) = \begin{cases} a & b=0\\ gcd(b, a \ mod \ b) & b \neq 0 \end{cases} gcd(a,b)={agcd(b,a mod b)?b=0b?=0?
• 寫成 c++ 代碼就是：

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

• 這里 !是 c/c++ 中的運算式取非的意思，即 真變假，假變真，且 c/c++ 中 0 為假，非0為真；%是取模，即 m o d mod 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);
}