Ceil函数实现

Veröffentlicht am   |  

Introductio

下取整函数，或高斯函数，记作$\lfloor x \rfloor$，表示不超过$x$的最大整数。

上取整函数，记作$\lceil x \rceil$,表示不小于$x$的整数中最小的那个。

易得如下性质$$-\lfloor -x \rfloor = \lceil x \rceil$$

Python approach

python2中默认的整数除法是向下取整，根据以上性质，可以直接转化成代码：

1
2
def ceil(op1, op2):
    return -(-op1/op2)

C/C++ approach

C++中的整数除法默认是截断小数部分，比如1.5截断后变为1,-1.5截断后变为-1。可见，在正整数时是向下取整， 在负整数时是向上取整。所以简单的实现可以将其变为负数，然后再根据原来的符号输出。但是其实有更简单的做法：

1
2
3
4
int ceil(int op1, int op2)
{
    return (op1 + op2 - 1)/op2;
}

propositon: $\lceil a/b \rceil = (a+b-1)//b$ 其中//代表截断除，即C++自带的除法。
Proof:

我们可以设 $a=k*b+r$ 其中 $k=\lfloor a/b \rfloor , 0 < r < b$ ,可得

$$(a+b-1)//b = [(k+1)*b+r-1]//b=k+1+(r-1)//b = k+1 = \lfloor a/b \rfloor+1=\lceil a/b \rceil$$

QED