前面3篇文章介绍了减治法的策略和思想，经典数据结构算法中的几个减治算法，排列，子集的减治算法。这些都是属于减一治的减治策略。

这篇文章来介绍减常因子和减可变规模的减治策略算法，当然，规模递减的越快的算法也就越难找，所以这样的算法并不是很多。目前前面写过的减常因子的有折半查找（减常因子的减治策略的可以看做分治的变种，前面说过），减可变规模的减治策略有欧几里得最大公约数算法。

—————————————————————————————————————————————————

1.减常因子策略

1）假币问题

或者说是坏苹果问题，很老的微软面试题了。在n个外观相同的硬币中，有一个是假币（重量与别的硬币不同，较轻），只有一架天枰，怎么找出假币？

这或许是个小学生都会的问题：

a，　　每次若为偶数，分成两半，假币肯定在较轻的那一半中

b，　　若为奇数，拿一个出来然后把剩下的分两半，若两半相等则拿出的一个是假币，否则同步骤a

这样每次都将问题的规模缩减为原来规模的1/2，其时间复杂度和折半查找一样。

看上去，现在这个问题似乎是很低级无聊，问题是，这样做最高效的算法吗？给你一堆假币，按照上述办法来做找假币，是最快的办法吗？

不是！

事实上可以将规模分成三份，每次比较任意两份，若相等则在第三份中，若不相等则在这两份的较轻一份中，这样问题的规模每次递减为原来规模的1/3。虽然它也是对数级别的复杂度，但一个是log2（n），一个是log3（n）

根据这一思想，对于二分查找，我们可以设计出更好一点的算法：三重查找，每次同时和数组中下标n/3， 2n/3的两个点比较，这样多比较一次就将问题规模定位到一个原规模三分之一的区间了。复杂度为log3（n）,本节的习题给出了这样一个问题，实现不是很难，略。

2）俄式乘法

一个很简单但很有趣的例子，简单看下吧：

对于2个数相乘n * m，显然有这样的式子：

 

上面的式子显然可以递归的定义，见乘法的规模越变越小，把1 * m作为结束递归的条件。

这样做有什么好处和意义呢？应该注意到，用上述办法来做乘法，该算法所有运算只有折半，加倍，相加3个操作，这对于不想记乘法口诀表的人来说是一个诱惑，因此在19世纪俄国农夫广泛的采用了这种方法。另外，由于它只进行加法吗，折半和加倍（可以通过移位运算），速度比传统乘法快。

package Section5;

/*第5章 减治法 俄式乘法*/

public class Russe {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int result = RusseMul(26,47);
System.out.println(result);
}

public static int RusseMul(int n,int m){
//俄式乘法:只用加法，增倍，减半3个操作来实现乘法运算
int result = m;
if(n == 1)
return result;
else
{
if(n % 2 == 0)
result = RusseMul(n/2,2*m);
else
result = RusseMul((n–1)/2,2*m) + m;
}
return result;
}
}

3）约瑟夫斯问题

这个传统上来说，应该用循环链表来解决，之前用C写过了，见前面文章。这里从减治的角度，用递推来实现，对数学要求就很高，简单看一下吧，不过我觉得这种解决办法不是很主流，详细的自己去看书，只说有意思的一点：

不过用这种办法，在报数为2时，跟二进制有一点关系，对于n个人，每次报数为2，最后剩下的人的编号（从1编号）可以直接用二进制编码循环左移一位得到。

例如6个人，7个人的情况如上，最后剩下的人的编号分别为5和7。

————————————————————————————————————————————————-

2，减可变规模的问题

1）计算中值和选择问题

选择问题是求一个n个数的列表的第k个最小元素的问题，这个数字被称为第k个顺序统计量。（编程之美上也有这个问题）如果k=1或者n，那就是求最大最小值，扫描一遍就可得到，对于任意的k，怎么办呢？

对整个列表排序？时间复杂度是n * log（n），当然，这样是可行的，排序后你就得到了每一个元素的顺序，而不仅仅是第k个最小元素，这样显得有些杀鸡用牛刀，因为别人并不要求你把每个元素的顺序都求出来，质只要第k个最小的元素。

对于这个问题，其实有许多线性复杂度的方法（例如用一个含k个最小元素的筛子筛选，扫描一遍就能筛选出最小的k个元素，等等其他方法。见编程之美）。这里要说的一种方法是基于减可变规模的分区思想的方法，k元素筛和分区的方法各有特点：k元素实现非常简单，且最后结果不仅仅是第k个最小元素，它找出了最小的k个元素；分区方法结果找出了第k个元素，且以它为边界把其他元素分成了大于它和小于它的两个部分，类似快排，实现稍显复杂一点。

分区思想就是根据每一次快排后，分割下标是否为k，若为k那么它就是第k个顺序统计量，若不是，规模就减小了，第k个顺序统计量在左边或者右边。其实现非常类似于快速排序，虽然前面写过了，但看到这个才发现快排分区那我还不是很会，时间久了就忘了。写了半天也没写好，有时间把这个地方重写一遍

2）插值查找

简单，纯数学问题，注意是减可变规模。参见相关书籍

3）二叉查找树的查找和插入

写过，略，注意是减可变规模的。

4）拈游戏

拈游戏是一种博弈的游戏：

现在有一堆n个石子，两个玩家轮流每次从堆中拿走至少一个至多m个石子，每次拿走的数量可以不同。如果每个玩家都作出了最佳选择，哪个玩家能够拿到最后的哪个棋子（定义为赢，即当一个人没有棋子拿的时候，就说他输了），问题是，哪个玩家能拿到最后的棋子（赢），先走的还是后走的？

这样来分析：

轮到某人拿时，棋子的数量：　　　　　　他是赢还是输：
　

　　　0　　　　　　　　　　　　　　　　　　 输　　（输的定义）

　1 <=   x  <=  m　　　　　　　　　　　　　赢　　（全部拿走就赢了，石子状态转移到0，把输留给对方）

　　m + 1　　　　　　　　　　　　　　　　　输　　（最多只能拿m，不管拿多少，对方总能把剩余的全部拿走）

m+2   <=   x   <=  2m+1　　　　　　　　　赢　　（可以拿【1，m】，使石子为m+1，将输的状态留给对方）

………

据以上分析：如果石子数量是m+1的倍数，那么先手的人是一个败局，否则先手的人是一个胜局（拿取特定的数目，使石子数量是m+1倍数，即把败局留给对方）。

简单的说，在整个游戏过程中，只要谁拿的时候碰上了m+1倍数的棋子，他就是一个败局（当然，这是基于双方都非常聪明总是做出最佳选择情况，如果一方很傻，遇到了胜局又错过了，那就没办法了）。

策略是这样滴：如果对方遇到了m+1，那么你现在是胜局，且你要把胜局保持下去，每次对方拿了之后（因为是m+1的倍数，他无法拿完把下一个m+1的倍数留给你），你都要拿相应的棋子，使得石子仍为m+1的倍数（即永远把败局留给他），如果你不明白这样的最佳策略，一旦你错过一次，他就可以把败局永远的留给你（如果他懂得这样的最佳策略），当然，如果两个人都很傻，那就混乱了，随便乱玩。

这是一个减可变规模的！