SDUTOJ 1018 骨牌铺方格 递推

2024-08-24 23:32
文章标签 递推 1018 sdutoj 方格 骨牌

本文主要是介绍SDUTOJ 1018 骨牌铺方格 递推,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:

输入

输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。

输出

对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。

示例输入

1
3
2

示例输出

1
3
2
 
如果往后多推几个的话,不难发现其实它就是一个斐波那契数列的一部分...
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>using namespace std;long long s[52];int main()
{int i,n;s[1]=1;s[2]=1;for(i=3;i<51;i++){s[i]=s[i-1]+s[i-2];}while(~scanf("%d",&n)){printf("%lld\n",s[n]);}return 0;
}

这篇关于SDUTOJ 1018 骨牌铺方格 递推的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103911

相关文章

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

HLJUOJ1128 HDU2046(数学递推)

1128: 递推求解专题练习三 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 8   Solved: 6 [ Submit][ Status][ Web Board] Description 在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数。 例如n=3时,为2× 3方格,骨牌的铺放方案有三

POJ 1018 Communication System(枚举)

题目: http://poj.org/problem?id=1018 题解: 我们可以枚举每一种B可能的值,然后寻找每一行里大于等于B里最小的P。 代码: #include<cstdio>#include<stdlib.h>struct in{double B,P;}a[101][101];double b[10001];int t[101];int cmp(cons

蓝桥杯第八届 方格分割(dfs)

标题:方格分割6x6的方格,沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图:p1.png, p2.png, p3.png 就是可行的分割法。试计算:包括这3种分法在内,一共有多少种不同的分割方法。注意:旋转对称的属于同一种分割法。请提交该整数,不要填写任何多余的内容或说明文字。   观察可得他是一个中心对称图形,我们只需要搜索它的对称线即可。我们可以把对称线抽象为从(

【递推】【DP】-HDU-2064-汉诺塔③

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2064 题目描述:从最左边移到最右边柱子的过程中必须经过中间柱子。 解题思路: 进ACM组时候的考试题,当时虐我的题终于被我虐回来了。。一眼看出方程,1A了。。。呵呵。。满足一下我的虚荣心,,,抚慰一下受挫的心灵吧。 AC代码: #include <iostream>using names

【递推】【DP】-HDU-1996-汉诺塔⑥

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1996 题目描述:问三个柱子上放N个盘子,一共可能有多少种组合?(可以有柱子不放,放的时候依然满足下面盘子比上面盘子大) 解题思路: 对于放N个盘子,ans [ N ] = 3 + 6 * f ( N ) +6 * g ( N ) 这三项依次代表这N个盘子分成一堆,两堆,三堆时有多少种可能。排列

【递推】【DP】-HDU-1995-汉诺塔⑤

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1995 题目描述:计算汉诺塔中某个盘子的移动次数 解题思路: 想了好久,突然顿悟! 思路如下,所谓递推,即是前者与后者存在直接联系,由前者可以直接推出后者,因此必须有一端是已知的,这题里显然最下面的盘子只被动了一次,这就是开端,然后我们考虑紧挨着的两张盘子的递推关系,发现上面盘子是紧挨着的下面盘

【递推】【DP】-HDU-1207-汉诺塔②

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1207 题目描述:四柱汉诺塔 解题思路: 开始想了方程 f [ n ] = 2 * f [n - 2] + 3和 f [ n ] = 2 * f [n - 3] + 7。结果都不对,很郁闷,纠结半天之后,上网查攻略去了,啊!我就差一点了,但也是差了最为关键的一步! 正确的方程应该是: f [

蓝桥杯备赛day02:递推

斐波那契数列 #include <bits/stdc++.h>using namespace std;int main(){int n;cin>>n;int dp[n+1];dp[1]=1;dp[2]=1;for(int i = 3;i <= n;i++) dp[i] = dp[i-1]+dp[i-2];cout<<dp[n];return 0;} n = int(input())

递推—杭电2044 一只小蜜蜂...

http://acm.hdu.edu.cn/showproblem.php?pid=2044 一只小蜜蜂... Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 35811    Accepted Submission(s): 1317