知识框架

No.1 减治法

一、基本思想

思想：将规模为n的问题递减为规模为n-1或n/2的子问题,反复递减后对子问题分别求解,
再建立子问题的解与原问题的解的关系。（再回归过去就可以了。）

减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的关系。
一旦建立了这种关系，既可以自顶至下（递归），也可以自底至上（非递归）地运用这种关系。

二、类别

按照规模划分减治法有三个变形:

1. 减常数(如1) :每次迭代规模减1，即n→n-1（例如插入排序）
2. 减因子(如1/2):每次迭代规模减半，即n→ n/2（例如折半查找）
3. 减可变规模:每次迭代减小的规模不同（例如欧几里得算法）

三、简单举例子

举个简单的例子：

例如 f(n)=a^n;那么应用减治法就是

比如：减常数1；问题变成 f(n)=f(n-1)*a;(这里只需要求f(n-1),就可以了。就转化为f(n-1)问题了，然后继续往下；最后得到的子问题的结果再回归上去就可以了)；规模为n的问题–>规模为n-1的子问题–>子问题的解–>原始问题的解；

比如：减因子（半）；问题变成 f(n)=(a^n/2)2。然后继续往下；最后得到的子问题的结果再回归上去就可以了)；规模为n 的问题–>规模为n/2的子问题–>子问题的解–>原始问题的解;;

No.2 插入排序（减一个常量）

一、基本思想

它的基本思想是：每步将一个待排序的对象按照其关键字的大小，插到前面已经排好序的序列中的适当位置，直到全部对象插入完毕为止。

二、类别

1. 直接插入排序、
2. 折半插入排序、
3. 链表插入排序
4. 希尔排序（缩小增量排序），
5. 它们划分的依据是在排好序的序列中寻找插入位置所使用方法的不同。

#define MAXSIZE 200
typedef struct{     //结点类型KeyType		key;InfoType	otherinfo;
}RecordType;
typedef struct{     //排序表类型RecordType	R[MAXSIZE+1];int			length;
}SqList;    void InsertSort( SqList  &L )  {//对顺序表L作直接插入排序for(i=2; i<=L.length; i++)if (L.R[ i ].key < L.R[ i-1].key)  {L.R[0].key=L.R[ i ].key ;    //将R[ i ]赋给哨兵L.R[ i ]=L.R[ i-1] ;for( j=i-2;  L.R[ j ].key>L.R[0].key;  j- - )  L.R[ j+1]=L.R[ j ] ;   //将大于哨兵的记录右移L.R[ j+1]=L.R[0] ;     // 将R[i]放入有序区的正确位置}   //end if
} 

三、过程

待排序序列{89,45,68,90,29,34,17}

1. ​ {89} 不需比较
2. ​ {45,89}
3. ​ {45,68,89}
4. ​ {45,68, 89,90}
5. ​ {29,45,68, 89,90}
6. ​ {29,34,45,68 89, 90}
7. ​ {17,29,34,45,68, 89, 90}

得到插入的次数：为n-1=6次；；是每个序列都是这样吗？？

比较次数：一趟一趟的计算即可。

四、效率分析

直接插入排序的基本操作是：：比较；

即 时间复杂度为：O(n^2);

No.3 减常因子算法

一、折半查找

这个要真正的自己过一遍才能知道了解具体的过程；；

int Search_Bin(SSTable ST, KeyType K){int low=1, high=ST.length;int mid;while(low<=high){mid=(low+high)/2;if(K<ST[mid].key)high=mid-1; 	//在左区间继续查找else if(K>ST[mid].key)low=mid+1; 	//在右区间继续查找else  return mid;	//查找成功的出口}//whilereturn 0;      //查找失败的出口
}//Search_Bin

效率分析：

基本操作：比较 ；； C(n)∈Θ(log2n)

二、假币问题

题目：有n个金币，其中一个是假币。这个假币的重量比真币的重量要轻一点，所有n-1个金币的重量是一样的。现在你有一架天平，设计高效的算法（用最少的使用天平次数）找出那个假的金币。

1、用减治法（减半）

把n个硬币分为两堆，每堆n/2个，每次称两堆。易见 W(1)=0；；W(n)=W(n/2)+1；；解得 W(n)= log2n

2、用减治法(减n/3）

把n个硬币分为三堆，每堆n/3个，每次称任意二堆。易见
W(1)=0 当n=1
W(n)=W(n/3)+1 当n>1

解得 W(n)=O(log3n)，结果比减半法更好。

3、问题实例

用方法2（减n/3法）需要称 2 次。过程如下：；
将9个金币分为3个组，每组3个金币。
将其中的两组放在天平的两边，如果有一边轻，说明假的金币就在这个组里。如果两边一样重，说明假的金币在第三个组里。
在有假币的组中，拿出两个金币，放在天平的两边，如果有一个轻，则这个轻的就是假币，如果两个一样重，则剩下的一个就是假币。

三、俄式乘法

1、题目

题目：：n、m是整数，求n*m。

解题步骤：

1. 若n为偶数，则n·m=(n/2)· 2m；
2. 若n为奇数，则 n·m=((n-1)/2)· 2m+m
3. 结束条件：1·m=m为算法停止的条件。

差不多是将乘法转化为1*z+加法结果。

2、实例：

俄国农民法举例: 50×65；

n m 分析 .
50 65 50×65=25×130
25 130 +130 25×130=12×260+130
12 260
6 520
3 1040 +1040
1 2080 +2080
= 3250

四、约瑟夫斯问题

1、题目：

题目：设有n个以1、2、…、n编号的人，按编号顺序围成一圈，从1号开始报数，每数到2就淘汰一人，问最后被淘汰的人是几号呢？

解题步骤：

1. ​ J(2k)=2*J(k)-1
2. ​ J(2k+1)=2*J(k)+1

首先总人数是 2k或者2k+1；然后再减半规模下去。

2、实例：

No.4 减可变规模算法

一、欧几里得算法

二、计算中值和选择问题

选择问题是求一个n个数列表的第k个最小元素的问题。这个数字被称为第k个顺序统计量

1. k＝1或者k＝n的情况，就是求列表的最小或最大元素
2. ​ k=n/2 时，要求找出这样一个元素，该元素比列表中的一半元素大，比另一半元素小，这个值被称为中值。

求解步骤：

1. 利用快速排序的分区方法，将数组分成两部分，分割点的下标为s，右边部分大于枢轴值p，左边部分小于枢轴值p。
2. 若s=k则结束；
3. 若s>k，则在左边继续找第k小的元素；
4. 若s<k，则在右边继续找第k-s小的元素；

三、插值查找

四、二叉查找树的查找和插入

1、定义和步骤

二叉查找树：每个节点一个元素，并使得对于每个节点来说，所有左子树的元素都小于子树根节点的元素，所有右子树的元素都大于子树根节点的元素。

查找元素v：

1. 如果子树为空，查找失败
2. 如果不为空，则把v和该树的根K®比较
   1. 相等就是找到了
   2. v< K®则在左子树中查找
   3. v> K®则在右子树中查找

2、效率 分析

有点类似折半；；

1. 一棵查找树的规模的最佳度量就是树的高度
2. 最坏情况就是当这棵树是单支树时是Θ(n)
3. 平均效率为Θ(logn)，

五、拈游戏

1、单堆棋子版本

题意：

1. 有一堆 n 个棋子
2. 两个玩家轮流从堆中拿走最小 1 个，最多 m 个棋子
3. 每次拿走的棋子可以不同，但上下限数量不变
4. 如果每个玩家都做出最佳选择，哪个玩家能胜利的拿走最后那个棋子，先走的还是后走的？

解题步骤：

1. 本题以 先手的 来入局；
2. 以 拿走最后的棋子的 人 为赢家；
3. 模式：当且仅当n不是m+1的倍数的时候，n个棋子的实例是个胜局。
4. 获胜策略每次拿走n mod (m+1)个棋子；