前面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((n1)/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的倍数(即永远把败局留给他),如果你不明白这样的最佳策略,一旦你错过一次,他就可以把败局永远的留给你(如果他懂得这样的最佳策略),当然,如果两个人都很傻,那就混乱了,随便乱玩。

这是一个减可变规模的!