证明:对于两个正整数a和b,为什么a/b向上取整的结果等于(a+b-1)/b向下取整的结果
要证明的问题是:
⌈ a b ⌉ = = ⌊ a + b − 1 b ⌋ \\lceil \\frac{a}{b} \\rceil==\\lfloor \\frac{a+b-1}{b} \\rfloor ⌈ba⌉==⌊ba+b−1⌋
证明过程如下:
记 a = k b + m i f m = = 0 : t h e n ⌈ a b ⌉ = k , ⌊ a + b − 1 b ⌋ = ⌊ k b + b − 1 b ⌋ = k i f m ! = 0 : t h e n 1 ≤ m ≤ b − 1 , ⌈ a b ⌉ = k + 1 ⌊ a + b − 1 b ⌋ ⟺ ⌊ k b + m + b − 1 b ⌋ ⟺ k + ⌊ m + b − 1 b ⌋ 由于 1 ≤ m ≤ b − 1 ,因此 b ≤ m + b − 1 ≤ 2 b − 2 ,因此 ⌊ m + b − 1 b ⌋ = 1 所以 ⌊ a + b − 1 b ⌋ = k + 1 = ⌈ a b ⌉ 记a=kb+m \\\\ \\\\ if \\quad m==0: \\quad then \\quad\\lceil \\frac{a}{b}\\rceil=k , \\lfloor \\frac{a+b-1}{b} \\rfloor=\\lfloor \\frac{kb+b-1}{b} \\rfloor=k \\\\ \\\\ if \\quad m!=0: \\quad then \\quad 1\\leq m \\leq b-1, \\quad\\lceil \\frac{a}{b}\\rceil=k+1 \\\\ \\lfloor \\frac{a+b-1}{b} \\rfloor \\\\ \\iff \\lfloor \\frac{kb+m+b-1}{b} \\rfloor \\\\ \\iff k+\\lfloor \\frac{m+b-1}{b}\\rfloor \\\\由于1\\leq m \\leq b-1,因此b\\leq m+b-1 \\leq 2b-2,因此\\lfloor \\frac{m+b-1}{b}\\rfloor=1 \\\\所以\\lfloor \\frac{a+b-1}{b} \\rfloor=k+1=\\lceil \\frac{a}{b}\\rceil 记a=kb+mifm==0:then⌈ba⌉=k,⌊ba+b−1⌋=⌊bkb+b−1⌋=kifm!=0:then1≤m≤b−1,⌈ba⌉=k+1⌊ba+b−1⌋⟺⌊bkb+m+b−1⌋⟺k+⌊bm+b−1⌋由于1≤m≤b−1,因此b≤m+b−1≤2b−2,因此⌊bm+b−1⌋=1所以⌊ba+b−1⌋=k+1=⌈ba⌉