算法设计与分析

一、求两个正整数的最大公约数

1.欧几里得算法

欧几里得算法也被称为辗转相除法，原理就是当前一个数比后一个数大时，我们将大数模小数得到的数放在括号右侧，原来的小数放在括号左侧，以此类推，直到n=0时，那么此时的m就是最大公约数

2.连续整数检测法

第一步：找到这两个数的最小值

第二步：判断m%这个最小数是否等于0，如果等于0就进入第三步，否则进入第四步

第三步：判断n%这个最小值是否等于0，如果等于0就返回这个最小值，否则进入第四步

第四步：将这个最小值-1操作，再回到第二步重新判断，知道两个数模以这个最小值都等于0，那么就证明这个结果找到了

3.分解因式方法

那么这两个式子有着公共的式子，出现了这样的公共因式，所以;

那么我们应该怎么做呢，如何实现呢

应该把2到n的所有素数找出来，那么如何快速找出所有素数呢？通过埃拉托色尼筛算法

首先初始化一个2-n的序列，第一个循环消去2的倍数，接下来消去3的倍数，接下来又指向5，消去他的倍数，直到没有可消的元素

棋盘覆盖问题，全步骤和代码

棋盘覆盖是一个非常非常非常经典的利用分治策略求解的一类题型，最近正好学到这里，借此更新一波～

那么我们如何进行铺骨牌才能保证不重叠呢？，这里棋盘是一个偶数的方阵，我们可以逐步拆开，将，横着来一刀，竖着来一刀,我们可划分为的四个子问题了，我这里讲一下这个逻辑，也就是，看那个特殊方块（题目中会给出或者自己输入），如果在我们划分的第一个区域也就是左上角，那么就把这个左上角再做一次划分递归调用，如果我们发现不在这个区域，我们就可以直接覆盖他们的中心代码。

关于归并排序的问题

归并排序的要点就是，在一组连续的数中，第一次把单独的看成一个整体，第二次把两两看成一组，第三次把两两组成的分别的两两再拿在一个组里来，排序，然后合并他们，仅此而已

关于快速排序的问题

快速的排序主要在于分支策略中的patition算法，一分为二，设置一个基准数（普通的是一直找数组首元素），在改进后的patition算法中是随机找一个数，这样可以避免最坏情况

关于矩阵连乘的问题

矩阵连乘也是动态规划的典型例题

数乘次数：（1）如果A是m×p的矩阵，B是p×n的矩阵，那么乘积C是m×n的矩阵。 （2）矩阵C共有m×n个元素，每个元素为A的一行与B的一列对应元素相乘再相加（此过程有p次数乘）；（3）故共计算了m×n×p次数乘。

最优二叉搜索树的一些知识和有用的解题思路

那么我们要干嘛呢，何为搜索？搜索就是查找一个数嘛，这么简单理解，那么如果我从这棵树里找一个数，那么找到这个数的概率是多少呢，找不到的概率又是多少呢，我们通过研究这个来进行探讨最优二叉搜索树的问题。

题目信息如下：假如我们有6个数字在这棵树中,其中k代表的是真实存在的，d代表不存在的,那么为什么要多添加不存在的呢,我们设想如果我们要找5这个数，但是这棵树里面并没有5这个数，但是这个5是不是一定存在于这棵树的其中一个位置呢，我们说左子树小于父亲，右子树大于父亲，那么一定能在这棵树找5这个位置，那么5这个不存在的位置我们就记作以d为不存在的数，可是他们的位置我们仍然需要探讨，搜索与否的概率。(换句话说，计算机不能和人一样，可以直接看到，所以他需要对这棵树进行遍历，找到最合适的范围再看是不是要查找的这个数，直到为不存在的数d。)