14

我有floor(sqrt(floor(x)))。这是真的:

  1. 内部floor是多余的。
  2. 外部floor是多余的。
4

9 回答 9

37

显然外层不是多余的,因为例如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))=mand 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)))
于 2009-05-17T20:39:32.260 回答
18

内层是多余的,外层当然不是。

外面的不是多余的,因为如果 x 是平方数,数字 x 的平方根只会产生整数。

内部是多余的,因为区间 [x,x+1[ (其中 x 是整数)中的任何数字的平方根始终位于区间 [floor(sqrt(x)),ceil(sqrt(x) )[ 因此,如果您只对结果的整数部分感兴趣,则无需在取其平方根之前对数字求底。

于 2009-05-17T20:40:29.887 回答
5

直觉上我相信内在的是多余的,但我无法证明这一点。

除非你能提供一个证明我错的 x 值,否则你不能投票给我。8-)

编辑:请参阅 v3 对此答案的评论以获取证据 - 谢谢,v3!

于 2009-05-17T20:14:00.683 回答
4

内层是多余的

于 2009-05-17T20:09:29.057 回答
4

内层是多余的。反证法:

假设内层不是多余的。这将意味着:

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)。我们遇到了矛盾,所以我们的假设是错误的,内层是多余的。

于 2009-05-17T20:40:14.847 回答
3

如果 x 是整数,则内层是多余的。

如果 x 不是整数,则两者都不是多余的。

于 2009-05-17T20:12:18.067 回答
3

外层不是多余的。反例:x = 2。

地板(sqrt(地板(2))) = 地板(sqrt(2)) = 地板(1.41...)

如果没有外层,结果将是 1.41...

于 2009-05-17T20:19:26.427 回答
2

如果内层不是多余的,那么我们会期望 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))。这与最初的假设相矛盾。

因此内层是多余的。

于 2009-05-17T20:53:54.160 回答
0

如果n^2 <= x < (n+1)^2wheren是一个整数,那么

  1. n <= sqrt(x) < n+1, 所以floor(sqrt(x)) = n;
  2. 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)),这意味着内层是多余的。

于 2019-04-04T15:28:01.287 回答