При каких условиях для целых чисел a и b выражение (a/b) в целочисленном делении можно заменить на округление к ближайшему целому без изменения результата в дальнейших алгебраических преобразованиях, и приведи примеры, где это приводит к ошибке

25 Ноя в 11:37
4 +3
0
Ответы
1
Коротко: всё зависит от остатка при делении. Принятие эквивалентно тогда и только тогда, когда дробная часть ab\frac{a}{b}ba меньше 12\tfrac1221 по модулю (и в случае ровной половины — когда правило округления совпадает с выбранным целочисленным делением).
Более формально (предположим сначала b>0b>0b>0 и целочисленное деление — это округление вниз, a÷b=⌊a/b⌋a\div b=\lfloor a/b\rfloora÷b=a/b). Пусть
q=⌊a/b⌋,r=a−bq,0≤r<b. q=\lfloor a/b\rfloor,\qquad r=a-bq,\qquad 0\le r<b.
q=a/b,r=abq,0r<b.
Тогда округление до ближайшего (правило «round half-up»: round(x)=⌊x+1/2⌋\mathrm{round}(x)=\lfloor x+1/2\rfloorround(x)=x+1/2) даёт то же значение, что и ⌊a/b⌋\lfloor a/b\rfloora/b тогда и только тогда, когда
r<b2. r<\tfrac{b}{2}.
r<2b .
Если r>b2r>\tfrac{b}{2}r>2b , то round(a/b)=q+1\mathrm{round}(a/b)=q+1round(a/b)=q+1. При r=b2r=\tfrac{b}{2}r=2b зависит от правила обработки полуцелых (tie): при «half-up» округление даст q+1q+1q+1, при «round-to-even» — возможно qqq.
Если целочисленное деление в вашей системе делает усечение к нулю (как в C/C++ для отрицательных чисел), то условие записывают через модуль остатка: для записи a=bq+ra=bq+ra=bq+r с ∣r∣<∣b∣|r|<|b|r<b замена на округление безопасна, когда ∣r∣<∣b∣/2|r|<|b|/2r<b∣/2; при ∣r∣=∣b∣/2|r|=|b|/2r=b∣/2 — снова зависит от правила округления и от того, как устроено целочисленное деление.
Примеры, где замена приводит к ошибке:
- a=3, b=2a=3,\; b=2a=3,b=2: ⌊3/2⌋=1\lfloor 3/2\rfloor=13/2=1, а round(3/2)=2\mathrm{round}(3/2)=2round(3/2)=2 (поскольку остаток r=1≥b/2=1r=1\ge b/2=1r=1b/2=1).
- a=5, b=2a=5,\; b=2a=5,b=2: ⌊5/2⌋=2\lfloor 5/2\rfloor=25/2=2, round(5/2)=3\mathrm{round}(5/2)=3round(5/2)=3.
- При отрицательных: в языках с усечением к нулю a=−3, b=2a=-3,\; b=2a=3,b=2: целочисленное деление даёт −1-11, а округление round(−1.5)=−2\mathrm{round}(-1.5)=-2round(1.5)=2 — различие.
- Точная полуцелая ситуация: a=3, b=2a=3,\; b=2a=3,b=2 (см. первый пример) или a=6, b=4a=6,\; b=4a=6,b=4 — здесь r=b/2r=b/2r=b/2, и итог зависит от правила «половинок».
Вывод: можно безопасно заменить только если известно, что остаток удовлетворяет r<∣b∣/2r<|b|/2r<b∣/2 (и при равенстве — что правило округления совпадает с поведением используемого целочисленного деления).
25 Ноя в 11:44
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир