Ответ 1
Можно доказать, что верно следующее:
c = floor((a+b/2)/b)
a = a - c*b
Обратите внимание, что слово означает округление вниз, к отрицательной бесконечности: не к 0. (Например, floor (-3.1) = - 4. Библиотечные функции floor() будут делать это, просто не забудьте просто сбрасывать int, что обычно будет округлять к нулю.)
Предположительно b строго положителен, потому что в противном случае ни один цикл никогда не завершится: добавление b больше не сделает a больше, а вычитание b не сделает меньше a. С этим допущением мы можем доказать, что приведенный выше код работает. (И код paranoidgeek также почти корректен, за исключением того, что вместо floor он использует cast для int).
Умный способ доказать это:
Код добавляет или вычитает кратность b из a, пока a не находится в [-b/2,b/2), который вы можете рассматривать как добавление или вычитание целых чисел из a/b, пока a/b не находится в [-1/2,1/2), то есть до (a/b+1/2) (назовем его x) находится в [0,1). Поскольку вы только меняете его целыми числами, значение x не меняет mod 1, то есть оно переходит в остаток mod 1, который равен x-floor(x). Таким образом, эффективное количество вычитаний, которое вы делаете (c), равно floor(x).
Тонкий способ доказать это:
<суб > В конце первого цикла значение c является отрицательным числом циклов цикла, то есть:
- 0, если: a > -b/2 <= > a + b/2 > 0
- -1, если: -b/2 ≥ a > -3b/2 <= > 0 ≥ a + b/2 > -b <= > 0 ≥ x > -1
- -2 if: -3b/2 ≥ a > -5b/2 <= > -b ≥ a + b/2 > -2b <= > -1 ≥ x > -2 и т.д.,
где x = (a+b/2)/b, поэтому c: 0, если x > 0 и "потолок (x) -1" в противном случае. Если первый цикл выполнялся вообще, то он был ≤ -b/2 незадолго до того, как последний раз был выполнен цикл, поэтому теперь он равен ≤ -b/2 + b, то есть ≤ b/2. В соответствии с тем, является ли оно ровно b/2 или нет (т.е. Если x, когда вы начали, было точно неположительным целым числом или нет), второй цикл выполняется ровно 1 раз или 0, а c - либо потолок (x) или потолок (x) -1. Таким образом, это решает его для случая, когда первый цикл выполнялся.
Если первый цикл не выполнялся, то значение c в конце второго цикла:
- 0, если: a < b/2 <= > a-b/2 < 0
- 1, если: b/2 ≤ a < 3b/2 <= > 0 & le; a-b/b <= > 0 & le; y < 1
- 2, если: 3b/2 ≤ a < 5b/2 <= > b & le; a-b/2b <= > 1 & le; y < 2 и т.д.,
где y = (a-b/2)/b, поэтому c: 0, если y < 0 и 1 + floor (y) в противном случае. [И a теперь, безусловно, b/2 и ≥ -b/2.]
Итак, вы можете написать выражение для c как:
x = (a+b/2)/b
y = (a-b/2)/b
c = (x≤0)*(ceiling(x) - 1 + (x is integer))
+(y≥0)*(1 + floor(y))
Конечно, в следующий раз вы заметите, что (ceiling(x)-1+(x is integer)) совпадает с floor(x+1)-1, который является floor(x), и что y на самом деле x-1, поэтому (1+floor(y))=floor(x), а также для условных выражений:
когда x≤0, это не может быть (y≥0), поэтому c - это только первый член, который является floor(x),
когда 0 < x < 1, ни одно из условий не выполняется, поэтому c есть 0,
когда 1 ≤ x, то только 0≤y, поэтому c - это просто второе слагаемое, которое является floor(x) снова.
Так что c = floor(x) во всех случаях.
Суб >