母牛数量算法

mymsammy

母牛能活100岁么？

ftInternet

原帖由 loveguohuasai 于 2003-8-3 17:14 发表
若一头小母牛，从出生起第四个年头开始每年生一头母牛，按此规律，第n年有多少头母牛？

哈哈，这个牛品种很好啊。无性繁殖，还能算准是生母牛。厉害！

难道传说中的女儿国进化成女牛国了

mcknight

为什么不用解构呢？
struct cow
{
  int date_of_birth; //mark when the cow is born
  int num_of_children; //sum up all its children
}
再定义一个Cow[MAXNUM],生一头就在Cow数组加一个成员，最后一统计不久可以了吗

earl808

第n年能生小牛的牛为(n>=
f(n)=f(n-1)+f(n-3)//n-1年能生小牛的牛 加上n-3年前生出来的在第n牛能生小牛的牛
第n牛不能生小牛的牛为
g(n)=f(n)+f(n-1)+f(n-2)

后面的不会算了..那个3次方的齐次方程好恐怖..

小飞爱使申华

4年前的老帖子，顶一个，怀旧一下。。。

redspider

这贴生命力够强

robin10

...非常有幸。。。。能够看到司马迁的的一些手记`~呵呵，还是学到了不少东西~~~
仅此留名。。。
XX到次一览~~~
// added by XX 20070807
(偶刚看了那个注释后面加 //mod by xx的帖~~~ )

leeon868

很显然，这类递归。

long num_cow(int n){
   return (n < 4) ? 1 : num_cow(n-1) + num_cow(n-3);
}

还有这样的代码。

#include <stdio.h>;

int cow(int n)
{
  unsigned long sum = 1, i;

  if (n <= 3) sum += 0;
  else {
        for (i = 4; i <= n; i++)
                sum += cow(i-3);
  }
  return(sum);
}

main()
{
  int n;

  printf("input n years, from 1\n");
  scanf("%d", &n);
  printf("total is %ld\n", cow(n));
}  

都是低效率的，这样的算法用大O记录，就是O(n^2)和O(n^3)的算法。如果是100的话。那简直消耗的时间恐怖到极点。

这样的算法，我就弄了个30，num_cow就作了79730步调用。

[ 本帖最后由 leeon868 于 2007-8-8 01:16 编辑 ]

leeon868

其实，这个题目还是说明了一个基本功：算法分析与设计。下面写一系列BTW。

BTW1：只要看到代码里数据保存使用的是int或者long，就说明写的代码就是不符合要求的，尽管某些算法是对的。

BTW2：其实第一页7楼的灰色轨迹写的代码就是对的，算法设计的很好而且而且递归调用的非常好，算法就像一个do...while循环，很容易改写为do...while循环，复杂度是O(n)的算法，存储空间就是栈上的空间，只不过函数写的仓促了点，代码组织上有些混乱，返回值用的是int，当然得不出正确的结论，其实应该对自己有信心一点，跟踪每一步all_cow的结果，很容易发现数据存储空间的溢出。很多人都闷头自己写自己的代码，也不看看前面别人写好的代码有什么长处。

BTW3：看到两个for循环叠加的那种，甭看，就不是最佳算法，虽然会得到正确结果，比如: flw写的那个链表，还有其他类似的用STL的那种，类似这样的代码，下面是flw的代码片段：

for( int i=0; i<years; i++ ) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for( cow *ptr = cow::head; ptr != NULL; ptr = ptr->next ) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ptr->grow();

for()循环里面再套一个for()，即便有空间展开算法复杂度，也没有任何意义，复杂度是O(n^2)的算法，可以说把O(n^3)的算法复杂度减少了一点，而且分配了很多动态空间。尽管“按照”题目写的算法，结果一定是正确的。但是丝毫没有真正的数学分析和算法分析。就实际应用来说，确是最下乘的用法。

BTW4：整个帖子来说，唯一能解这个题目符合题目的，而且代码能处理正确的，能算到100年以上的，只有HopeCao写的代码。HopeCao的代码很好的解决了这个问题，根本不存在长度的问题，只要buffer足够大，得到的结果永远是对的。他的buffer是1024，是非常非常非常非常非常的大…… 是效率上，大量的strcpy是在不敢恭维。

BTW5：win_hate的算法分析和结果都是对的。用了maple写…… 如果结果和他的不相符，就一定是错的。可是这里可是C/C++版。太没面子了。

BTW6：我所看到的至少有8份以上的代码是错的，根本就没有理解题意。也没有验证数据的正确性就贴上来了。如果你是程序员的话，要对自己的代码负责，即便有一行代码，有一天也需要维护。

BTW7：用f(n) = f(n-1) + f(n-3)，直接写代码的，算法分析方面前进了一大步，恭喜，解题来说，是对的，但是你将很难的到答案，算法设计上却是非常得差劲。为什么这么慢？调用了两个f(n)这个函数，没有保存结果，而是一步步地计算，计算步骤数量，就是(n-1)阶乘+(n-3)的阶乘这么多。下面是计算10年的函数调用步骤结果：

No.1|year:3|quantity: 1
No.2|year:1|quantity: 1
No.3|year:4|quantity: 2
No.4|year:2|quantity: 1
No.5|year:5|quantity: 3
No.6|year:3|quantity: 1
No.7|year:6|quantity: 4
No.8|year:3|quantity: 1
No.9|year:1|quantity: 1
No.10|year:4|quantity: 2
No.11|year:7|quantity: 6
No.12|year:3|quantity: 1
No.13|year:1|quantity: 1
No.14|year:4|quantity: 2
No.15|year:2|quantity: 1
No.16|year:5|quantity: 3
No.17|year:8|quantity: 9
No.18|year:3|quantity: 1
No.19|year:1|quantity: 1
No.20|year:4|quantity: 2
No.21|year:2|quantity: 1
No.22|year:5|quantity: 3
No.23|year:3|quantity: 1
No.24|year:6|quantity: 4
No.25|year:9|quantity: 13
No.26|year:3|quantity: 1
No.27|year:1|quantity: 1
No.28|year:4|quantity: 2
No.29|year:2|quantity: 1
No.30|year:5|quantity: 3
No.31|year:3|quantity: 1
No.32|year:6|quantity: 4
No.33|year:3|quantity: 1
No.34|year:1|quantity: 1
No.35|year:4|quantity: 2
No.36|year:7|quantity: 6
No.37|year:10|quantity: 19


总共37步，如果是16年将增长到恐怖的377步，极其恐怖。算法，既要设计又要分析……

BTW8：果想处理正确，使用正确的数据类型，还有浮点类型了，不过浮点类型就没有任何意义了。windows下有__int64类型，不过还有一种类型，就是long long，没错是两个，c99标准中定义的类型，当然，比long还long。我这么定义的typedef unsigned long long qty_type; windows下也可以typedef unsigned __int64 qty_type;或许，有些人使用的是64位的操作系统呢？

BTW9：就算法分析还有递归的使用方面，推荐《Structure and Interpretation of Computer Programs》（SICP）这本书。北大裘宗燕老师翻译成了中文版。用lisp描述的，只有递归，没有迭代……

BTW10：我是第一次来这个论坛，就是找点资料用用，没想到看到这个热帖，忍不住多说几句。

夜深了，该睡觉了，明天还要分析数据……

最后给出结果，那个楼主，貌似2003年就不来了……

又简单又好用的答案，代码也不用重新写了，简单整理了灰色轨迹的代码就足够用了，而且很容易就可以修改为迭代类型的代码，

代码在WinXP SP2 VC2005 SP1和ubuntu7.04 g++4.1下测试通过。代码如下：

01  #include <iostream>
02  using namespace std;
03  
04  typedef unsigned long long qty_type ;
05  
06  int i = 0;
07  
08  qty_type cow( qty_type all_cow, qty_type can_born, qty_type i_born, qty_type ii_born, qty_type iii_born, qty_type year )
09  {
10      all_cow += can_born;
11      can_born += iii_born;
12      iii_born = ii_born;
13      ii_born = i_born;
14      i_born = ( all_cow - ii_born - iii_born ) > can_born ? ( all_cow - ii_born - iii_born ) : can_born;
15      cout << ++i << ": " << all_cow << endl;
16      return ( !year ) ? all_cow : cow( all_cow, can_born, i_born, ii_born, iii_born, --year );
17  }
18  
19  
20  int main( int argc, char* argv[] )
21  {
22      cow( 1, 0, 1, 0, 0, 99 );
23  }

正确的结果100年内：
1: 1
2: 1
3: 1
4: 2
5: 3
6: 4
7: 6
8: 9
9: 13
10: 19
11: 28
12: 41
13: 60
14: 88
15: 129
16: 189
17: 277
18: 406
19: 595
20: 872
21: 1278
22: 1873
23: 2745
24: 4023
25: 5896
26: 8641
27: 12664
28: 18560
29: 27201
30: 39865
31: 58425
32: 85626
33: 125491
34: 183916
35: 269542
36: 395033
37: 578949
38: 848491
39: 1243524
40: 1822473
41: 2670964
42: 3914488
43: 5736961
44: 8407925
45: 12322413
46: 18059374
47: 26467299
48: 38789712
49: 56849086
50: 83316385
51: 122106097
52: 178955183
53: 262271568
54: 384377665
55: 563332848
56: 825604416
57: 1209982081
58: 1773314929
59: 2598919345
60: 3808901426
61: 5582216355
62: 8181135700
63: 11990037126
64: 17572253481
65: 25753389181
66: 37743426307
67: 55315679788
68: 81069068969
69: 118812495276
70: 174128175064
71: 255197244033
72: 374009739309
73: 548137914373
74: 803335158406
75: 1177344897715
76: 1725482812088
77: 2528817970494
78: 3706162868209
79: 5431645680297
80: 7960463650791
81: 11666626519000
82: 17098272199297
83: 25058735850088
84: 36725362369088
85: 53823634568385
86: 78882370418473
87: 115607732787561
88: 169431367355946
89: 248313737774419
90: 363921470561980
91: 533352837917926
92: 781666575692345
93: 1145588046254325
94: 1678940884172251
95: 2460607459864596
96: 3606195506118921
97: 5285136390291172
98: 7745743850155768
99: 11351939356274689
100: 16637075746565861

[ 本帖最后由 leeon868 于 2007-8-8 03:59 编辑 ]

redspider

ls太牛了 PF，没想到还有人能耐心看完21页帖子，并且分析出现的每一段代码，实在PF，不知道花了多长时间