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 | |
|
