母牛數(shù)量算法

flw

已經(jīng)加上了釋放內(nèi)存的那一段了。

kj501

我用vector重新實(shí)現(xiàn)flw的算法，正好考驗(yàn)一下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++;                // 每年長(zhǎng)了一歲。
    
16.       if ( age >;= 4 ) {     // 第四個(gè)年頭起生小牛。
    
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.    //輸出結(jié)果
    
30.    cout<<ver.size()<<endl;
    
31.    //釋放內(nèi)存
    
32.    for(int i=0; i<ver.size(); i++)
    
33.       delete ver[i];
    
34. }
    

復(fù)制代碼

算到y(tǒng)ears=40時(shí)，出來(lái)的結(jié)果是1822473。計(jì)算years=50時(shí)就狂讀硬盤(pán)了，所有我沒(méi)有繼續(xù)。由此看來(lái)stl的容器能夠支持的元素個(gè)數(shù)是很大的，但不知道最大是多少，什么時(shí)候能溢出？

HopeCao

我也做了一個(gè)：

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. //  字符串?dāng)?shù)據(jù)相加.
    
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. }
     

復(fù)制代碼

測(cè)試了幾個(gè)跟flw兄的結(jié)果一致，不知道數(shù)字大了會(huì)不會(huì)錯(cuò)，請(qǐng)各位測(cè)試一下！
要是沒(méi)有問(wèn)題的話下次來(lái)討論算法�。�！

kj501

強(qiáng)，不過(guò)years只能算到767，768以上出來(lái)的數(shù)字全都一樣。

sdupoplar

有沒(méi)有注意，程序最后占了多少內(nèi)存呢？

aero

這個(gè)版好久沒(méi)這么熱鬧了。
一天沒(méi)來(lái)，這么多code了，偶分析不過(guò)來(lái)了，太面了，落下了，來(lái)叫聲好。

aero

看了后來(lái)的，又評(píng)論了一點(diǎn)，臭屁一下。

flw的算法的確是非常新穎，想法也非常的有創(chuàng)意。

但是，偶還是覺(jué)得不如偶的非遞歸算法好（嘻嘻）。

flw的算法中為每頭牛創(chuàng)建了一個(gè)節(jié)點(diǎn)，異常龐大的內(nèi)存消耗自不必說(shuō)，偶覺(jué)得創(chuàng)建節(jié)點(diǎn)的開(kāi)銷(xiāo)也是蠻大的，因?yàn)楫吘共皇窃�有的�?shù)據(jù)類(lèi)型。在者，在每一年的循環(huán)中都要?dú)v遍一次鏈表，這個(gè)也是不小的一筆時(shí)間開(kāi)銷(xiāo)吧？

當(dāng)然，這個(gè)用鏈表的想法應(yīng)該是這個(gè)帖子里最有創(chuàng)意的想法了吧，版主到底是版主。

HopeCao的想法也很好，用字符串代替原有的數(shù)據(jù)類(lèi)型以拓展可以求解的空間，可以計(jì)算到700多，想法非常好。

小飛愛(ài)使申華

我模仿flw老大的C++版，做了一個(gè)java版本，給大家找找樂(lè)，有興趣請(qǐng)看：  
   http://www.chinaunix.net/forum/viewtopic.php?p=882955#882955     

還有，flw老大，你的code還有小問(wèn)題，釋放內(nèi)存那段，ptr沒(méi)有聲明過(guò)吧。應(yīng)改為Cow *ptr = cow::head;

海濱

一頭牛，引來(lái)兄弟無(wú)數(shù)呀
哈哈哈哈哈哈哈哈：）

小飛愛(ài)使申華

原帖由 "海濱" 發(fā)表：
一頭牛，引來(lái)兄弟無(wú)數(shù)呀
哈哈哈哈哈哈哈哈：）

   

不不，關(guān)鍵是“母”牛。