Заокруживање количника целобројним дељењем
Ако су \(n\) и \(k\) природни бројеви, тада се вредности \(\lfloor {\frac{n}{k}} \rfloor\) и \(\lceil {\frac{n}{k}} \rceil\) могу израчунати и само помоћу операција над целим бројевима. Тиме избегавамо употребу реалних бројева и све опасности до којих може доћи услед немогућности потпуно прецизног записа реалних бројева.
Доказаћемо да је број \(\lfloor{\frac{n}{k}}\rfloor\) једнак целобројном количнику бројева \(n\) и \(k\) који ћемо означавати са \(n\,\mathrm{div}\,k\). Рачунањем целобројног количника избегавамо употребу реалног дељења и функција за рад са реалним бројевима. Нека је \(n = q\cdot k+r\), тако да је \(0 \leq r < k\). Тада је \(q\cdot k + 0 \leq q\cdot k + r < q\cdot k + k\) тј. \(q\cdot k \leq n < (q+1)\cdot k\), тј. \(q \leq \frac{n}{k} < q + 1\). Зато је \(q = \lfloor{\frac{n}{k}}\rfloor\). Међутим, на основу основне дефиниције целобројног количника, коју смо навели у задатку Разломак у мешовит број, важи да је \(q = n\,\mathrm{div}\,k\).
Програмски језици по правилу дају могућност да се директно, целобројним дељењем, израчуна \(\lfloor{\frac{n}{k}}\rfloor\) (то је, како смо већ доказали, целобројни количник бројева \(n\) и \(k\) тј. број \(n\,\mathrm{div}\,k\)), али не и да се директно израчуна \(\lceil{\frac{n}{k}}\rceil\). Постоји неколико начина да се то уради посредним путем.
Први начин се заснива на томе да је \(\lceil{\frac{n}{k}}\rceil\) једнако \(\frac{n}{k}\) када је \(n\) дељиво са \(k\) (без остатка), а да је једнако \(\lfloor{\frac{n}{k}}\rfloor + 1\) тј. \(n\,\mathrm{div}\,k + 1\) када постоји остатак. На пример, ако је \(n=18\) и \(k=3\), тада је \(\frac{n}{k} = 6\) и то је управо најмањи цео број већи или једнак (а уједно и мањи или једнак) вредности 6, тј. \(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n}{k}}\rfloor = \frac{n}{k} = 6\). Ако је \(n=18\), a \(k=4\), тада је \(\frac{n}{k} = 4.5\), па је \(\lfloor{\frac{n}{k}}\rfloor = 4\), \(\lceil{\frac{n}{k}}\rceil = 5\) и важи да је \(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n}{k}}\rfloor + 1\).
Докажимо претходно тврђење и формално. Ако постоје \(q\) и \(r\) такви да је \(n = q\cdot k + r\), где је \(0 \leq r < k\), тада важи да је \(q = n\,\mathrm{div}\,k\), \(r = n\,\mathrm{mod}\,k\) и \(\frac{n}{k} = \frac{q\cdot k + r}{k} = q + \frac{r}{k}.\) Пошто је \(0 \leq \frac{r}{k} < 1\), важи да је \(q \leq \frac{n}{k} < q + 1\). Зато је и \(\lfloor{\frac{n}{k}}\rfloor = q\), тј. \(\lfloor{\frac{n}{k}}\rfloor\) заправо представља вредност целобројног количника \(n\) и \(k\) тј. вредност \(n \,\mathrm{div}\,k\), што смо и раније доказали. Ако је \(r = 0\), тада важи да је \(\frac{n}{k} = q\) и \(q\) је најмањи број такав да већи или једнак од \(\frac{n}{k}\), тј. \(\lceil{\frac{n}{k}}\rceil = q = n\,\mathrm{div}\,k = \frac{n}{k}\). Ако је \(r > 0\), тада је \(\frac{r}{k} > 0\), pa je \(q < \frac{n}{k}\). Зато је \(q+1\) најмањи број већи или једнак (у овом случају је већи) од \(\frac{n}{k}\), тј. \(\lceil{\frac{n}{k}}\rceil = q + 1 = n\,\mathrm{div}\,k + 1 = \lfloor{\frac{n}{k}}\rfloor + 1\).
Други начин је да се примети да важи да је
\(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n+k-1}{k}}\rfloor = (n+k-1)\,\mathrm{div}\,k\).
Размотримо вредности \(\lceil{\frac{n}{k}}\rceil\) и \(\lfloor{\frac{n}{k}}\rfloor\) за \(k=4\) и разне вредности \(n\).
| \(n\) | … | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | … |
| \(\lfloor{\frac{n}{4}}\rfloor\) | … | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | … |
| \(\lceil{\frac{n}{4}}\rceil\) | … | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | … |
Приметимо да за вредности \(n=9\), \(n=10\), \(n=11\) и \(n=12\) важи да је \(\lceil{\frac{n}{4}}\rceil = 3\). Са друге стране за вредности \(n=12\), \(n=13\), \(n=14\) и \(n=15\) важи да је \(\lfloor{\frac{n}{4}}\rfloor = 3\). Додавањем вредности \(k-1=3\) на полазни број \(n\) тј. на бројеве \(9\), \(10\), \(11\) или \(12\) добијају се редом бројеви \(12\), \(13\), \(14\) и \(15\) и израчунавањем целобројног количника добија се вредност 3, што је и било потребно.
Да бисмо формално доказали да важи \(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n+k-1}{k}}\rfloor\), опет претпоставимо да је \(n = q\cdot k + r\), где је \(0 \leq r < k\). Тада је \(n + k - 1 = q\cdot k + r + k - 1\). Зато је \(\frac{n+k-1}{k} = q + \frac{r+k-1}{k}\). Пошто је \(0 \leq r < k\), важи и да је \(0 \leq \frac{0+k-1}{k} \leq \frac{r+k-1}{k} < \frac{k + k-1}{k} < 2\), па је \(q \leq \frac{n+k-1}{k} < q + 2\). Ако је \(r = 0\), тада је \(\frac{n+k-1}{k} = q + \frac{k-1}{k}\) и пошто је \(\frac{k-1}{k} < 1\), тада је \(q \leq \frac{n+k-1}{k} < q + 1\), па важи \(\lfloor{\frac{n+k-1}{k}}\rfloor = q\), а већ раније смо показали да је у случају \(r=0\) важи да је \(q = \frac{n}{k} = \lceil{\frac{n}{k}}\rceil\). Ако је \(r > 0\) тада је \(\frac{r+k-1}{k} \geq 1\), па је \(\frac{n+k-1}{k} \geq q+1\). Пошто већ знамо да је \(\frac{n+k-1}{k} < q + 2\), важи да је \(\lfloor{\frac{n+k-1}{k}}\rfloor = q+1\) за који смо већ показали да је у случају \(r > 0\) једнак броју \(\lfloor{\frac{n}{k}}\rfloor + 1\) тј. броју \(\lceil{\frac{n}{k}}\rceil\).
Напоменимо да мали проблем у имплементацији ове технике представља могућност да збир \(n+k-1\) прекорачи опсег целобројног типа и ову технику није пожељно примењивати када \(n\) и \(k\) могу да буду релативно велики бројеви (колико велики, зависи од њиховог целобројног типа).
Заокруживање количника целобројним дељењем
Ако су \(n\) и \(k\) природни бројеви, тада се вредности \(\lfloor {\frac{n}{k}} \rfloor\) и \(\lceil {\frac{n}{k}} \rceil\) могу израчунати и само помоћу операција над целим бројевима. Тиме избегавамо употребу реалних бројева и све опасности до којих може доћи услед немогућности потпуно прецизног записа реалних бројева.
Доказаћемо да је број \(\lfloor{\frac{n}{k}}\rfloor\) једнак целобројном количнику бројева \(n\) и \(k\) који ћемо означавати са \(n\,\mathrm{div}\,k\). Рачунањем целобројног количника избегавамо употребу реалног дељења и функција за рад са реалним бројевима. Нека је \(n = q\cdot k+r\), тако да је \(0 \leq r < k\). Тада је \(q\cdot k + 0 \leq q\cdot k + r < q\cdot k + k\) тј. \(q\cdot k \leq n < (q+1)\cdot k\), тј. \(q \leq \frac{n}{k} < q + 1\). Зато је \(q = \lfloor{\frac{n}{k}}\rfloor\). Међутим, на основу основне дефиниције целобројног количника, коју смо навели у задатку Разломак у мешовит број, важи да је \(q = n\,\mathrm{div}\,k\).
Програмски језици по правилу дају могућност да се директно, целобројним дељењем, израчуна \(\lfloor{\frac{n}{k}}\rfloor\) (то је, како смо већ доказали, целобројни количник бројева \(n\) и \(k\) тј. број \(n\,\mathrm{div}\,k\)), али не и да се директно израчуна \(\lceil{\frac{n}{k}}\rceil\). Постоји неколико начина да се то уради посредним путем.
Први начин се заснива на томе да је \(\lceil{\frac{n}{k}}\rceil\) једнако \(\frac{n}{k}\) када је \(n\) дељиво са \(k\) (без остатка), а да је једнако \(\lfloor{\frac{n}{k}}\rfloor + 1\) тј. \(n\,\mathrm{div}\,k + 1\) када постоји остатак. На пример, ако је \(n=18\) и \(k=3\), тада је \(\frac{n}{k} = 6\) и то је управо најмањи цео број већи или једнак (а уједно и мањи или једнак) вредности 6, тј. \(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n}{k}}\rfloor = \frac{n}{k} = 6\). Ако је \(n=18\), a \(k=4\), тада је \(\frac{n}{k} = 4.5\), па је \(\lfloor{\frac{n}{k}}\rfloor = 4\), \(\lceil{\frac{n}{k}}\rceil = 5\) и важи да је \(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n}{k}}\rfloor + 1\).
Докажимо претходно тврђење и формално. Ако постоје \(q\) и \(r\) такви да је \(n = q\cdot k + r\), где је \(0 \leq r < k\), тада важи да је \(q = n\,\mathrm{div}\,k\), \(r = n\,\mathrm{mod}\,k\) и \(\frac{n}{k} = \frac{q\cdot k + r}{k} = q + \frac{r}{k}.\) Пошто је \(0 \leq \frac{r}{k} < 1\), важи да је \(q \leq \frac{n}{k} < q + 1\). Зато је и \(\lfloor{\frac{n}{k}}\rfloor = q\), тј. \(\lfloor{\frac{n}{k}}\rfloor\) заправо представља вредност целобројног количника \(n\) и \(k\) тј. вредност \(n \,\mathrm{div}\,k\), што смо и раније доказали. Ако је \(r = 0\), тада важи да је \(\frac{n}{k} = q\) и \(q\) је најмањи број такав да већи или једнак од \(\frac{n}{k}\), тј. \(\lceil{\frac{n}{k}}\rceil = q = n\,\mathrm{div}\,k = \frac{n}{k}\). Ако је \(r > 0\), тада је \(\frac{r}{k} > 0\), pa je \(q < \frac{n}{k}\). Зато је \(q+1\) најмањи број већи или једнак (у овом случају је већи) од \(\frac{n}{k}\), тј. \(\lceil{\frac{n}{k}}\rceil = q + 1 = n\,\mathrm{div}\,k + 1 = \lfloor{\frac{n}{k}}\rfloor + 1\).
Други начин је да се примети да важи да је
\(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n+k-1}{k}}\rfloor = (n+k-1)\,\mathrm{div}\,k\).
Размотримо вредности \(\lceil{\frac{n}{k}}\rceil\) и \(\lfloor{\frac{n}{k}}\rfloor\) за \(k=4\) и разне вредности \(n\).
| \(n\) | … | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | … |
| \(\lfloor{\frac{n}{4}}\rfloor\) | … | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | … |
| \(\lceil{\frac{n}{4}}\rceil\) | … | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | … |
Приметимо да за вредности \(n=9\), \(n=10\), \(n=11\) и \(n=12\) важи да је \(\lceil{\frac{n}{4}}\rceil = 3\). Са друге стране за вредности \(n=12\), \(n=13\), \(n=14\) и \(n=15\) важи да је \(\lfloor{\frac{n}{4}}\rfloor = 3\). Додавањем вредности \(k-1=3\) на полазни број \(n\) тј. на бројеве \(9\), \(10\), \(11\) или \(12\) добијају се редом бројеви \(12\), \(13\), \(14\) и \(15\) и израчунавањем целобројног количника добија се вредност 3, што је и било потребно.
Да бисмо формално доказали да важи \(\lceil{\frac{n}{k}}\rceil = \lfloor{\frac{n+k-1}{k}}\rfloor\), опет претпоставимо да је \(n = q\cdot k + r\), где је \(0 \leq r < k\). Тада је \(n + k - 1 = q\cdot k + r + k - 1\). Зато је \(\frac{n+k-1}{k} = q + \frac{r+k-1}{k}\). Пошто је \(0 \leq r < k\), важи и да је \(0 \leq \frac{0+k-1}{k} \leq \frac{r+k-1}{k} < \frac{k + k-1}{k} < 2\), па је \(q \leq \frac{n+k-1}{k} < q + 2\). Ако је \(r = 0\), тада је \(\frac{n+k-1}{k} = q + \frac{k-1}{k}\) и пошто је \(\frac{k-1}{k} < 1\), тада је \(q \leq \frac{n+k-1}{k} < q + 1\), па важи \(\lfloor{\frac{n+k-1}{k}}\rfloor = q\), а већ раније смо показали да је у случају \(r=0\) важи да је \(q = \frac{n}{k} = \lceil{\frac{n}{k}}\rceil\). Ако је \(r > 0\) тада је \(\frac{r+k-1}{k} \geq 1\), па је \(\frac{n+k-1}{k} \geq q+1\). Пошто већ знамо да је \(\frac{n+k-1}{k} < q + 2\), важи да је \(\lfloor{\frac{n+k-1}{k}}\rfloor = q+1\) за који смо већ показали да је у случају \(r > 0\) једнак броју \(\lfloor{\frac{n}{k}}\rfloor + 1\) тј. броју \(\lceil{\frac{n}{k}}\rceil\).
Напоменимо да мали проблем у имплементацији ове технике представља могућност да збир \(n+k-1\) прекорачи опсег целобројног типа и ову технику није пожељно примењивати када \(n\) и \(k\) могу да буду релативно велики бројеви (колико велики, зависи од њиховог целобројног типа).