w******g
发帖数: 67 | 1 Q:Given a positive integer, return the integer part of its square root.
Requirements: cannot use any math functions; can only use integer
variables, no double variables even for intermediate variables; as
efficient as possible.
我想的是：从i=1 到 n/2 挨个试，如果i*i >n 就停止。
这道题有什么trick或者要注意的吗？ 多谢。 |
z****n
发帖数: 1379 | 2 用二分法
其实二分对于double sqrt(double)也是适用的，不知道面试题为什么都问int sqr
t(int)，可能int你说的那种方法也行，而double你说的方法就不行了
【在 w******g 的大作中提到】
: Q:Given a positive integer, return the integer part of its square root.
: Requirements: cannot use any math functions; can only use integer
: variables, no double variables even for intermediate variables; as
: efficient as possible.
: 我想的是：从i=1 到 n/2 挨个试，如果i*i >n 就停止。
: 这道题有什么trick或者要注意的吗？ 多谢。
|
h**6
发帖数: 4160 | 3 double sqrt(double)可以用牛顿法，而int则不行，只能二分，可见面试想考的是编程
而不是数学。 |
B*****g
发帖数: 193 | 4 不判断<1/2可以吗？ like the following, the i must be < 1/2 of the value.
int intSqrt(int value)
{
int i = 0;
while ( true ){
if( i * i == value )
return i;
if( i * i > value )
return (i-1);
i++;
}
return 0;
} |
a****d
发帖数: 114 | 5 笔算开方，九章算术里面有。
【在 w******g 的大作中提到】
: Q:Given a positive integer, return the integer part of its square root.
: Requirements: cannot use any math functions; can only use integer
: variables, no double variables even for intermediate variables; as
: efficient as possible.
: 我想的是：从i=1 到 n/2 挨个试，如果i*i >n 就停止。
: 这道题有什么trick或者要注意的吗？ 多谢。
|
R*******e
发帖数: 36 | 6 这样看看：
unsigned int integerSquarRoot(unsigned int number)
{
unsigned int i= number/2;
while (i * i > number)
i /= 2;
while (i * i < number)
i += 1;
if (i * i == number)
return i;
else
return i-1;
}
【在 w******g 的大作中提到】
: Q:Given a positive integer, return the integer part of its square root.
: Requirements: cannot use any math functions; can only use integer
: variables, no double variables even for intermediate variables; as
: efficient as possible.
: 我想的是：从i=1 到 n/2 挨个试，如果i*i >n 就停止。
: 这道题有什么trick或者要注意的吗？ 多谢。
|
w******g
发帖数: 67 | |
h**k
发帖数: 3368 | 8 既然用二分法，就应该一直用到底
precondition : left<= i < right. i is the answer.
left = 0;
right = number/2+1;
while( left + 1 < right )
{
middle = (left + right) / 2;
if( middle*middle == number )
return middle;
if( middle*middle < number )
left = middle;
else
right = middle;
}
return left;
【在 R*******e 的大作中提到】
: 这样看看：
: unsigned int integerSquarRoot(unsigned int number)
: {
: unsigned int i= number/2;
:
: while (i * i > number)
: i /= 2;
: while (i * i < number)
: i += 1;
: if (i * i == number)
|
