thảo luận [Học Tập] Topic thuật toán

em thấy để tìm ceil(a/b) với a và b là int thì người ta dùng công thức (a + b - 1)/b. Có bác nào giải thích giúp em sao lại có công thức như vậy được không ạ?

Daedalus said:

em thấy để tìm ceil(a/b) với a và b là int thì người ta dùng công thức (a + b - 1)/b. Có bác nào giải thích giúp em sao lại có công thức như vậy được không ạ?

Click to expand...

Cho a = qb + r hay a/b = q dư r. Điều kiện của số dư r là 0 <= r < b. Ta có ceil(a/b) = q+1 nếu r > 0, ceil(a/b) = q nếu r = 0.

a + b - 1 = qb + r + b - 1 = (q+1)b + r - 1
nếu r > 0: b > r-1 >= 0 nên (a+b-1)/b = q+1 dư r-1
nếu r = 0: r-1 = -1 nên a+b-1 = qb + b - 1, (a+b-1)/b = q dư b-1 vì 0 <= b-1 < b
vậy (a+b-1)/b là ceil(a/b)

mà xài như vầy lỡ a+b nó overflow thì bỏ mọe, toy toàn xài a/b + (a%b != 0)