棋盘算法是怎么回事

2025年01月30日 阅读 (53)

在之前介绍的排序算法中,二分搜索、合并排序、快速排序都是用分治方法排序的。类似于数学归纳法,思想还是很简单的。

案例:

在一个2的k次方乘以2的k次方个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为一个特殊方格,且称该棋盘为一个特殊棋盘。显然特殊方格在棋盘上出现的位置有4的k次方种情形。因为对任何k=0,有4的k次方种不同的特殊棋盘。如图(a)所示。

棋盘算法是怎么回事(1)

在棋盘覆盖问题中,要用4种不同形态的L型骨牌(b图所示)覆盖一个给定的特殊棋盘上除特殊方格以外所有方格,且任何2个L型骨牌不得重叠覆盖。

分治策略:

特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,这三个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为1×1棋盘。

郑重声明:玄微运势的内容来自于对中国传统文化的解读,对于未来的预测仅供参考。