Bailian4108 羚羊数量-Number Of Antelope【递推+打表+递归+记忆化递归】

本文主要是介绍Bailian4108 羚羊数量-Number Of Antelope【递推+打表+递归+记忆化递归】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

4108:羚羊数量-Number Of Antelope
总时间限制: 1000ms 内存限制: 65536kB
描述
草原上有一种羚羊,假设它们出生时为0岁,那么经过3年的成长,当它们在3岁的时候会成年,并开始繁殖。每一对羚羊在3岁的那一年会产下两只小羚羊,并且这对成年羚羊结为永久的伴侣,在以后的每一年又生出两只小羚羊。

假定一对羚羊产下的两只小羚羊必定为一雄一雌,羚羊在3岁时必定会找到另外一只同年羚羊结为永久伴侣,并开始繁殖。此外,假定这种羚羊在50岁以内不会死去。

如果在第0年,草原上有一对0岁的羚羊,那么第n年末草原上有多少对羚羊?

例如,第1年和第2年,草原上有1对羚羊;第3年,由于这对羚羊成年了,它们会生下一对羚羊,因此第3年末草原上有2对羚羊。

输入
第一行是一个正整数m(1<=n<=15),表示共有m个问题。
下面m行,每行是一个数字n(0<=n<=40),表示第n年。
输出
总共m行,每行一个数字,表示相应的第n年末草原上有几对羚羊。
样例输入
3
1
3
4
样例输出
1
2
3
提示
结果不会超出int范围

问题链接:Bailian4108 羚羊数量-Number Of Antelope
问题简述:(略)
问题分析
    本题类似于菲波那契数列问题,关键是递推式,前几项需要自己算出来。递推式是f(n)=f(n-3)+f(n-1)。打表是好的做法,可以减少重复计算的次数。
程序说明:(略)
参考链接:(略)
题记:(略)

AC的C语言程序(打表)如下:

/* Bailian4108 羚羊数量-Number Of Antelope */#include <stdio.h>#define N 40
int a[N + 1];void init(int n)
{int i;a[0] = 1;a[1] = 1;a[2] = 1;for(i = 3; i <= n; i++)a[i] = a[i - 3] + a[i - 1];
}int main(void)
{init(N);int m, n;scanf("%d", &m);while(m--) {scanf("%d", &n);printf("%d\n", a[n]);}return 0;
}

AC的C语言程序(递归)如下:

/* Bailian4108 羚羊数量-Number Of Antelope */#include <stdio.h>int fib(int n)
{if (n == 0) return 1;else if (n == 1) return 1;else if (n == 2) return 1;else return fib(n - 3) + fib(n - 1);
}int main(void)
{int m, n;scanf("%d", &m);while (m--) {scanf("%d", &n);printf("%d\n", fib(n));}return 0;
}

AC的C语言程序(记忆化递归)如下:

/* Bailian4108 羚羊数量-Number Of Antelope */#include <stdio.h>
#include <string.h>#define N 40
int a[N + 1];int fib(int n)
{if (a[n]) return a[n];else if (n == 0 || n == 1 || n == 2) return a[n] = 1;else {if (a[n - 3] == 0)a[n - 3] = fib(n - 3);if (a[n - 1] == 0)a[n - 1] = fib(n - 1);return a[n - 3] + a[n - 1];}
}int main(void)
{memset(a, 0, sizeof a);int m, n;scanf("%d", &m);while (m--) {scanf("%d", &n);printf("%d\n", fib(n));}return 0;
}

这篇关于Bailian4108 羚羊数量-Number Of Antelope【递推+打表+递归+记忆化递归】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL精准控制Binlog日志数量的三种方案

《MySQL精准控制Binlog日志数量的三种方案》作为数据库管理员,你是否经常为服务器磁盘爆满而抓狂?Binlog就像数据库的“黑匣子”,默默记录着每一次数据变动,但若放任不管,几天内这些日志文件就... 目录 一招修改配置文件:永久生效的控制术1.定位my.cnf文件2.添加核心参数不重启热更新:高手应

mysql递归查询语法WITH RECURSIVE的使用

《mysql递归查询语法WITHRECURSIVE的使用》本文主要介绍了mysql递归查询语法WITHRECURSIVE的使用,WITHRECURSIVE用于执行递归查询,特别适合处理层级结构或递归... 目录基本语法结构:关键部分解析:递归查询的工作流程:示例:员工与经理的层级关系解释:示例:树形结构的数

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

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 <=

uva 10916 Factstone Benchmark(打表)

题意是求 k ! <= 2 ^ n ,的最小k。 由于n比较大,大到 2 ^ 20 次方,所以 2 ^ 2 ^ 20比较难算,所以做一些基础的数学变换。 对不等式两边同时取log2,得: log2(k ! ) <=  log2(2 ^ n)= n,即:log2(1) + log2(2) + log2 (3) + log2(4) + ... + log2(k) <= n ,其中 n 为 2 ^

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大