递归与分治解棋盘覆盖问题(C++)

分治算法: 当k>0时,将2^k ́ 2^k棋盘分割为4个2^(k-1) ́ 2^(k-1)子棋盘残缺方格必位于4个子棋盘之一其余3个 子棋盘中无残缺方格。为此将剩余3棋盘转化为残缺棋盘.。用一个L型骨牌覆盖这3个较小棋盘的结合处。这 3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方格,原问题转化为4个较小规模的棋盘覆盖问题。 递归地使用这种分割,直至棋盘简化为1 ́1棋盘。 算法分析:设T(k)为覆盖2^k ́ 2^k残缺棋盘的时间: 当k=0时覆盖它需要常数时间O(1)。 当k>0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1)。 覆盖4个残缺子棋盘需四