题目描述:
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
输入:
输入可能包含多个测试样例,对于每个测试案例,
输入包括一个整数n(1<=n<=70),其中n为偶数。
输出:
对应每个测试案例,
输出用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有的方法数。
样例输入:
4
样例输出:
5
/*********************************
* 日期:2013-11-15
* 作者:SJF0115
* 题号: 题目1390:矩形覆盖
* 来源:http://ac.jobdu.com/problem.php?pid=1390
* 结果:AC
* 来源:剑指Offer
* 总结:
**********************************/
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
//F(n) = F(n-1) + F(n-2)
long long Fibonacci(int n){
int i;
long long fibonacciA = 1;
long long fibonacciB = 2;
long long fibonacciC;
if(n == 1){
return fibonacciA;
}
else if(n == 2){
return fibonacciB;
}
for(i = 3;i <= n;i++){
fibonacciC = fibonacciA + fibonacciB;
fibonacciA = fibonacciB;
fibonacciB = fibonacciC;
}
return fibonacciC;
}
int main()
{
int i,n;
while(scanf("%d",&n) != EOF){
printf("%lld\n",Fibonacci(n));
}
return 0;
}
代码
/*---------------------------------------
* 日期:2015-07-19
* 作者:SJF0115
* 题目: 3.矩形覆盖
* 网址:http://www.nowcoder.com/books/coding-interviews/72a5a919508a4251859fb2cfb987a0e6?rp=1
* 结果:AC
* 来源:剑指Offer
* 博客:
-----------------------------------------*/
#include <iostream>
using namespace std;
class Solution {
public:
int rectCover(int n){
if(n < 0){
return 0;
}//if
else if(n == 1 || n == 0){
return 1;
}//else
else if(n == 2){
return 2;
}//else
return rectCover(n-1) + rectCover(n-2);
}
};
int main(){
Solution s;
int number = 4;
cout<<s.rectCover(number)<<endl;
return 0;
}
分享到:
相关推荐
面试题 1:二维数组中的查找(考点: 数组) 1 面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: 链表) 2 面试题 4:重建二叉树(考点: 树) 4 ...面试题 10:矩形覆盖(考点: 递归和循环) 8
剑指offer 1.二位数组中的查找 2.替换空格 3.单链表:从尾到头打印链表 4.二叉树:重建二叉树 5.栈:用两个栈实现队列 6.旋转数组的最小数字 7.斐波那契数列 8.跳台阶 9.变态跳台阶 10.矩形覆盖 11.二进制中1的个数 12....
剑指offer代码实现,通过。 # Title Solution Tag Note LeetCode 1 二维数组中的查找 数组 2 替换空格 字符串 3 从尾到头打印链表 链表 4 重建二叉树 树 5 用两个栈实现队列 栈和队列 LeetCode 232 6 旋转数组的最小...
【Python学习-递归-斐波那契数列】【剑指offer】之跳台阶题目分析代码变态跳台阶分析代码矩形覆盖分析代码 题目 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序...
Coding-InterviewsCoding-Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的...
Leetcode、剑指 offer等笔试题集合 SwordtoOffer ReConstructBinaryTree:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 QueueByStack:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的...
该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. Search a 2D Matrix II ...
《剑指Offer》 练习题 经典算法大全 leetcode 学习进度 ####递归 递归 cn.diyai.recursion.Recursion 斐波那契数列 跳台阶 cn.diyai.algorithmics.JumpTool 变态跳台阶 矩形覆盖 三角数字 阶乘 递归的二分查找 汉诺...
1、牛客网《剑指offer》二刷(二刷结束) 2、LeetCode (持续练习中,为了速度都是.java文件,不再写Markdown文件) 1、牛客网《剑指offer》二刷(二刷结束) 1、二维数组的查找 2、替换空格 3、从尾到头打印链表 4、...
剑指Offer 考点 题目 解法 难度 字符串 替换空格 易 字符串 字符串旋转 易 数组 二维数组中的查找 难 数组 旋转数组的最小数字 难 数组 打印1到最大的n位数 难 栈和队列 用两个栈实现队列 中 链表 从尾到头打印链表 ...
剑指Offer编程题目录 二维数组中的查找: 替换空格: 从尾到头打印链表: 重建二叉树: 用两个栈来实现队列: 旋转数组的最小数字: 斐波那契数列: 跳台阶: 跳台阶2: 矩形覆盖: 二进制中1的个数 数值的整数次方: 调整数组...
在指定空间中创建对象数组去重时间格式化获取字符串长度邮箱字符串判断颜色字符串转换字符串转为驼峰格式字符串字符统计剑指offer二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的...