母牛生小牛
Problem
設有一頭小母牛,從出生第四年起每年生一頭小母牛,按此規律,第N年時有幾頭母牛?
Input
本題有多組資料。每組資料隻有一個整數N,獨占一行。(1≤N≤50)
Output
對每組資料,輸出一個整數(獨占一行)表示第N年時母牛的數量
Sample Input
1
4
5
20
Sample Output
1
2
3
872
核心算法:// func(year-3) 是老母牛1頭 因為前三年隻有1頭母牛 func(year-1)第二代牛數量沒1年産1頭
return (func(year-3)+func(year-1));
解題思路:
//第一代永遠都是1個
//第二代從第4年開始,每年加一個
//第三代從第7年開始,由上一代個數決定每個産一個
//第四代從第10年開始由上一代個數決定每個産一個
//問題的實質是:從新牛出生起就開始了同一個問題原問題的第1年就是新牛出生的那一年
代碼如下:
#include "stdafx.h"
#include
#include
using namespace std;
int a[100]={0,1}; //a[i]村第i代的數量 a[0]總數量
//問題的實質是:從新牛出生起就開始了同一個問題 原問題的第1年就是新牛出生的那一年
int func(int year)
{
if(year<4) //隻有1頭牛時 頭三年隻有原本的母牛1頭
{
return 1;
}
else
{
// func(year-3) 是老母牛1頭 因為前三年隻有1頭母牛 func(year-1)第二代牛數量沒1年産1頭
return (func(year-3)+func(year-1));
}
}
int main(int argc, char* argv[])
{
ifstream in("a.txt");
int n;
while(in>>n)
{
cout<< func(n)<
}
return 0;
}