Zzuli:1055 rabbit reproduction

Title Description

This is an interesting classical mathematical problem , Famous Italian mathematician Fibonacci A question was raised ： There's a couple of rabbits , From the day after birth 3 A couple of rabbits are born every month from . The little rabbit grows to the third place 3 Two months later, a couple of rabbits were born every month . According to this rule , Suppose no rabbits died , In the first month, there was a couple of newborn rabbits , Ask No n How many pairs of rabbits in a month ？

Input

Enter the number of months n（1<=n<=44）.

Output

Output No n How many pairs of rabbits in a month .

The sample input  Copy

3

Sample output  Copy

2

Tips

This topic is a classic introduction to recursion ： use f(n) It means the first one n Number of rabbits in months , be ： f(n) = f(n-1) + Number of rabbits born this month and , Number of rabbits born this month = f(n-2) ( Because every rabbit that existed last month , A new rabbit will be born this month ） therefore ,f(n) = f(n-1) + f(n-2) That's the famous one fabinacci The sequence , The latter is equal to the sum of the first two ： 1 1 2 3 5 8.....

#include <stdio.h>
int main()
{
	int i,n,a=1,b=1,c;
	scanf("%d",&n);
	if(n==1)
	{
		printf("%d",a);
	}
	else
	{
		for(i=2;i<n;i++)
		{
			c=a;
			a=a+b;
			b=c;
		}
		printf("%d",a);
	}
	return 0;
}