文档章节

【九度OJ1390】|【剑指offer9】斐波那契数列之矩形覆盖

aqia358
 aqia358
发布于 2013/10/18 09:12
字数 281
阅读 46
收藏 0
题目描述:

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

输入:

输入可能包含多个测试样例,对于每个测试案例,

输入包括一个整数n(1<=n<=70),其中n为偶数。

输出:

对应每个测试案例,

输出用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有的方法数。

样例输入:
4
样例输出:
5

分析:把2约掉本题即为基本的斐波那契数列求值问题


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * 斐波那契数列之矩形覆盖 
 * @author aqia358
 *
 */
public class Main {

	public static long f(int n){
		long[] a = new long[n+3];
		a[0] = 0;
		a[1] = 1;
		a[2] = 2;
		int pos = 3;
		while(pos <= n){
			a[pos] = a[pos-1] + a[pos-2];
			pos++;
		}
		return a[n];
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(st.nextToken() != st.TT_EOF){
			System.out.println(f((int)st.nval));
		}
	}

}





© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
私信 提问
剑指Offer学习总结-斐波那契数列

剑指Offer学习总结-斐波那契数列 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.163....

wwlcsdn000
01/17
0
0
剑指offer-010-斐波那契数列

问题:写一个函数,输入n,求斐波那契数列的第n项。斐波那切数列的定义如下: 一般算法:递归(时间复杂度O(2^n)) 递归解法写起来很简单,但是效率极差,因为它在不停的重复计算,根据上图就...

triorwy
01/22
0
0
剑指offer 矩阵覆盖

题目描述 我们可以用 2 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个 2 1的小矩形无重叠地覆盖一个 2 * n的大矩形,总共有多少种方法? 思路 竖着的长度为n,横的长度为2 n = 1,明显只...

云胡_
2017/11/25
0
0
重点汇总-python-gitbook-重要点学习-4-数据结构/编程题

数据结构 - 红黑树 红黑树与AVL的比较: AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多; 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低;...

时间之友
2017/12/21
0
0
[剑指offer] 斐波那契数列

本文首发于我的个人博客:尾尾部落 题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39 解题思路 公式: f(n) = n, n <= ...

繁著
08/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C4C销售订单行项目价格维护方法

需求很简单,能够创建销售订单,在行项目里添加产品,带出价格来,同时把总价显示在销售订单抬头区域。 如下图所示: 下面是具体配置。 Business Configuration里,点击Sales Order的配置: ...

JerryWang_SAP
39分钟前
9
0
deepin中配置robot framework环境

本文永久更新地址:https://my.oschina.net/bysu/blog/2989005 【若要到岸,请摇船:开源中国 不最醉不龟归】 1.在终端中输入pip,回车,如果提示没有该命令,则先安转pip sudo apt-get inst...

不最醉不龟归
今天
8
0
OSChina 周日乱弹 —— 钱不还,我就当你人不在了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享Bigleaf的单曲《小鹿》 《小鹿》- Bigleaf 手机党少年们想听歌,请使劲儿戳(这里) 周日在家做什么? 做手工呀, @poorfis...

小小编辑
今天
200
5
EOS docker开发环境

使用eos docker镜像是部署本地EOS开发环境的最轻松愉快的方法。使用官方提供的eos docker镜像,你可以快速建立一个eos开发环境,可以迅速启动开发节点和钱包服务器、创建账户、编写智能合约....

汇智网教程
今天
23
0
《唐史原来超有趣》的读后感优秀范文3700字

《唐史原来超有趣》的读后感优秀范文3700字: 作者:花若离。我今天分享的内容《唐史原来超有趣》这本书的读后感,我将这本书看了一遍之后就束之高阁了,不过里面的内容一直在在脑海中回放,...

原创小博客
今天
33
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部