学步园

#include <iostream><br /> #include "windows.h"<br /> using namespace std;<br /> /*-----------------------------------<br /> 母牛生小牛Problem<br /> 设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？<br /> Input<br /> 本题有多组数据。每组数据只有一个整数N，独占一行。(1≤N≤50) </p> <p>Output<br /> 对每组数据，输出一个整数（独占一行）表示第N年时母牛的数量 </p> <p>Sample Input<br /> 1<br /> 4<br /> 5<br /> 20</p> <p>Sample Output<br /> 1<br /> 2<br /> 3<br /> 872<br /> -----------------------------------*/<br /> /*----------------------------------<br /> 1 1 1 2 3 4 6 9 13 19 28 ...<br /> 后一项 等于 前x-1项 + x-3 之和<br /> f(x) = f(x-1) + f(x-3)<br /> 特殊的斐波那契数列<br /> -----------------------------------*/<br /> int MuNiu(const int& value){<br /> int sum[1000];<br /> sum[0] = sum[1] = sum[2] = 1;<br /> for(int i = 3 ;i < value;i++){<br /> sum[i] = sum[i - 1] + sum[i - 3];<br /> }<br /> return sum[value-1];<br /> }<br /> int MuNiu2(const int& value){<br /> if(value <= 3){<br /> return 1;<br /> }else{<br /> return MuNiu2(value - 1) + MuNiu2(value - 3);<br /> }<br /> }<br /> int main(){</p> <p> DWORD a = ::GetTickCount();<br /> cout<<MuNiu(50)<<endl;<br /> DWORD b = ::GetTickCount();<br /> DWORD c = b - a;<br /> cout<<c<<endl;</p> <p> a = ::GetTickCount();<br /> cout<<MuNiu2(50)<<endl;<br /> b = ::GetTickCount();<br /> c = b - a;<br /> cout<<c<<endl;<br /> return 0;<br /> }