母牛数量算法

flw

已经加上了释放内存的那一段了。

kj501

我用vector重新实现flw的算法，正好考验一下stl的健壮性。

1. 
   
2. #include<iostream>;
   
3. #include<vector>;
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Cow;
   
8. vector< class Cow *>; ver;
   
9. 
   
10. class Cow {
    
11.     int age;
    
12. public:
    
13.     Cow():age(0) {}
    
14.     void grow(void) {
    
15.       age++;                // 每年长了一岁。
    
16.       if ( age >;= 4 ) {     // 第四个年头起生小牛。
    
17.          ver.push_back(new Cow);
    
18.       }
    
19.    }
    
20. };
    
21. 
    
22. int main()
    
23. {
    
24.    int years = 40;  
    
25.    ver.push_back(new Cow);
    
26.    for( int i=0; i<years; i++ )
    
27.       for( int j=0; j<ver.size(); j++)
    
28.             ver[j]->;grow();
    
29.    //输出结果
    
30.    cout<<ver.size()<<endl;
    
31.    //释放内存
    
32.    for(int i=0; i<ver.size(); i++)
    
33.       delete ver[i];
    
34. }
    

复制代码

算到years=40时，出来的结果是1822473。计算years=50时就狂读硬盘了，所有我没有继续。由此看来stl的容器能够支持的元素个数是很大的，但不知道最大是多少，什么时候能溢出？

HopeCao

我也做了一个：

1. 
   
2. #include <stdlib.h>;
   
3. #include <stdio.h>;
   
4. 
   
5. #define MAX_STRING_LEN                128
   
6. 
   
7. static void Add(const char *, const char *, char *);
   
8. 
   
9. int main(int argc, char **argv)
   
10. {
    
11.         char        szCowCount[MAX_STRING_LEN];
    
12.         char        szLastCount3[MAX_STRING_LEN];
    
13.         char        szCount3[MAX_STRING_LEN];
    
14.         char        szCount2[MAX_STRING_LEN];
    
15.         char        szCount1[MAX_STRING_LEN];
    
16.         int                iYears;
    
17.         int                i;
    
18.        
    
19.         iYears = atoi(argv[1]);
    
20.         for (i = 1; i <= iYears; ++i)
    
21.         {
    
22.                 switch(i)
    
23.                 {
    
24.                         case 1:
    
25.                         case 2:
    
26.                         case 3:
    
27.                                 strcpy(szCowCount, "1");
    
28.                         break;
    
29.                         case 4:
    
30.                                 strcpy(szCowCount, "2");
    
31.                         break;
    
32.                         case 5:
    
33.                                 strcpy(szCowCount, "3");
    
34.                                 strcpy(szCount3, "1");
    
35.                                 strcpy(szCount2, "1");
    
36.                                 strcpy(szCount1, "1");
    
37.                         break;
    
38.                         default:
    
39.                                 if (strlen(szCowCount) >;= MAX_STRING_LEN)
    
40.                                         goto OUT;
    
41.                                 strcpy(szLastCount3, szCount3);
    
42.                                 Add(szCowCount, szCount3, szCowCount);
    
43.                                 //szCowCount = szLastCowCount + szCount3;
    
44.                                 Add(szCount3, szCount2, szCount3);
    
45.                                 //szCount3 += szCount2;
    
46.                                 strcpy(szCount2, szCount1);
    
47.                                 strcpy(szCount1, szLastCount3);
    
48.                         break;
    
49.                 }
    
50.         }
    
51. OUT:       
    
52.         printf("Yead:[%d]; Cow number:[%s].\n", iYears, szCowCount);
    
53. }
    
54. 
    
55. 
    
56. 
    
57. //
    
58. //  字符串数据相加.
    
59. //
    
60. static void Add(const char *pcFirst, const char *pcSecond, char *pcAdd)
    
61. {
    
62.         char        szFirstAdd[MAX_STRING_LEN];
    
63.         char        szAdd[MAX_STRING_LEN];
    
64.         int                i;
    
65.         int                iFirst;
    
66.         int                iSecond;
    
67.         int                iAdd;
    
68.         int                iFirstLen;
    
69.         int                iSecondLen;
    
70.         int                iMinLen;
    
71.         int                iOver = 0;
    
72.         int                n;
    
73.        
    
74.         iFirstLen = strlen(pcFirst);
    
75.         iSecondLen = strlen(pcSecond);
    
76.         if (iFirstLen < iSecondLen)
    
77.                 iMinLen = iFirstLen;
    
78.         else
    
79.                 iMinLen = iSecondLen;
    
80.         for (i = 0; i < iMinLen; ++i)
    
81.         {
    
82.                 szFirstAdd[i] = pcFirst[iFirstLen - i - 1] - 48 + pcSecond[iSecondLen - i - 1] + iOver;
    
83. 
    
84.                 if (szFirstAdd[i] - 48 >;= 10)
    
85.                 {
    
86.                         szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
    
87.                         iOver = 1;
    
88.                 }
    
89.                 else
    
90.                         iOver = 0;
    
91.         }
    
92.         if (iFirstLen >; iMinLen)
    
93.         {
    
94.                 for (; i < iFirstLen; ++i)
    
95.                 {
    
96.                         szFirstAdd[i] = pcFirst[iFirstLen - i - 1] + iOver;
    
97.                 if (szFirstAdd[i] - 48 >;= 10)
    
98.                 {
    
99.                         szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
    
100.                         iOver = 1;
     
101.                 }
     
102.                 else
     
103.                         iOver = 0;
     
104.                 }
     
105.         }
     
106.         else
     
107.         {
     
108.                 for (; i < iSecondLen; ++i)
     
109.                 {
     
110.                         szFirstAdd[i] = pcSecond[iSecondLen - i - 1] + iOver;
     
111.                 if (szFirstAdd[i] - 48 >;= 10)
     
112.                 {
     
113.                         szFirstAdd[i] = (szFirstAdd[i] - 48) % 10 + 48;
     
114.                         iOver = 1;
     
115.                 }
     
116.                 else
     
117.                         iOver = 0;
     
118.                 }
     
119.         }
     
120.         if (iOver == 1)
     
121.                 szFirstAdd[i++] = '1';
     
122.        
     
123.         for (n = 0; n < i; ++n)
     
124.                 szAdd[i - n - 1] = szFirstAdd[n];
     
125.         szAdd[i] = '\0';
     
126.         strcpy(pcAdd, szAdd);
     
127.        
     
128.         return;
     
129. }
     

复制代码

测试了几个跟flw兄的结果一致，不知道数字大了会不会错，请各位测试一下！
要是没有问题的话下次来讨论算法！！！

kj501

强，不过years只能算到767，768以上出来的数字全都一样。

sdupoplar

有没有注意，程序最后占了多少内存呢？

aero

这个版好久没这么热闹了。
一天没来，这么多code了，偶分析不过来了，太面了，落下了，来叫声好。

aero

看了后来的，又评论了一点，臭屁一下。

flw的算法的确是非常新颖，想法也非常的有创意。

但是，偶还是觉得不如偶的非递归算法好（嘻嘻）。

flw的算法中为每头牛创建了一个节点，异常庞大的内存消耗自不必说，偶觉得创建节点的开销也是蛮大的，因为毕竟不是原有的数据类型。在者，在每一年的循环中都要历遍一次链表，这个也是不小的一笔时间开销吧？

当然，这个用链表的想法应该是这个帖子里最有创意的想法了吧，版主到底是版主。

HopeCao的想法也很好，用字符串代替原有的数据类型以拓展可以求解的空间，可以计算到700多，想法非常好。

小飞爱使申华

我模仿flw老大的C++版，做了一个java版本，给大家找找乐，有兴趣请看：  
   http://www.chinaunix.net/forum/viewtopic.php?p=882955#882955     

还有，flw老大，你的code还有小问题，释放内存那段，ptr没有声明过吧。应改为Cow *ptr = cow::head;

海滨

一头牛，引来兄弟无数呀
哈哈哈哈哈哈哈哈：）

小飞爱使申华

原帖由 "海滨" 发表：
一头牛，引来兄弟无数呀
哈哈哈哈哈哈哈哈：）

   

不不，关键是“母”牛。