一、欧几里得算法

我们前面学过求最大公约数的算法：欧几里得算法（又叫辗转相除法） ，一般缩写是gcd，在C++中经常写成如下形式：

int gcd(int a,int b)     {        if(a%b==0)           return b;       else           return gcd(b,a%b);   }

原理就是代码中比较核心的 gcd(b，a%b)，这个定理用文字描述就是:

用a除以b（这里是a>b,当然，在程序编程中，求两个数的最大公约数，可以不限a和b的大小，a<b也就是多一次循环）得到结果q和余数r，再用除数b除以余数r 再得到一个余数，再用除数除以余数，…如此循环，直到余数为0，那么此时的除数就是最大公因数。

想要证明gcd(a,b) = gcd(b,a%b)，需要简单了解下面两个引理：

• 若d是a和b的公约数，那么d也是b和c的公约数（c为a%b）

• 若d是b和c的公约数（c为a%b），那么d也是a和b的公约数

这两个引理的是什么意思呢，拿第一个来说；

假设一个数d是a的因子，也就是a=m*d，同时也是b的因子，b=n*d，那么a%b = a-w*b =  (m-w*n)*d；

由此可得，a的因子集合、b的因子集合和c的因子集合是相同的；

然后利用上述定理当余数为0的时候，除数就是最大公约数；

二、扩展欧几里得算法

    从字面上看，扩展欧几里得算法就是把欧几里得算法进行了扩展，不仅能求a和b的最大公约数，还其他功能，比如:

• 求ax+by=m的任意一组解，最小整数解。

• 求模逆元（模反元素）

为了了解学习上面的公式，需要先了解一个裴属定理

1. 样例

   
   
   

#include<iostream>  using namespace std;  int main(){  	cout<<(1&1)<<endl; //1   	cout<<(1&-1)<<endl; // 1   	cout<<(-1&-1)<<endl; //-1   	cout<<(-2&-3)<<endl; //-4   	return 0;  }

2.解释

 1&1：

      1    0000 0001  

      &   

      1    0000 0001  

-----------------------

      1    0000 0001   

 1&-1：

     1    0000 0001  

      &   

     -1   1111 1111  （补码）

-----------------------

      1    0000 0001   

解释：1的补码是1111 1111，然后进行逻辑与运算即可。

 -1&-1：

     -1   1111 1111  （补码）

      &   

     -1   1111 1111  （补码）

-----------------------

           1111 1111   

解释：负数和负数的逻辑与运算比较特殊。

-1 & -1 的直接结果是1111 1111，出符号位以外，剩下111 1111

然后把最低位减一得： 111 1110

然后按位取反得： 000 0001, 也就是1

加上符号就是-1，所以最后结果是-1

 -2&-3：

     -2   1111 1110 （补码）

      &   

     -3   1111 1101  （补码）

-----------------------

           1111 1100   

解释：

-2 & -3 的直接结果是1111 1100  ，出符号位以外，剩下111 1100

然后把最低位减一得： 111 1011

然后按位取反得： 000 0100, 也就是4

加上符号就是-1，所以最后结果是-4

1. 前言

   所谓分治算法就是指分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。

   比如，我们玩过最简单的猜数游戏，一开始，对方先想一个1000以内的正整数，然后你给出一个数x。对方只要回答“比x大”或者“比x小”或者“猜中”。

   开始猜测是1到1000之间，你可以先猜500。运气好的一次猜中，如果比500大，显然结果不是1到500之间，那么下一次就猜501到1000。如果比500下，那么下次就猜1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。这样不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。

2. 基本思想及策略

   分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

    分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

     如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法适用的情况

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

应用

（1）二分搜索

 （11）一元三次方程求解

快速排序：

void qsort(int left, int right){  	int i=left; j =right;  	mid=a[left+right]/2;  	while(i<=j){  		while(a[i]<mid) i++;   		while(a[j>mid]) j--;  		if(i<=j){  			swap(a[i],a[j]);  			i++;  			j--;  		}  	}  	if(left<j) qsort(left,j);  	if(i<right) qsort(i,right);  }

一元三次方程求解：

描述

有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。

给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。

输入

一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。

输出

一行，包含三个实数，为该方程的三个实根，按从小到大顺序排列，相邻两个数之间用单个空格隔开，精确到小数点后2位。

样例输入

1.0 -5.0 -4.0 20.0

样例输出

-2.00 2.00 5.00

【题目描述】

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。

下图 显示了一个迷阵的样例及李逍遥找到仙药的路线。

【输入描述】

第1行输入两个非零整数 M 和 N ，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。

接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:

1) ‘@’：少年李逍遥所在的位置；

2) ‘.’：可以安全通行的方格；

3) ‘#’：有怪物的方格；

4) ‘*’：仙药所在位置。

【输出描述】

求李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。

【样例输入】

8 8  .@##...#  #....#.#  #.#.##..  ..#.###.  #.#...#.  ..###.#.  ...#.*..  .#...###

【样例输出】

10