我有floor(sqrt(floor(x)))
。这是真的:
- 内部
floor
是多余的。 - 外部
floor
是多余的。
显然外层不是多余的,因为例如sqrt(2)
不是整数,因此floor(sqrt(2))≠sqrt(2)
.
sqrt(floor(x))≠sqrt(x)
对于非整数也很容易看出这一点x
。因为sqrt
是单调函数。
我们需要找出是否floor(sqrt(floor(x)))==floor(sqrt(x))
适用于所有有理数(或实数)。
让我们证明如果sqrt(n)<m
那么sqrt(n+1)<m+1
,对于整数m,n
。很容易看出
n<m^2 ⇒ n+1 < m^2+1 < m^2+2m+1 = (m+1)^2
因此,由于sqrt
是 montone,我们有
sqrt(n) < m -> sqrt(n+1) < m+1 -> sqrt(n+eps)<m+1 for 0<=eps<1
因此floor(sqrt(n))=floor(sqrt(n+eps))
对于 all0<eps<1
和 integer n
。否则假设floor(sqrt(n))=m
and floor(sqrt(n+eps))=m+1
,并且你有一个案例 wheresqrt(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) )[ 因此,如果您只对结果的整数部分感兴趣,则无需在取其平方根之前对数字求底。
直觉上我相信内在的是多余的,但我无法证明这一点。
除非你能提供一个证明我错的 x 值,否则你不能投票给我。8-)
编辑:请参阅 v3 对此答案的评论以获取证据 - 谢谢,v3!
内层是多余的
内层是多余的。反证法:
假设内层不是多余的。这将意味着:
floor(sqrt(x)) != floor(sqrt(x+d))
对于某些 x 和 d,其中 floor(x) = floor(x+d)。然后我们要考虑三个数字:a = sqrt(x),b = floor(sqrt(x+d)),c = sqrt(x+d)。b 是一个整数,a < b < c。这意味着 a^2 < b^2 < c^2,或 x < b^2 < x+d。但是如果 b 是一个整数,那么 b^2 是一个整数。因此 floor(x) < b^2,b^2 <= floor(x+d),然后 floor(x) < floor(x+d)。但我们首先假设 floor(x) = floor(x+d)。我们遇到了矛盾,所以我们的假设是错误的,内层是多余的。
如果 x 是整数,则内层是多余的。
如果 x 不是整数,则两者都不是多余的。
外层不是多余的。反例:x = 2。
地板(sqrt(地板(2))) = 地板(sqrt(2)) = 地板(1.41...)
如果没有外层,结果将是 1.41...
如果内层不是多余的,那么我们会期望 floor(sqrt(n)) != floor(sqrt(m)),其中 m = floor(n)
请注意,n - 1 < m <= n。m 总是小于或等于 n
floor(sqrt(n)) != floor(sqrt(m)) 要求 sqrt(n) 和 sqrt(m) 的值至少相差 1.0
但是,没有任何值 n 的 sqrt(n) 与 sqrt(n + 1) 相差至少 1.0,因为对于 0 和 1 之间的所有值,该值的 sqrt 根据定义小于 1。
因此,对于所有值 n,floor(sqrt(n)) == floor(sqrt(n + 1))。这与最初的假设相矛盾。
因此内层是多余的。
如果n^2 <= x < (n+1)^2
wheren
是一个整数,那么
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))
,这意味着内层是多余的。