我有floor(sqrt(floor(x)))
。下列哪种说法是正确的:
- 内部的
floor
是多余的。 - 外部的
floor
是多余的。
我有floor(sqrt(floor(x)))
。下列哪种说法是正确的:
floor
是多余的。floor
是多余的。显然,外层floor函数不是多余的,因为例如sqrt(2)
不是整数,因此floor(sqrt(2))≠sqrt(2)
。
对于非整数x
,很容易看出sqrt(floor(x))≠sqrt(x)
。因为sqrt
是单调递增函数。
我们需要找出是否对于所有有理数(或实数)都满足floor(sqrt(floor(x)))==floor(sqrt(x))
。
让我们证明如果对于整数m,n
,sqrt(n)<m
则sqrt(n+1)<m+1
。很容易看出:
n<m^2 ⇒ n+1 < m^2+1 < m^2+2m+1 = (m+1)^2
因此,由于sqrt
是单调的,我们有:
sqrt(n) < m -> sqrt(n+1) < m+1 -> sqrt(n+eps)<m+1 for 0<=eps<1
对于所有的n
为整数,以及所有的0<eps<1
,都有floor(sqrt(n))=floor(sqrt(n+eps))
。假设否定这个结论,即存在floor(sqrt(n))=m
和floor(sqrt(n+eps))=m+1
的情况,则会出现sqrt(n)<m+1
但sqrt(n+eps)>=m+1
的矛盾。
因此,如果需要外层的floor
,那么内层的floor
就是多余的。
换句话说,总是成立:
floor(sqrt(n)) == floor(sqrt(floor(n)))
内部的ceil
怎么办?
很容易看出floor(sqrt(n)) ≠ floor(sqrt(ceil(n)))
。例如:
floor(sqrt(0.001))=0, while floor(sqrt(1))=1
然而,您可以以类似的方式证明
ceil(sqrt(n)) == ceil(sqrt(ceil(n)))
内部的是多余的,而外部的当然不是。
外部的不是多余的,因为一个数 x 的平方根只有在 x 是平方数时才会得到整数结果。
内部的是多余的,因为在区间 [x,x+1[(其中 x 是整数)中的任何数字的平方根总在区间 [floor(sqrt(x)),ceil(sqrt(x))[ 内,因此如果你只对结果的整数部分感兴趣,则无需在取平方根之前对数字进行向下取整。
内部地面是多余的。反证法:
假设内部地面不是多余的。这意味着:
floor(sqrt(x)) != floor(sqrt(x+d))
外层 floor 不是多余的。反例:x = 2。
floor(sqrt(floor(2))) = floor(sqrt(2)) = floor(1.41...)
如果没有外层 floor,结果将为 1.41...
如果 n^2 <= x < (n+1)^2
,其中 n
是整数,则
n <= sqrt(x) < n+1
,因此 floor(sqrt(x)) = n
;n^2 <= floor(x) < (n+1)^2
,因此 n <= sqrt(floor(x)) < n+1
,因此 floor(sqrt(floor(x))) = n
。因此,floor(sqrt(floor(x))) = floor(sqrt(x))
,这意味着内部的 floor 是多余的。