首页 > 其他 > 详细

UVa 12459 - Bees' ancestors

时间:2015-06-10 08:51:13      阅读:260      评论:0      收藏:0      [点我收藏+]

题目:一只雌蜂有一个父亲和母亲,一只雄蜂只有一个母亲,问一只雄蜂的第n带祖先有多少个。

分析:递推,Fib数列。

            状态定义:设f(k)和m(k)分别为第k代祖先中雌蜂和雄蜂的数量;

            递推关系:f(k)= f(k-1)+ m(k-1)和 m(k)= f(k-1);

            递推整理:f(k)= f(k-1)+ f(k-2);f(1) = 1;f(2)= 2;

说明:使用long long防止溢出。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

long long F[100];

int main()
{
	F[1] = 1; F[2] = 2;
	for (int i = 3; i < 100; ++ i)
		F[i] = F[i-1] + F[i-2];
	
	int n;
	while (cin >> n && n)
		cout << F[n] << endl;
	
    return 0;
}

           

UVa 12459 - Bees' ancestors

原文:http://blog.csdn.net/mobius_strip/article/details/46437071

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!