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;
}