有一个农场,有一头小母牛,它到了四岁的时候就可以生一头小牛,以后的每年都可以生一头,到了十三年后这这头可以生多少头牛,(它生的小年到了四年的时候也可以生小牛)
希望师兄们给我点意见并且最好给点注释,因为老师会问我这步是干什么的?
/*---------------------------------------------------------------------------
File name: bccn-Heifer-right.cpp
Author: HJin
Date: 6/13/2007
*/
/**
Recurrence formula for f(n), where n is the year
number. Now is year 1.
f(n) = f(n-3) + f(n-1), if n>=4
= 1, if n<=3
This formula is very similar to the famous Fibonacci formula.
One can solve this recurrence equation mathematically, using the
three roots, x_1, x_2, x_3, of
x^3 - x^2 -1 = 0.
You can solve the cubic equation using Cardano formula:
x_1 ~ 1.47, x_2 ~-0.23 + 0.79 i, x_3 = complex conjugate of x_2
To compute it programatically, you can use aipb2007's recursive formula.
Or use my two formulae below.
Sample output:
Year No.| iterative | recursive
--------+-----------+-----------
1 | 1 | 1
2 | 1 | 1
3 | 1 | 1
4 | 2 | 2
5 | 3 | 3
6 | 4 | 4
7 | 6 | 6
8 | 9 | 9
9 | 13 | 13
10 | 19 | 19
11 | 28 | 28
12 | 41 | 41
13 | 60 | 60
14 | 88 | 88
15 | 129 | 129
16 | 189 | 189
17 | 277 | 277
18 | 406 | 406
19 | 595 | 595
20 | 872 | 872
21 | 1278 | 1278
22 | 1873 | 1873
23 | 2745 | 2745
24 | 4023 | 4023
25 | 5896 | 5896
26 | 8641 | 8641
27 | 12664 | 12664
28 | 18560 | 18560
29 | 27201 | 27201
30 | 39865 | 39865
31 | 58425 | 58425
Press any key to continue . . .
*/
#include <iostream>
using namespace std;
/**
Iterative soln: time complexity is O(n); i.e., linear growth.
Space complexity is O(1).
*/
int f_iterative(int n);
/**
Recursive soln: time complexity is O(2^n); i.e., exponential growth.
*/
int f_recursive(int n);
int main()
{
int i;
cout<<"Year No.| iterative | recursive\n";
cout<<"--------+-----------+-----------\n";
for(i=1; i<32; ++i)
{
cout<<i<<"\t| "<<f_iterative(i)<<"\t | "<<f_recursive(i)<<endl;
}
return 0;
}
int f_iterative(int n)
{
int f0=1; // tracks f(n-3)
int f1=1; // tracks f(n-2)
int f2=1; // tracks f(n-1)
int res=1;
int i;
for(i=3; i<n; ++i)
{
res = f0+f2;
// update the tracking
f0 = f1;
f1 = f2;
f2 = res;
}
return res;
}
int f_recursive(int n) // simply the formula
{
if(n<=3)
return 1;
else
return f_recursive(n-3) + f_recursive(n-1);
}
[此贴子已经被作者于2007-6-14 2:09:54编辑过]