最近写程序的时候、碰到一个问题。其实就是将celing函数用C++默认的除法运算(向下取整)表示出来。所以我打算总结下整值函数。
Firth.首先我们要熟悉顶函数和底函数,最好的方式就是了解他们的图形。
由于数学符号在这里不好写出来,我们用floor来表示底,celing表示顶。
图形其实就是以f(x) = x 为分界线,这边就不画出来了。向下取整组成的坐标点就是(x, floor(x))
这些刚好就是在f(x) = x下方的,而向上取整则是在上方的。
Tips:
所以从图像中我们可以发现一下两个等式(位移、奇函数)
1.x – 1 < floor(x) <= x <= celing(x) < x + 1 (可以通过位移图像来得出该不等式)
2.floor(-x) = – celing(x) 或者 celing(-x) = – floor(x) (这个其实可以简单记为奇函数)
Second.两条法则(你要细分成4条我也不反对)
1.floor(x) = n 等价于 n <= x < n + 1 等价于 x – 1 < n <= x
2.celing(x) = n 等价于 n - 1 < x <= n 等价于 x <= n < x + 1
Tips:
1.其中n是整数,x是实数
2.floor(x + n) = floor(x) + n (因为有上面法则有 floor(x) + n <= x + n < floor(x) + n + 1).
3.但floor(nx) != n*floor(x)
Third.实数和整数之间的关系,其实都等价于一个顶或底函数于整数的关系。
1.x < n 等价于 floor(x) < n
2.n < x 等价于 n < celing(x)
3.x <= n 等价于 celing(x) <= n
4.n <= x 等价于 n <= floor(x)
Tips
1.celing相当于扩大、floor相当于缩小
2.取到n,则看能取到最大或者最小,最大取celing、最小floor。
不达n,则缩小或扩大x等式不变。
3.floor(x + y) 等于 floor(x) + floor(y) 或者是 floor(x) + floor(y) + 1
x = floor(x) + {x}, y = floor(y) + {y},then
x + y = floor(x) + floor(y) + {x} + {y},then
floor(x + y) = floor(x) + floor(y) + floor( {x} + {y})
and because 0<={x} < 1 and so do {y},so
0<={x} + {y} <2,so floor({x} + {y}) = 0 or 1
应用:
在程序中应用之前,我先说下一个等式的证明
celing(n / m) = floor( (n + m – 1) / m)
这里n 、m都是整数,而且m是正整数。
证明:
因为celing(n /m) – floor(n /m) = celing(n / m – floor(n / m))
= celing(1/m * ( n – m*floor(n / m))) = celing((n mod m) / m)-------------(1)利用了上面两条法则中Tips的第二点
同理可以得出floor((n + m –1) /m) = floor((n mod m + m – 1) / m)---------- (2)
由(1)可以得到celing((n mod m )/ m) = 1
由(2)可以得到floor((n mod m + m – 1) / m) = 1 (因为n mod m + m – 1 < 2 *m –1)
所以可以一步步向上反推得到上面的公式。(其实这是一种分而自治的证明思想)
具体在程序中的应用例如:
当你要在C++中写如下代码时候,而且n 、m都是整数。
则celing(n * 1.0 / m) = floor( (n – 1) / m) + 1
由于C++中除运算就是向下取整,所以
celing(n * 1.0 / m) = (n - 1) / m + 1
那么什么地方用得到,比如你在做大数运算时侯,要进行,分组,要8位一组
然后算出一个可以分成几组。可以直接利用这个原理,而不用再其进行函数的
调用,比如你在阅读人家的代码时候、有时候就会这样写。
下次你碰到这种代码就会知道什么意思,和为什么能表示成这样了。