深海游弋的鱼 – 默默的点滴

保持函数依赖的分解

大部分是对一个关系模式分解成两个模式的考察，分解为三个以上模式时无损分解和保持依赖的判断比较复杂，考的可能性不大，因此我们只对“一个关系模式分解成两个模式”这种类型的题的相关判断做一个总结。

以下的论述都基于这样一个前提：
R是具有函数依赖集F的关系模式，（R1 ，R2）是R的一个分解。

首先我们给出一个看似无关却非常重要的概念：属性集的闭包。
令α为一属性集。我们称在函数依赖集F下由α函数确定的所有属性的集合为F下α的闭包，记为α+ 。
下面给出一个计算α+的算法，该算法的输入是函数依赖集F和属性集α，输出存储在变量result中。
算法一：
result:=α;
while(result发生变化)do
    for each 函数依赖β→γ in F do
    begin
        if β⊆result then result:=result∪γ;
    end

属性集闭包的计算有以下两个常用用途：
·判断α是否为超码，通过计算α+（α在F下的闭包），看α+ 是否包含了R中的所有属性。若是，则α为R的超码。
·通过检验是否β⊆α+，来验证函数依赖是否成立。也就是说，用属性闭包计算α+，看它是否包含β。

看一个例子吧，2005年11月系分上午37题：

● 给定关系R(A1，A2，A3，A4)上的函数依赖集F={A1→A2，A3→A2，A2→A3，A2→A4}，R的候选关键字为________。
（37）A. A1 　B. A1A3 　C. A1A3A4 　D. A1A2A3

首先我们按照上面的算法计算A1+ 。
result=A1，
由于A1→A2，A1⊆result，所以result=result∪A2=A1A2
由于A2→A3，A2⊆result，所以result=result∪A3=A1A2A3
由于A2→A4，A2⊆result，所以result=result∪A3=A1A2A3A4
由于A3→A2，A3⊆result，所以result=result∪A2=A1A2A3A4

通过计算我们看到，A1+ =result={A1A2A3A4}，所以A1是R的超码，理所当然是R的候选关键字。此题选A 。

好了，有了前面的铺垫，我们进入正题。

无损分解的判断。
如果R1∩R2是R1或R2的超码，则R上的分解（R1，R2）是无损分解。这是一个充分条件，当所有的约束都是函数依赖时它才是必要条件（例如多值依赖就是一种非函数依赖的约束），不过这已经足够了。

保持依赖的判断。
如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（这是一个充分条件）。
如果上述判断失败，并不能断言分解不是保持依赖的，还要使用下面的通用方法来做进一步判断。
该方法的表述如下：
算法二：
对F上的每一个α→β使用下面的过程：
result:=α;
while(result发生变化)do
    for each 分解后的Ri
        t=(result∩Ri)+ ∩Ri
        result=result∪t

这里的属性闭包是在函数依赖集F下计算出来的。如果result中包含了β的所有属性，则函数依赖α→β。分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。

下面给出一个例题，2006年5月系分上午43题：

●设关系模式R<U, F>，其中U=｛A, B, C, D, E｝，F＝{A→BC，C→D，BC→E，E→A｝，则分解ρ={R1（ABCE），R2（CD）｝满足（43）。
（43） A．具有无损连接性、保持函数依赖
              B．不具有无损连接性、保持函数依赖
              C．具有无损连接性、不保持函数依赖
              D．不具有无损连接性、不保持函数依赖

先做无损链接的判断。R1∩R2={C}，计算C+。

Result=C
由于C→D，C∈result，所以result=result∪D=CD
可见C是R2的超码，该分解是一个无损分解。

再做保持依赖的判断。
A→BC，BC→E， E→A都在R1上成立（也就是说每一个函数依赖左右两边的属性都在R1中），C→D在R2上成立，因此给分解是保持依赖的。

选A。

再看一个复杂点的例题。2007年5月数工40-41题。

●给定关系模式R<U, F>，U=｛A, B, C, D, E｝，F＝{B→A，D→A，A→E，AC→B｝，其候选关键字为
（40），则分解ρ={R1（ABCE），R2（CD）｝满足（41）。
（40） A．ABD
              B．ABE
              C．ACD
              D．CD
（41） A．具有无损连接性、保持函数依赖
              B．不具有无损连接性、保持函数依赖
              C．具有无损连接性、不保持函数依赖
              D．不具有无损连接性、不保持函数依赖

看见了吧，和前面一题多么的相像！
对于第一问，分别计算ABCD四个选项的闭包，
（ABD）+ = { ABDE }
（ABE）+ = { ABE }
（ACD）+ = { ABCDE }
（CD）+ = { ABCDE }
选D。

再看第二问。
先做无损链接的判断。R1∩R2={C}，计算C+。

result=C
因此C既不是R1也不是R2的超码，该分解不具有无损分解性。

再做保持依赖的判断。
B→A，A→E，AC→B在R1上成立，D→A在R1和R2上都不成立，因此需做进一步判断。
由于B→A，A→E，AC→B都是被保持的（因为它们的元素都在R1中），因此我们要判断的是D→A是不是也被保持。

对于D→A应用算法二：
result=D
对R1，result∩R1=ф（空集，找不到空集的符号，就用这个表示吧），t=ф，result=D
再对R2，result∩R2=D，D+ =ADE ，t=D+ ∩R2=D，result=D
一个循环后result未发生变化，因此最后result=D，并未包含A，所以D→A未被保持，该分解不是保持依赖的。

选D。

参考链接

笛卡尔乘积

笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尔积（Cartesian product），又称直积，表示为X×Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。

矩阵的笛卡尔乘积就是矩阵的直积

讲到笛卡尔乘积，就难免会提到数据库中的 "自然连接(⋈)"。

要求：连接两个表 R ⋈ S
(表中标黄的数据后面会说到)

先看两个表头，发现A C是重复出现的

所以连接后，新表头为

然后把A C这两列单独拎出来，如下

发现有两组相同的，（也就是上面标红的数据）
所以这两个表连接之后只有两条记录。

此时，可以做出下图

这时候从原来的R表、S表中找到对应数据填上

这样表格就完成了。

然后根据上述过程，尝试完成下面的例题：

结果：

我们还可以知道当R和S没有公共属性时，则R⋈S = RXS
（没有公共属性，即每个属性都有它们唯一确定的值。所以RXS就没有需要划去的，也没有相同属性需要整合）

参考链接

向量与矩阵相乘

最近在看"程序员的数学"系列的"线性代数"部分，当阅读向量矩阵乘法的时候，感觉各种别扭。以前学习的时候，简单的把向量乘以矩阵简化理解成矩阵乘以一维矩阵，然后交换位置进行矩阵乘法。也就是 n 维向量乘以 m*n 矩阵，变成m*n 矩阵乘以 n*1 维矩阵。以后一直是这么计算的。

这么理解计算结果是正确的，但是却不利于理解矩阵的映射特性，矩阵就是映射这句话怎么都理解不对了！！

书本中一直说向量是竖排的，类似这样 $\begin{bmatrix} v1\\\ v2\\\ v3\\\ v4 \end{bmatrix}$。

并且说 n 维向量乘以 m*n 矩阵，得到 m 维向量。这个各种不理解，把列向量理解成了列矩阵，因此这个乘法各种不理解，不符合矩阵的运算规则。这么多年过去了，基础知识都理解的不正确，呵呵！！

其实，书上 1.16部分已经解释过，列向量计算的时候，要放倒，变成 $\begin{bmatrix} v1& v2& v3& v4 \end{bmatrix}$ 的样子，再参与计算。计算结果再切换成$\begin{bmatrix} v1\\\ v2\\\ v3\\\ v4 \end{bmatrix}$的列向量的样子，这样就可以完整的理解整个映射过程了。

继续阅读向量与矩阵相乘

匈牙利算法

零、前言

匈牙利算法是一个经典的解决二部图最小权值匹配问题的算法。网上也有不少资料，但是看完之后总觉得有两个核心问题没有解决：算法为什么一定能得到最优匹配？算法复杂度为什么不再是指数级了？

最后读到了python的库函数scipy.optimize.linear_sum_assignment源代码里引用的文章，才算理解算法的实现，再花了一点时间弄清楚了上边两个问题。

继续阅读匈牙利算法

Munkres' Assignment Algorithm

Assignment Problem - Let C be an nxn matrix representing the costs of each of n workers to perform any of n jobs. The assignment problem is to assign jobs to workers so as to minimize the total cost. Since each worker can perform only one job and each job can be assigned to only one worker the assignments constitute an independent set of the matrix C.

继续阅读Munkres' Assignment Algorithm

求最长公共子序列

求给出的两个序列的最长公共子序列是常见的一个问题。

需要注意的就是最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。

解法如下：

参考链接

最长递增子序列（Longest Increasing Subsequence）

最长递增子序列的解法，可以转化为 求最长公共子序列，也就是生成从目标序列从小到大排序之后的新序列，然后计算原始序列与新序列的 最长公共子序列。但是遇到重复数字的时候，会出现问题。也就是这个解法只能解决无重复数字的最长递增子序列。

另外需要注意的就是最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。

整个的求解过程其实很好理解：

假定要计算的序列为 K = {K₁,K₂,K₃,……,K_n,K_n+1,……,K_m}
初始化计数数组 N = {N₁,N₂,N₃,……,N_n,N_n+1,……,N_m} ，（计数数组跟序列的长度相同，K_n 的最长递增子序列长度计数对应于 N_n）用来记录最长递增子序列的长度，每个项的初始化值都设置为 1 （即使最小的项，项本身也算一个长度，因此最小的长度是 1）
必须从头部(K₁)开始遍历
当计算 K_n 结尾的最长递增子序列的时候，只要遍历序列 K 的前 [0 ~ n-1] 个项，找到数值小于(或者小于等于） K_n （必须遍历，K_n 之前的最长递增子序列不一定是 K_n-1 对应的 N_n-1 ），并且在计数数组 N 中对应的计数最大的项 N_i ，然后 N_n = N_i + 1 。

本方法的时间复杂度是 O(n²)

例子：

设数组 K = { 2， 5， 1， 5， 4， 5 } 那么求最长递增子序列的代码如下：

#include <iostream>
#include <vector>

int calcMaxLISLength(const std::vector<int>& K) {
    std::vector<int> N(K.size(), 1);
    int maxL = 0;
    for(int i = 0; i < K.size(); i++) {
        int Ki = K[i];
        int maxNi = 0;
        for(int j = 0; j < i; j++) {
            int Kj = K[j]; 
            if(Kj < Ki) {
                int Nj = N[j];
                if(Nj > maxNi) {
                    maxNi = Nj;
                }
            }
        }
        int Ni = maxNi + 1;
        N[i] = Ni;
        if(maxL < Ni) {
            maxL = Ni;
        }
    }
    return maxL;    
}

int main(int argc, char** argv) {
    // 2 5 1 5 4 5
    // 3
    std::vector<int> K = {2, 5, 1, 5, 4, 5};
    int r = calcMaxLISLength(K);
    std::cout << r << std::endl;
    
    // 17
    K = {317, 211, 180, 187, 104, 285, 63, 117, 320, 35, 288, 299,
          235, 282, 105, 231, 253, 74, 143, 148, 77, 249, 310, 137,
          191, 184, 88, 8, 194, 12, 117, 108, 260, 313, 114, 261, 60,
          226, 133, 61, 146, 297, 291, 13, 198, 286, 254, 96, 135, 48, 
          135, 307, 23, 155, 203, 258, 168, 42, 301, 45, 164, 193, 26, 
          290, 280, 172, 94, 230, 156, 36, 250, 174, 47, 188, 148, 138,
          194, 89, 71, 119, 218, 325, 136, 63, 271, 210, 320, 309};
    
    r = calcMaxLISLength(K);
    std::cout << r << std::endl;
	
    return 0;
}

#include <iostream>

#include <vector>

int calcMaxLISLength(const std::vector<int>& K) {

std::vector<int> N(K.size(), 1);

int maxL = 0;

for(int i = 0; i < K.size(); i++) {

int Ki = K[i];

int maxNi = 0;

for(int j = 0; j < i; j++) {

int Kj = K[j];

if(Kj < Ki) {

int Nj = N[j];

if(Nj > maxNi) {

maxNi = Nj;

}

int Ni = maxNi + 1;

N[i] = Ni;

if(maxL < Ni) {

maxL = Ni;

}

return maxL;

}

int main(int argc, char** argv) {

// 2 5 1 5 4 5

// 3

std::vector<int> K = {2, 5, 1, 5, 4, 5};

int r = calcMaxLISLength(K);

std::cout << r << std::endl;

// 17

K = {317, 211, 180, 187, 104, 285, 63, 117, 320, 35, 288, 299,

235, 282, 105, 231, 253, 74, 143, 148, 77, 249, 310, 137,

191, 184, 88, 8, 194, 12, 117, 108, 260, 313, 114, 261, 60,

226, 133, 61, 146, 297, 291, 13, 198, 286, 254, 96, 135, 48,

135, 307, 23, 155, 203, 258, 168, 42, 301, 45, 164, 193, 26,

290, 280, 172, 94, 230, 156, 36, 250, 174, 47, 188, 148, 138,

194, 89, 71, 119, 218, 325, 136, 63, 271, 210, 320, 309};

r = calcMaxLISLength(K);

std::cout << r << std::endl;

return 0;

}

第二个测试用例的数据如下：

输入数据个数 
88

实际数据 
317 211 180 187 104 285 63 117 320 35 288 299 235 282 105 231 253 74 143 148 77 249 310 137 191 184 88 8 194 12 117 108 260 313 114 261 60 226 133 61 146 297 291 13 198 286 254 96 135 48 135 307 23 155 203 258 168 42 301 45 164 193 26 290 280 172 94 230 156 36 250 174 47 188 148 138 194 89 71 119 218 325 136 63 271 210 320 309

期望结果
17

输入数据个数

实际数据

317 211 180 187 104 285 63 117 320 35 288 299 235 282 105 231 253 74 143 148 77 249 310 137 191 184 88 8 194 12 117 108 260 313 114 261 60 226 133 61 146 297 291 13 198 286 254 96 135 48 135 307 23 155 203 258 168 42 301 45 164 193 26 290 280 172 94 230 156 36 250 174 47 188 148 138 194 89 71 119 218 325 136 63 271 210 320 309

期望结果

涉及到的面试题目如下类型：

梅花桩问题

题目描述 : Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？ 
样例输入
6
2 5 1 5 4 5
样例输出
3
提示
Example: 
6个点的高度各为 2 5 1 5 4 5 
如从第1格开始走,最多为3步, 2 4 5 
从第2格开始走,最多只有1步,5 
而从第3格开始走最多有3步,1 4 5 
从第5格开始走最多有2步,4 5
所以这个结果是3。
输入例子:
6
2
5
1
5
4
5
输出例子:
3

题目描述 : Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？

样例输入

2 5 1 5 4 5

样例输出

提示

Example:

6个点的高度各为 2 5 1 5 4 5

如从第1格开始走,最多为3步, 2 4 5

从第2格开始走,最多只有1步,5

而从第3格开始走最多有3步,1 4 5

从第5格开始走最多有2步,4 5

所以这个结果是3。

输入例子:

输出例子:

合唱队问题

题目描述
计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述:
整数N
输出描述:
最少需要几位同学出列
示例1
输入
8
186 186 150 200 160 130 197 200
输出
4

题目描述

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述:

整数N

输出描述:

最少需要几位同学出列

示例1

输入

186 186 150 200 160 130 197 200

输出

合唱队问题其实是求最长递增子序列与最长递减子序列的和最大。

最长递减子序列的求法其实就是把原始序列反序，然后 求最长递增子序列 然后把最后的结果反序即可。

代码如下：

#include <iostream>
#include <vector>

static void calcMaxLIS(const std::vector<int>& K, std::vector<int>& N) {
    for(int i = 0; i < K.size(); i++) {
        int Ki = K[i];
        int maxNi = 0;
        for(int j =0; j<i; j++) {
            int Kj = K[j];
            if(Ki > Kj) {
                int Nj = N[j];
                if(maxNi < Nj) {
                    maxNi = Nj;
                }
            }
        }
        N[i] = maxNi + 1;
    }
}

static void calcMaxLDS(const std::vector<int>& K, std::vector<int>& N) {
    std::vector<int> rK(K.rbegin(), K.rend());
    std::vector<int> rN(N);
    calcMaxLIS(rK, rN);
    for(int i = 0; i<rN.size(); i++) {
        N[i] = rN[rN.size() - 1 - i];
    }
}

static int calcMaxVal(const std::vector<int>& K) {
    std::vector<int> N(K.size(), 1);
    std::vector<int> rN(K.size(), 1);
    std::vector<int> KN(K.size(), 0);
    calcMaxLIS(K, N);
    calcMaxLDS(K, rN);
    //
    /*for(int i = 0; i<N.size(); i++) {
        std::cout << N[i];
    }
    std::cout << std::endl;
    for(int i = 0; i<rN.size(); i++) {
        std::cout << rN[i];
    }
    std::cout << std::endl;*/
    
    for(int i = 0; i<N.size(); i++) {
        KN[i] = N[i] + rN[i];
    }
    
   /* for(int i = 0; i<KN.size(); i++) {
        std::cout << KN[i];
    }
    std::cout << std::endl;*/
    
    int maxL = 0;
    for(int i = 0; i < KN.size(); i++) {
        if(maxL < KN[i]) {
            maxL = KN[i];
        }
    }
    return maxL - 1;
}

static void test_calcMaxVal() {
    std::vector<int> K = {186, 186, 150, 200, 160, 130, 197, 200};
    int r = calcMaxVal(K);
    std::cout << K.size() - r << std::endl;
}

static void main_test() {
    test_calcMaxVal();
}

static void main_task() {
    int n = 0;
    while(std::cin >> n) {
        std::vector<int> K;
        for(int i = 0; i<n; i++) {
            int v = 0;
            std::cin >> v;
            K.push_back(v);   
        }
        int r = calcMaxVal(K);
        std::cout << n - r << std::endl;         
    }
}

int main(int argc, char** argv) {
    //main_test();
    main_task();
    return 0;
}

#include <iostream>

#include <vector>

static void calcMaxLIS(const std::vector<int>& K, std::vector<int>& N) {

for(int i = 0; i < K.size(); i++) {

int Ki = K[i];

int maxNi = 0;

for(int j =0; j<i; j++) {

int Kj = K[j];

if(Ki > Kj) {

int Nj = N[j];

if(maxNi < Nj) {

maxNi = Nj;

}

N[i] = maxNi + 1;

}

static void calcMaxLDS(const std::vector<int>& K, std::vector<int>& N) {

std::vector<int> rK(K.rbegin(), K.rend());

std::vector<int> rN(N);

calcMaxLIS(rK, rN);

for(int i = 0; i<rN.size(); i++) {

N[i] = rN[rN.size() - 1 - i];

}

static int calcMaxVal(const std::vector<int>& K) {

std::vector<int> N(K.size(), 1);

std::vector<int> rN(K.size(), 1);

std::vector<int> KN(K.size(), 0);

calcMaxLIS(K, N);

calcMaxLDS(K, rN);

/*for(int i = 0; i<N.size(); i++) {

std::cout << N[i];

}

std::cout << std::endl;

for(int i = 0; i<rN.size(); i++) {

std::cout << rN[i];

}

std::cout << std::endl;*/

for(int i = 0; i<N.size(); i++) {

KN[i] = N[i] + rN[i];

}

/* for(int i = 0; i<KN.size(); i++) {

std::cout << KN[i];

}

std::cout << std::endl;*/

int maxL = 0;

for(int i = 0; i < KN.size(); i++) {

if(maxL < KN[i]) {

maxL = KN[i];

}

return maxL - 1;

}

static void test_calcMaxVal() {

std::vector<int> K = {186, 186, 150, 200, 160, 130, 197, 200};

int r = calcMaxVal(K);

std::cout << K.size() - r << std::endl;

}

static void main_test() {

test_calcMaxVal();

}

static void main_task() {

int n = 0;

while(std::cin >> n) {

std::vector<int> K;

for(int i = 0; i<n; i++) {

int v = 0;

std::cin >> v;

K.push_back(v);

}

int r = calcMaxVal(K);

std::cout << n - r << std::endl;

}

int main(int argc, char** argv) {

//main_test();

main_task();

return 0;

}

解法介绍

首先计算每个数在最大递增子串中的位置

186  186  150  200  160  130  197  200   quene

1      1      1      2       2      1      3     4       递增计数


然后计算每个数在反向最大递减子串中的位置--->计算反向后每个数在最大递增子串中的位置

200  197  130  160  200  150  186  186   反向quene

1      1      1       2     3      2      3       3      递减计数


然后将每个数的递增计数和递减计数相加

186  186  150  200  160  130  197  200   quene

1      1      1      2       2     1      3      4       递增计数

3      3      2      3       2     1      1      1       递减计数

4      4      3      5       4     2      4      5       每个数在所在队列的人数+1（自己在递增和递减中被重复计算）


如160这个数

在递增队列中有2个人数

150  160

在递减队列中有2个人数

160  130

那么160所在队列中就有3个人

150  160  130


每个数的所在队列人数表达就是这个意思


总人数 - 该数所在队列人数 = 需要出队的人数

首先计算每个数在最大递增子串中的位置

186 186 150 200 160 130 197 200 quene

1 1 1 2 2 1 3 4 递增计数

然后计算每个数在反向最大递减子串中的位置--->计算反向后每个数在最大递增子串中的位置

200 197 130 160 200 150 186 186 反向quene

1 1 1 2 3 2 3 3 递减计数

然后将每个数的递增计数和递减计数相加

186 186 150 200 160 130 197 200 quene

1 1 1 2 2 1 3 4 递增计数

3 3 2 3 2 1 1 1 递减计数

4 4 3 5 4 2 4 5 每个数在所在队列的人数+1（自己在递增和递减中被重复计算）

如160这个数

在递增队列中有2个人数

150 160

在递减队列中有2个人数

160 130

那么160所在队列中就有3个人

150 160 130

每个数的所在队列人数表达就是这个意思

总人数 - 该数所在队列人数 = 需要出队的人数

参考链接

兔子生兔子问题详解(斐波那契数列)

有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

这个问题可能我比较笨，看大多数解释都是一句话，f(n) = f(n-1) + f(n-2)，但是总有点想不明白这个。列了个表格才看清楚咋回事。

月份	1	2	3	4	5	6	7
兔子总数	1	1	2	3	5	8	13
具有生育能力兔子	0	0	1	1	2	3	5

如果这个月是第n个月，那要求这个月兔子的总数，其实就是上个月的兔子总数加上新生出来的兔子。也就是f(n) = f(n-1) + x。这个x是比较难理解的地方。那这个月到底新生出来多少兔子呢？这就是求这个月已经有生育能力的兔子是多少，上上个月所有的兔子就是这个月所有的有生育能力的兔子，这里可以结合表格推一推就很好理解了。所以x就是f(n-2)。

因此可以得到递推f(n) = f(n-1) + f(n-2)。

其实比较简单的问题，不过自己光凭笨脑子想，突然没想明白，记一下这个思考过程。

还有就是牛客网上的高赞答案详解：

#include <iostream>
using namespace std;
 
int main(){
    int m;
    while(cin>>m){
        int a=1,b=0,c=0;//a:一个月兔子数，b：两个月兔子数，c：三个月兔子个数
        while(--m){//每过一个月兔子数变化
            c+=b;
            b=a;
            a=c;
        }
        cout<<a+b+c<<endl;
    }
}

#include <iostream>

using namespace std;

int main(){

int m;

while(cin>>m){

int a=1,b=0,c=0;//a:一个月兔子数，b：两个月兔子数，c：三个月兔子个数

while(--m){//每过一个月兔子数变化

c+=b;

b=a;

a=c;

}

cout<<a+b+c<<endl;

}

有人是以a表示一个月的兔子，b表示两个月的兔子，c表示三个月的兔子（原文这么注释的），我因为这个注释半天没看懂，后来明白了，c意思是已经成熟的兔子，也就是表示3个月及以上的兔子，也就是说c表示能生兔子的兔子。

那就可以以月份循环，每到达新的一个月，b都会成熟，所以c+=b，c就更新了，仍然表示所有成熟了的兔子，b怎么更新呢？b其实就是上个月那些成熟度是1个月的兔子，所以再更新b，用b=a；a呢？a就是现在更新后的c，因为更新后的c表示这个月成熟了的兔子，那这些兔子都会生一只新的兔子，新兔子就是成熟度为1个月的，所以用a=c。这样现在这个月的兔子总数就是a+b+c。

这是我自己没找到注释，自己总结出来的答案详解，这个方法比递归复杂度低，空间占用更是比用数组先去存要少很多。