说明:
程序除了可以枚举或猜测外,简单的数学证明更有说服力,下面是关于C语言的得到整数除法结果向上取整的数学证明:
int x, n;
int c=(x+n-1)/ n ; (0)
c为x除以n的向上取整结果。
已知:
对于常量n,任意正整数x可以表示为:
x=an+c;(其中,a为整数,且0⩽a) (1)
为了满足向上取整,需要限制c为:
1<c<n; (2)
类似,向下取整,则需要限制c为:
0<c<n−1;(对于向下取整,C语言正整数除法默认为就是这样子的)
证明:
为了使x/n向上取整,需要满足:
(a+1)n<x+σ<(a+2)n;
根据条件(1)推出:
(a+1)n<an+c+σ<(a+2)n;
简化,
n-c<σ<2n-c; (3)
根据条件(2)推出:
0<n-c<n-1;n<2n-c<2n-1 (4)
由(3)(4)推出:
n-1<σ<n
结论:
σ取整数的话就只可以为n-1,故可以得出结论(0)成立。
类推可以得到向下取整的σ=0;