UVA 11000- Bee 递推-白红宇

UVA 11000- Bee 递推

阅读量：5107 次

发布时间：2019-06-13

本文共 1726 字，大约阅读时间需要 5 分钟。

In Africa there is a very special species of bee. Every year, the female bees of such species give birth

to one male bee, while the male bees give birth to one male bee and one female bee, and then they die!

Now scientists have accidentally found one “magical female bee” of such special species to the eﬀect

that she is immortal, but still able to give birth once a year as all the other female bees. The scientists

would like to know how many bees there will be after N years. Please write a program that helps them

ﬁnd the number of male bees and the total number of all bees after N years.

Input

Each line of input contains an integer N (≥ 0). Input ends with a case where N = −1. (This case

should NOT be processed.)

Output

Each line of output should have two numbers, the ﬁrst one being the number of male bees after N

years, and the second one being the total number of bees after N years. (The two numbers will not

exceed 232.)

Sample Input

-1

Sample Output

1 2

4 7

题意：蜜蜂，每年每只雄蜂产下一只雌蜂和一只雄蜂，每只雌蜂产下一只雄蜂，然后就死去，现在发现了一只不会死的雌蜂，问以她为起始点，第N年有多少雄蜂和一共多少蜜蜂。

题解：设第i年的雄蜂和雌蜂分别为a（i）与s（i），则有如下递推关系：

1 s（i）= a（i-1）+ 1

2 a（i）= s（i-1）+ a（i-1）

整理得：a（i）=a（i-1）+ a（i-2）+ 1；

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include
            
             #include 
             using namespace std ;typedef long long ll;const int N=100+10;const int maxn = 1e9 + 1;ll a[N];void init() { a[1] = 1; a[0] = 0; for(int i=2;i<=N;i++) a[i] = a[i-1] + a[i-2] +1ll;}int main() { init(); int n; while(~scanf("%d",&n)) { if(n == -1) break; printf("%lld %lld\n", a[n] , a[n+1]); } return 0;}