Sicily 1029. Rabbit
2010-05-14 17:15:36| 分类：
递推
| 标签：
|举报
|字号大中小 订阅
题目链接：
http://www.sicily.3322.org/show_problem.php?pid=1029 这题需要用高精度加法。递推关系是 f [n] = f [n - 1] + f [n - m] （其中 n 为月数，m 为题中的每对兔子长大成为成年兔子需要的月数）。
关于递推关系的解释： 这个月兔子的总数 ＝ 上个月兔子的总数 + 新出生兔子的总数。而新出生兔子的总数 ＝ n － m 个月前兔子的总数，因为那时新出生的幼年兔子到这个月已经变成了成年兔子可以生育，而那时其他的兔子当然也可以生育，即到 n 个月时，n － m 个月前的全部兔子都会生兔子，而在 n － m 个月 和 n 个月之间新出生的兔子到 n 个月时是没有生育能力的。代码如下：
#include <iostream> #include <cstdio> #include <cstring> using namespace std;
int f[110][51]; void init(
int idx, int num)
//初始化 m 个月前兔子的总数 { for (
int i = 50;
num != 0 && i >= 0;
i --)
{ f[idx][i] = num % 10;
num /= 10;
} } void addition(
int idx, int m)
//高精度加法 { int temp;
for (
int i = 50;
i >= 1;
i --)
{ temp = f[idx][i]; f[idx][i] = (
temp + f[idx - 1][i] + f[idx - m][i]) % 10;
//注意是先加再模 f[idx][i - 1] = (
temp + f[idx - 1][i] + f[idx - m][i]) / 10;
//注意是先加再除 } } int main()
{ //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int m, d, c;
while (
scanf(
"%d%d", &m, &d), m > 0 && d > 0)
{ memset(
f, 0, sizeof(
f));
for (
int i = 0;
i <= d;
i ++)
{ if (
i <= m)
init(
i, i + 1);
//初始化 m 个月前兔子的总数 else addition(
i, m);
//递推兔子的总数 } for (
int i = 0;
i <= 50;
i ++)
//去掉结果开头的 0 。 { if (
f[d][i] != 0)
{ c = i;
break;
} } for (
int i = c;
i <= 50;
i ++)
printf(
"%d", f[d][i]); printf(
"\n");
} return 0;
}
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论