向上取整算法

今天在Coursera上看到一节关于向上取整的算法，自身觉得挺新奇的，自己也没有想过类似的问题。因为在计算机中整数除法'/'表示的是向下取整的策略，但是日常生活中经常也需要向上取整，比如话费的计算、内存空间的分配问题，都是这样。接下来让我们看看向上取整的小技巧。

（A+B-1）/B

问题描述

有两个整数A和B，A>1,B>1，UP（A/B）表示向上取整。
求证UP（A/B）=（A+B-1）/B。

证明

由于A>1、B>1，且A、B都是整数，所以可以设A=NB+M

其中N为非负整数，M为0到B-1的数，则

A/B=N+M/B

(A+B-1)/B=N+1+(M-1)/B;

当M为0时，

int(A/B)=N，

int((A+B-1)/B)=N+int(1-1/B)=N

当M为1到B-1的数时，0<=M-1<=B-2

UP(A/B)=N+1，

int((A+B-1)/B)=N+1+int((M-1)/B)=N+1

所以对A>1、B>1的整数A、B都有：

UP(A/B)=int((A+B-1)/B)