关于C语言的得到整数除法结果向上取整的数学证明

时间:2021-07-26 01:46:54

说明:

程序除了可以枚举或猜测外,简单的数学证明更有说服力,下面是关于C语言的得到整数除法结果向上取整的数学证明:

int x, n;

int c=(x+n-1)/ n ;                                                                        (0)

cx除以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;