AlgarithmLearning_Day2.1 (《算法笔记》第四章 入门篇（2）算法初步）

本文主要是介绍AlgarithmLearning_Day2.1 (《算法笔记》第四章 入门篇（2）算法初步），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 4.3 递归
  4.3.1 分治(divide and conquer): 分治法将原问题划分成若干个规模较小而结构与原问题相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解。
  分治大体上有三步走：分解、解决、合并（这个方法貌似我一直都有在用，只不过用在了不对的地方，把简单的问题复杂化了，不能怪分治，怪就怪我的变成思想有问题）
  4.3.2 递归：“要理解递归，你要先理解递归，直到你能理解递归”——一个笑话。
  总之，递归很适合用来实现分治思想。
  递归的逻辑中有两个核心概念：递归边界，递归式
  递归边界让程序有了尽头，也告诉程序需要进行多少计算。递归式则包含着我们所求的问题。一个是问题与递归入口，一个决定了运行边界。最简单的例子就是求阶乘：
  return F(n - 1) * n这个递归式，其中边界是if(n == 0) return 1;
  再一个经典的例子就是斐波那契数列了，由于过于经典我这里就跳过了，因为在我之前的博客里面提到过。斐波那契的最优解就是建立一个小型备忘录，只需要就上次作用时候的变量就可以，这样空间与时间均为最优，而并不用建立全部数据的备忘录。
  全排列的递归实现：

const int maxn = 11;
//P为当前排列，hashTable记录整数x是否已经在P中
int n, P[maxn], hashTable[maxn] = {false};
//当前处理排列的第 index 号位
void generateP(int index){
    if (index == n + 1){ //递归边界，已经处理完排列的1~n位
        for (int i = 0; i <= n; ++i) {
            cout << P[i] << " "; //输出当前排列
        }
        cout << endl;
        return;
    }
    for (int x = 1; x <= n; ++x) { //枚举1~n，试图将x插入P[index]
        if (hashTable[x] == false){//如果x不在P[0]~P[index-1]中
            P[index]     =    x;   //令P的第index位为x，即把x加入当前排列
            hashTable[x] = true;   //记录x已在P中
            generateP(index + 1);//处理排列的第index+1号位
            hashTable[x] =false;       //已处理完P[index]为x的子问题，还原状态
        }
    }
}

体会一下哈希表的使用和递归的感觉。首先hashTable大小是11，即最多存储11个bool值，而n是控制全排序位数大小的变量。整段代码前半主要时候控制递归边界用的。可以如此理解：刚开始hashTable的值全部是false，因为P没有存入任何元素。若现在开始存入第一位为1，我们就会发现从第二位开始就有奇怪的事情发生了，由于第一位1的存入，hashTable[1]的值就是true了，因此在递归到下一个generateP的函数时1就无法被调用，轮到2了，一直这样1、2、3、4、5。这就是我们编程之后第一行是12345的原因了。之后的肯定就是先使hashTable[5]=false回到上一次让hashTable[4]=false那里，继续递归进行循环。
递归的艺术就是可能意识不到这种倒推的感觉，他自己就动起来了。在一次次的递归过程中，先解决最后一个问题，再从最后一个问题向前回溯，找到第n-1个问题，这个逻辑过程让人着迷。也正是这种非正常的逻辑过程让一些复杂的问题变得简单，递归加上hash就能将本需要重复计算的结点跳过，减少运行时间和内存调用。
其实

这篇关于AlgarithmLearning_Day2.1 (《算法笔记》第四章 入门篇（2）算法初步）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！