【校招面试 之 剑指offer】第10-3题 矩阵覆盖问题

题目:我们可以使用2✖️1的小矩形横着或者竖着去覆盖更大的矩形。请问用8个2✖️1的小矩形无重叠地覆盖一个2✖️8的大矩形,共有多少种方法?

【校招面试 之 剑指offer】第10-3题 矩阵覆盖问题

分析:当放第一块时(假定从左边开始)可以横着放,也可以竖着放,记总的情况为f(8)。如果是竖着放,则记下来还有f(7)种放法;若是横着放,则下一块必须横着放,则还有f(6)种放法。

所以可以推导出公式:f(1) = 1 f(2) = 2 f(n)(n为偶数) = f(n-1)+f(n-2);

#include<iostream>
#include<math.h>
using namespace std; //
int matrixCover(int n){
if(n == 1)
return 1;
if(n == 2)
return 2;
return matrixCover(n - 1) + matrixCover(n - 2);
} int main(){ // 矩阵覆盖问题
cout<<"有 "<<matrixCover(8)<<" 种覆盖方法"<<endl;
system("pause");
return 0;
}

 

上一篇:2015阿里巴巴安全峰会PPT


下一篇:linux系统编程:线程同步-信号量(semaphore)