ID #5709

A/B向上取整的方法

1.问题

A,B都是整数并且 A>1, B>1

求 ┌ A/B ┐ 即 A/B 的上取整。

当 A/B 整除,往上取整返回值 为 A/B。

当 不整除,返回值是 int(A/B) + 1

这个算法的一个应用:如果你有一个动态增长的缓冲区,增长的步长是 B,

某一次缓冲区申请的大小是 A,这个时候,就可以用这个算法,计算出缓冲区的一个合

适大小了,正好可以容纳A,并且不会过于得多,多余部分不会比B多。

2.方法

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

3.HUNTON 的证明

上取整用UP表示

由于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时,

UP(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)


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

关键数据结构之数据流向

RTree源代码——C语言实现(上)

IBM的MARS加密算法实现(上)

什么是算法

数据结构教程 第九课 循环链表与双向链表