楼层多余(sqrt(floor(x)))？

Question

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

Answer 1

显然,外层不是多余的,因为例如,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我们拥有单一的事实

sqrt(n) < m -> sqrt(n+1) < m+1 -> sqrt(n+eps)<m+1 for 0<=eps<1

因此floor(sqrt(n))=floor(sqrt(n+eps)),所有0<eps<1和整数n.然而,假设floor(sqrt(n))=m和floor(sqrt(n+eps))=m+1,你有一个案例.sqrt(n)<m+1sqrt(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)))

Answer 2

内在的是多余的,外面的当然不是.

外部不是冗余的,因为如果x是平方数,则数字x的平方根仅产生整数.

内部是冗余的,因为区间[x,x + 1 [(其中x是整数)中任何数字的平方根总是位于区间[floor(sqrt(x)),ceil(sqrt(x))内)[因此,如果您只对结果的整数部分感兴趣,则在取平方根之前不需要对数字进行置位.

Answer 3

直觉上我认为内在的是多余的,但我无法证明.

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

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