- 論壇徽章:
- 0
|
其實(shí)，這個(gè)題目還是說(shuō)明了一個(gè)基本功：算法分析與設(shè)計(jì)。下面寫(xiě)一系列BTW。
BTW1：只要看到代碼里數(shù)據(jù)保存使用的是int或者long，就說(shuō)明寫(xiě)的代碼就是不符合要求的，盡管某些算法是對(duì)的。
BTW2：其實(shí)第一頁(yè)7樓的灰色軌跡寫(xiě)的代碼就是對(duì)的，算法設(shè)計(jì)的很好而且而且遞歸調(diào)用的非常好，算法就像一個(gè)do...while循環(huán)，很容易改寫(xiě)為do...while循環(huán)，復(fù)雜度是O(n)的算法，存儲(chǔ)空間就是棧上的空間，只不過(guò)函數(shù)寫(xiě)的倉(cāng)促了點(diǎn)，代碼組織上有些混亂，返回值用的是int，當(dāng)然得不出正確的結(jié)論，其實(shí)應(yīng)該對(duì)自己有信心一點(diǎn)，跟蹤每一步all_cow的結(jié)果，很容易發(fā)現(xiàn)數(shù)據(jù)存儲(chǔ)空間的溢出。很多人都悶頭自己寫(xiě)自己的代碼，也不看看前面別人寫(xiě)好的代碼有什么長(zhǎng)處。
BTW3：看到兩個(gè)for循環(huán)疊加的那種，甭看，就不是最佳算法，雖然會(huì)得到正確結(jié)果，比如: flw寫(xiě)的那個(gè)鏈表，還有其他類(lèi)似的用STL的那種，類(lèi)似這樣的代碼，下面是flw的代碼片段：
for( int i=0; i<years; i++ )
for( cow *ptr = cow::head; ptr != NULL; ptr = ptr->next )
ptr->grow(); |
for()循環(huán)里面再套一個(gè)for()，即便有空間展開(kāi)算法復(fù)雜度，也沒(méi)有任何意義，復(fù)雜度是O(n^2)的算法，可以說(shuō)把O(n^3)的算法復(fù)雜度減少了一點(diǎn)，而且分配了很多動(dòng)態(tài)空間。盡管“按照”題目寫(xiě)的算法，結(jié)果一定是正確的。但是絲毫沒(méi)有真正的數(shù)學(xué)分析和算法分析。就實(shí)際應(yīng)用來(lái)說(shuō)，確是最下乘的用法。
BTW4：整個(gè)帖子來(lái)說(shuō)，唯一能解這個(gè)題目符合題目的，而且代碼能處理正確的，能算到100年以上的，只有HopeCao寫(xiě)的代碼。HopeCao的代碼很好的解決了這個(gè)問(wèn)題，根本不存在長(zhǎng)度的問(wèn)題，只要buffer足夠大，得到的結(jié)果永遠(yuǎn)是對(duì)的。他的buffer是1024，是非常非常非常非常非常的大…… 是效率上，大量的strcpy是在不敢恭維。
BTW5：win_hate的算法分析和結(jié)果都是對(duì)的。用了maple寫(xiě)…… 如果結(jié)果和他的不相符，就一定是錯(cuò)的�？墒沁@里可是C/C++版。太沒(méi)面子了。
BTW6：我所看到的至少有8份以上的代碼是錯(cuò)的，根本就沒(méi)有理解題意。也沒(méi)有驗(yàn)證數(shù)據(jù)的正確性就貼上來(lái)了。如果你是程序員的話(huà)，要對(duì)自己的代碼負(fù)責(zé)，即便有一行代碼，有一天也需要維護(hù)。
BTW7：用f(n) = f(n-1) + f(n-3)，直接寫(xiě)代碼的，算法分析方面前進(jìn)了一大步，恭喜，解題來(lái)說(shuō)，是對(duì)的，但是你將很難的到答案，算法設(shè)計(jì)上卻是非常得差勁。為什么這么慢？調(diào)用了兩個(gè)f(n)這個(gè)函數(shù)，沒(méi)有保存結(jié)果，而是一步步地計(jì)算，計(jì)算步驟數(shù)量，就是(n-1)階乘+(n-3)的階乘這么多。下面是計(jì)算10年的函數(shù)調(diào)用步驟結(jié)果：
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年將增長(zhǎng)到恐怖的377步，極其恐怖。算法，既要設(shè)計(jì)又要分析……
BTW8：果想處理正確，使用正確的數(shù)據(jù)類(lèi)型，還有浮點(diǎn)類(lèi)型了，不過(guò)浮點(diǎn)類(lèi)型就沒(méi)有任何意義了。windows下有__int64類(lèi)型，不過(guò)還有一種類(lèi)型，就是long long，沒(méi)錯(cuò)是兩個(gè)，c99標(biāo)準(zhǔn)中定義的類(lèi)型，當(dāng)然，比long還long。我這么定義的typedef unsigned long long qty_type; windows下也可以typedef unsigned __int64 qty_type;或許，有些人使用的是64位的操作系統(tǒng)呢？
BTW9：就算法分析還有遞歸的使用方面，推薦《Structure and Interpretation of Computer Programs》（SICP）這本書(shū)。北大裘宗燕老師翻譯成了中文版。用lisp描述的，只有遞歸，沒(méi)有迭代……
BTW10：我是第一次來(lái)這個(gè)論壇，就是找點(diǎn)資料用用，沒(méi)想到看到這個(gè)熱帖，忍不住多說(shuō)幾句。
夜深了，該睡覺(jué)了，明天還要分析數(shù)據(jù)……
最后給出結(jié)果，那個(gè)樓主，貌似2003年就不來(lái)了……
又簡(jiǎn)單又好用的答案，代碼也不用重新寫(xiě)了，簡(jiǎn)單整理了灰色軌跡的代碼就足夠用了，而且很容易就可以修改為迭代類(lèi)型的代碼，
代碼在WinXP SP2 VC2005 SP1和ubuntu7.04 g++4.1下測(cè)試通過(guò)。代碼如下：
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 }
正確的結(jié)果100年內(nèi)：
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 編輯 ] |
|
免費(fèi)注冊(cè)
樓主: loveguohuasai
發(fā)表于 2006-09-07 18:32
