花了一下午的时间去搞懂算法笔记上面的那个全排列的问题, 看来放松时间久了代码能力的确会下降的很快

 

递归

 

递归的概念很简单, 就是一个函数自己调用自己, 然后等到调用到不可再调用时依次从后往前返回值

函数递归有两个特点:

1. 递归边界 : 一般来指函数调用到最底层的结果
2. 递归式 : 即递归调用

 

如果一个函数没有递归边界, 会因为栈空间不足而出现程序崩溃的情况.

 

一个计算阶乘的程序

#include <cstdio>
#include <array>

using namespace std;

int factorial(int x)
{
    if(x == 0)
        return 1;			/*0的阶乘为1*/
    
    else
        return x * factorial(x - 1);		/*每次计算x都会减1, 这里千万不要写成自减形式*/
}

int main(void)
{
    int x;

    scanf("%d", &x);

    printf("%d\n", factorial(x));

    return 0;
}

 

在使用++或--时要保持一个原则, 就是单独使用, 不要把它们和其它运算 (如常规的四则运算中) 混用, 以免造成困惑.

 

斐波那契数列

 

斐波那契数列在刚学C语言或C++时都会涉及到, 它的一般形式是

1, 1, 2, 3, 5, 8, 13, 21 ....

从中我们可以找到一条规律 : 从第二个数开始, 后面每一个数都是前两数之和. 如果找出其中的一项, 该怎么办

 

#include <cstdio>
#include <array>

using namespace std;

int fibonacci(int x)
{
    if (x == 0)
        return 1;

    else if (x == 1)
        return 1;

    else
        return fibonacci(x - 1) + fibonacci(x - 2);
}

int main(void)
{
    int x;

    scanf("%d", &x);

    printf("%d\n", fibonacci(x));

    return 0;
}

 

通过上面这个函数可以看出来, fibonacci函数是将一个数分解成了几个1相加的形式求出的. 这里其实用到了分治的思想

 

---

 

分治

 

分治, 顾名思义就是分而治之的意思. 将一个大问题逐渐化为几个小问题然后依次求解最后全部合并得到最终结果.

 

分治除了最典型的斐波那契数列, 还有数学中的全排列. 这里举个简单的例子, 求出(1, 2, 3)的全排列

这道题只要简单的排列组合就可以得到最终答案 : (1, 2, 3) , (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

 

#include <cstdio>
#include <array>

using namespace std;

int n;							/*数字的个数*/
const int maxn = 11;			/*数字的位数*/
array<int, maxn> P;				/*用来存放排列好的数字*/
array<int, maxn> hashtable;		/*用来检查数字x是否在P中*/

void part(int index)			/*index, 位数*/
{
    if(index == n + 1)				/*递归边界, 用来输出排列好的数字*/
    {
        for (int i = 1; i <= n; i++)
            printf("%d", P[i]);

        printf("\n");
    }

    for (int x = 1; x <= n; x++)		/*从1到n枚举, 将x填入P中*/
    {
        if(hashtable[x] == false)		/*如果x不在P中*/
        {
            P[index] = x;				/*令P的第index位为x, 即将x加入排列中*/
            hashtable[x] = true;		/*证明x已被插入排列中*/
            part(index + 1);			/*继续将下一位数字插入排列中*/
            hashtable[x] = false;		/*已处理完P[index]为x的子问题, 还原状态*/
        }
    }
}

int main(void)
{
    n = 3;

    part(1);

    return 0;
}

 

第二个for循环实际上是用来填入数字的, 不用想的很复杂. 其实这里的全排列使用的字典序进行排列的, 关于字典项可以自行百度.