聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

整值函数的研究和在程序中的应用

2014-09-04 09:30 浏览: 1513182 次 我要评论(0 条) 字号:

最近写程序的时候、碰到一个问题。其实就是将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位一组
然后算出一个可以分成几组。可以直接利用这个原理,而不用再其进行函数的
调用,比如你在阅读人家的代码时候、有时候就会这样写。

下次你碰到这种代码就会知道什么意思,和为什么能表示成这样了。



swp 2014-09-03 15:06 发表评论


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复