i****m 发帖数: 15 | 1 不知道以前被讨论过没有?
好像是
Give four integer variables, a,b,c,d, all are in [1,1000]
and
a^3 + b^3 = c^3 + d^3,
写一个program找出所有的{a,b,c,d}满足上面的方程, what's the complexity, etc.
Obviously testing testing 3 variables and find out the last one, having O(n
^3) is a not the best way to do it. | I***e 发帖数: 1136 | 2 You need to compute all combination of i^3 + j^3 and keep the results sorted
in the process. Once it's done you simply traverse the list and find all
duplicate sums. The complexity is O(n^2). Memory usage is O(n^2) too. Could
there be O(n log(n)) solutions?
-iCare-
etc.
(n
【在 i****m 的大作中提到】 : 不知道以前被讨论过没有? : 好像是 : Give four integer variables, a,b,c,d, all are in [1,1000] : and : a^3 + b^3 = c^3 + d^3, : 写一个program找出所有的{a,b,c,d}满足上面的方程, what's the complexity, etc. : Obviously testing testing 3 variables and find out the last one, having O(n : ^3) is a not the best way to do it.
| n******t 发帖数: 4406 | 3 Just first calculate all the cubics of the numbers in [1,1000]
then solve x + y = z + w among those numbers.
etc.
(n
【在 i****m 的大作中提到】 : 不知道以前被讨论过没有? : 好像是 : Give four integer variables, a,b,c,d, all are in [1,1000] : and : a^3 + b^3 = c^3 + d^3, : 写一个program找出所有的{a,b,c,d}满足上面的方程, what's the complexity, etc. : Obviously testing testing 3 variables and find out the last one, having O(n : ^3) is a not the best way to do it.
| j****e 发帖数: 140 | |
|