There is a cow, which gives birth to a heifer at the beginning of each year. Each heifer has a heifer at the beginning of each year since the fourth year. Please program how many cows are there in the

Input

The input data consists of multiple test cases , One line per test instance , Include an integer n(0<n<55),n The meaning of is described in the title .
n=0 Indicates the end of the input data , Don't deal with it .

Output

For each test case , The output is in the second n The number of cows in the year .
One line per output .

Sample input copy

2
4
5
0

Sample output copy

2
4
6

The code is as follows ：

Two ways of thinking , Recursion and dynamic programming

1, recursive

Recursion first considers the end condition of recursion --》 Serve as n==1 When Only one cow ,,return 1

In other cases ： The first n year The number of cattle is ：n-1 Number of years and The number of new cows born this year

, The number of new cows born this year -- Is the number of fertile cows this year -- Namely n-3 year Number of cows per hour

So we have to discuss n--- When n<=3 When There is only one fertile cow ,

Pseudo code ：

if (n == 1)
    {
        return 1;
    }
     if (n <= 3)
    {
        return number(n - 1) + 1;
    }
    else
    {
        return number(n - 1) + number(n - 3);
    }

This code is OK, but   It's easy to time out

Let's continue to consider

First year 1 head

In the second year 2 head

The third year 3 head

No new cows have been born in the past three years , And the number of cows is equal to the number of years

improvement ：

 if (n <= 3)
    {
        return n;
    }
    else
    {
        return number(n - 1) + number(n - 3);
    }

The code is as follows ：

#include<stdio.h>
int number(int n)
{
	/*if (n == 1)
	{
		return 1;
	}*/
	 if (n <= 3)
	{
		//return number(n - 1) + 1;
		return n;
	}
	else
	{
		return number(n - 1) + number(n - 3);
	}
}
int main()
{

	int arr[1000]={0};
	int n = 0;
	int i = 0;
	scanf("%d", &n);
	while (n != 0)
	{
		arr[i] = n;
		i++;
		scanf("%d", &n);
	}
	for (i = 0; arr[i] != '\0'; i++) {
		printf("%d\n", number(arr[i]));
	}
	return 0;
}

 

The second method ： Dynamic programming --- It's about finding the rules

equally -- Don't go to this more abstract problem look for N The number of cattle corresponding to the year ,,, This will be more difficult ,, We introduce an array ,, Number of cattle stored every year , Horizontal law finding ,, The essential idea is the same as recursion ,

The code is as follows ：

#include<stdio.h>
int main()
{

	int arr[1000]={0};
	int n = 0;
	int i = 1;
	scanf("%d", &n);
	int max = n;
	while (n != 0)
	{
		arr[i] = n;
		i++;
		if (n >= max)
		{
			max = n;
		}
		scanf("%d", &n);
	}

	int number[1000] = { 0 };// The number of cows in the corresponding year 
	for (i = 1; i <= max; i++)
	{
		if (i <= 3)
		{
			number[i] = i;
		}
		else
		{
			number[i] = number[i - 1] + number[i - 3];
		}
	}

	for (i = 1; arr[i] != '\0'; i++)
	{
		printf("%d\n", number[arr[i]]);
	}
	return 0;

}

Take a look at the speed of two codes （ The top one is for Dynamic programming solution

 

obviously ----- Dynamic programming   ---- still Be quick

Try dynamic programming Fibonacci sequence ~！@#￥%……&*（