[求助]C++题目

/*---------------------------------------------------------------------------
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编辑过]

那个大哥帮帮小弟吧!

小牛到了它四岁的时候就可以生小牛,它生的小牛到了四岁的时候也可以生小牛依次类推!

先数学分析一下
30年后：
第一头可以产 13 - 3 = 10 头
第一头产的第一头小牛可以产： 13 - 8 = 5头
。。。。。。2 13 - 9 = 4
..........

从第4年起每年增加的能生的母牛数跟第1年起总牛数一一对应...

如果是3年一生 那就是fib 数列了``1 1 2 3 5 8 13...............

谢谢了,不愧是高手啊! 没错就是60头

LS的，
1-2-3-4-5-6-7-8-9 -10-11-12-13 年
1-1-1-2-3-4-5-7-10-14-19-26-36 头

第7年开始就错了哦！
7的年，本身母牛生一头，它在4的年生的女儿生一头（可以生育了）。所以在上一年的基础上多了两头，该是4+2=6头。
这里都错了，后面就不说了哈！



第4年出生的那头 要在后面第4年才能再生啊....也就应该是第8年啊! 如果你这样看那就的确是~
我以为后面1年是第1年 道理都一样

按照斑竹的:

1-2-3-4-5-6-7-8-9 -10-11-12-13 年
1-1-1-2-3-4-6-9-13-19-28-41-60 头
这题 只抓每年能生的母牛数就行了``

从16楼开始看！

You catch the main step of a good algorithm. Though you may not wrote the right code, however, what you thought is really good.
See the code on 3 floor, he has made the perfect program for that algorithm!

以下是引用aipb2007在2007-6-14 14:39:45的发言：
I saw your new respond for this problem at 3f. Very good, as you said, it's really like fibnacci numbers.
It's so easy to understand fibnacci numbers, but when come to this problem,I never think abt that.

In addition, every time you solve a problem, you have a good style to write you analysis and detailed comment.Do you follow some templet or whatever?

1. This problem is really a math problem. Do you agree?

2. There are some good C++/C coding style "standards" out there. I personally used some source code beautifier: say sourceFormatX (this program is very very very risky --- it may delete your windows registry if you use the shareware version!!! Google sourceFormatX and 看雪 for it), greatcode (open source @ sourceforge, and my own simple beautifier written in C++.

Best of the luck!