Re: [問題] 請問有關多項式相加的問題
看板java作者AmosYang (LetMeGoogleThatForYou)時間16年前 (2009/11/07 21:43)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
※ 引述《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)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：