※ 引述《Kovainen (雷克南)》之銘言： : 以係數非零的項次之方式儲存多項式 : 並進行多項式相加 : 例如程式輸入3,100,1,10,3,0,1(M(x)=X的100次方+3X的10次方+1) : 以及4,5,1,3,8,2,1,0,2(K(x)=X的5次方+8X的3次方+X的平方+2) : 多項式相加後結果為 : F(X)=X的100次方+3X的10次方+X的5次方+8X的3次方+X的2次方+3 : (6,100,1,10,3,5,1,3,8,2,1,0,3) 很有趣的題目，乍看之下以為開一個 array 讓 n 表示最高的項次; m 表示一共有多少個多項式 一路填下去 O(n*m) 就可以收工了 (記憶體使用量為 O(n)) 但事實上來一個項次為 2147483648 的，用普通 array 的大概都會爆掉 因為就我記得的，不管是 C/C++/C#/Java 的 array 大小上限通常都是 2^31-1 內建的 ArrayList 一類的東西也通常都有類似的限制 且一個大小為 2147483648 的 32bit int array 至少要 8GB XD 2147483648 * 32 bit = 2^31 * 4 byte = 2 * 2^30 * 4 byte = 8 byte * 2^30 = 8 GB 所以比較穩當的作法還是費一點 CPU time, 使用 O(m * n) (用 hash / dictionary) 或 O(m * (n log n)) (用 binary tree + binary search) 或 O(m * n^2) (用 linked-list + linear search) 的作法 讓 k 表示 "非零項次的數量" 則記憶體使用量為 O(k) 還是有可能會爆，但應該會比第一種 O(n*m) 的解法耐命些 : 請問題目的意思是什麼? 題目已經說得很清楚了… : 有誰可以附上寫好的程式碼嗎? 很有趣的問題，乍看之下是 undecidable http://en.wikipedia.org/wiki/Undecidable 但事實上是 O(n) ; 讓 n 為 "所以能滿足以下條件的 x 的數量" ForAll x that CanCommunicate(x) 我 Prolog 已經通通還給老師了， 有請強者用 Prolog 來解 "有誰可以附上寫好的程式碼嗎?" 這題。 XD --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 65.87.177.87 ※ 編輯: AmosYang 來自: 65.87.177.87 (11/07 21:45) ※ 編輯: AmosYang 來自: 65.87.177.87 (11/07 21:51)