※ 引述《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)