I have two simple while loops in my program that I feel ought to be math equations, but I'm struggling to convert them:
我的程序中有两个简单的while循环，我觉得应该是数学方程，但我很难把它们转换成:
float a = someValue;
int b = someOtherValue;
int c = 0;
while (a <= -b / 2) {
c--;
a += b;
}
while (a >= b / 2) {
c++;
a -= b;
}
This code works as-is, but I feel it could be simplified into math equations. The idea here being that this code is taking an offset (someValue) and adjusting a coordinate (c) to minimize the distance from the center of a tile (of size someOtherValue). Any help would be appreciated.
这段代码运行正常，但我觉得它可以简化成数学方程。这里的思想是，这段代码使用偏移量(someValue)并调整一个坐标(c)，以最小化离块中心(大小为其他值)的距离。如有任何帮助，我们将不胜感激。
4 个解决方案
#1
36
It can be proved that the following is correct:
可以证明以下是正确的:
c = floor((a+b/2)/b)
a = a - c*b
Note that floor means round down, towards negative infinity: not towards 0. (E.g. floor(-3.1)=-4. The floor() library functions will do this; just be sure not to just cast to int, which will usually round towards 0 instead.)
注意地板的意思是向下四舍五入，朝向负无穷:不是朝向0。(如地板(-3.1)= 4。floor()库函数将执行此操作;只是要确保不只是投射到int，它通常会转到0)。
Presumably b is strictly positive, because otherwise neither loop will never terminate: adding b will not make a larger and subtracting b will not make a smaller. With that assumption, we can prove that the above code works. (And paranoidgeek's code is also almost correct, except that it uses a cast to int instead of floor.)
假设b是严格正的，因为否则任何循环都不会终止:加b不会使a变大，减b不会使a变小。有了这个假设，我们可以证明上面的代码是有效的。(而且帕拉纳基克的代码也几乎是正确的，只是它使用了一个转换到int而不是floor。)
Clever way of proving it: The code adds or subtracts multiples of b from a until a is in [-b/2,b/2), which you can view as adding or subtracting integers from a/b until a/b is in [-1/2,1/2), i.e. until (a/b+1/2) (call it x) is in [0,1). As you are only changing it by integers, the value of x does not change mod 1, i.e. it goes to its remainder mod 1, which is x-floor(x). So the effective number of subtractions you make (which is c) is floor(x).
用聪明的方法来证明它:代码增加或减去b的倍数，直到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)是(x)
Tedious way of proving it:
冗长的证明方法:
At the end of the first loop, the value of c is the negative of the number of times the loop runs, i.e.:
在第一个循环结束时，c的值是循环运行次数的负数，即:
- 0 if: a > -b/2 <=> a+b/2 > 0
- 0 if: a > -b/2 <=> a+b/2 > 0
- -1 if: -b/2 ≥ a > -3b/2 <=> 0 ≥ a+b/2 > -b <=> 0 ≥ x > -1
- 1如果:- b / 2≥2 > 3 b / < = > 0≥+ b / 2 > - b < = > 0≥x > 1
- -2 if: -3b/2 ≥ a > -5b/2 <=> -b ≥ a+b/2 > -2b <=> -1 ≥ x > -2 etc.,
- 2如果:3 b / 2≥2 > 5 b / < = > - b≥2 b + b / 2 > < = > 1≥x > 2等等。
where x = (a+b/2)/b, so c is: 0 if x>0 and "ceiling(x)-1" otherwise. If the first loop ran at all, then it was ≤ -b/2 just before the last time the loop was executed, so it is ≤ -b/2+b now, i.e. ≤ b/2. According as whether it is exactly b/2 or not (i.e., whether x when you started was exactly a non-positive integer or not), the second loop runs exactly 1 time or 0, and c is either ceiling(x) or ceiling(x)-1. So that solves it for the case when the first loop did run.
其中x = (a+b/2)/b，则c =:如果x> = 0，则c =:如果第一个循环运行,那么这是≤- b / 2前最后一次循环执行,所以≤- b / 2 + b现在,即≤b / 2。根据它是否恰好是b/2(即。，当你开始的时候x是一个非正整数，第二个循环正好是1或0,c是上限(x)或者是上限(x)-1。这就解决了第一个循环运行时的问题。
If the first loop didn't run, then the value of c at the end of the second loop is:
如果第一个循环没有运行，那么第二个循环结束时c的值为:
- 0 if: a < b/2 <=> a-b/2 < 0
- 0 if: a < b/2 <=> a-b/2 < 0
- 1 if: b/2 ≤ a < 3b/2 <=> 0 ≤ a-b/2 < b <=> 0 ≤ y < 1
- 1如果:b / 2≤< 3 b / 2 b < = > 0≤a - b / 2 < < = > 0≤y < 1
- 2 if: 3b/2 ≤ a < 5b/2 <=> b ≤ a-b/2 < 2b <=> 1 ≤ y < 2, etc.,
- 2如果:3 b / 2≤5 < b / 2 < = > b≤a - b 2 b / 2 < < = > 1≤y < 2等等。
where y = (a-b/2)/b, so c is: 0 if y<0 and 1+floor(y) otherwise. [And a now is certainly < b/2 and ≥ -b/2.]
其中y = (a-b/2)/b, c =: 0，如果y<0, 1+楼层(y)(和现在肯定是< b / 2≥- b / 2。)
So you can write an expression for c as:
所以你可以把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))
Of course, next you notice that (ceiling(x)-1+(x is integer)) is same as floor(x+1)-1 which is floor(x), and that y is actually x-1, so (1+floor(y))=floor(x), and as for the conditionals:
when x≤0, it cannot be that (y≥0), so c is just the first term which is floor(x),
when 0 < x < 1, neither of the conditions holds, so c is 0,
when 1 ≤ x, then only 0≤y, so c is just the second term which is floor(x) again. So c = floor(x) in all cases.
当然,接下来,您注意到(上限(x)1 +(x是整数))一样的地板(x + 1)1楼(x),y是x - 1,所以(1 +地板(y))=地板(x),至于条件:当x≤0时,它不能(y≥0),所以c是第一项地板(x),当0 < x < 1,两个条件成立,所以c = 0,当1≤x,那么只有0≤y,所以c是地板上的第二个任期(x)。c =底(x)
#2
2
c = (int)((a - (b / 2)) / b + 1);
a -= c * b;
Test case at http://pastebin.com/m1034e639
测试用例在http://pastebin.com/m1034e639
#3
1
I think you want something like this:
我想你想要这样的东西:
c = ((int) a + b / 2 * sign(a)) / b
That should match your loops except for certain cases where b is odd because the range from -b/2 to b/2 is smaller than b when b is odd.
它应该与循环相匹配除了某些情况下b是奇数因为从-b/2到b/2的范围小于b是奇数时。
#4
0
Assuming b is positive, abs(c) = floor((abs(a) - b/2) / b). Then, apply sign of a to c.
假设b为正，那么abs(c) =底板(abs(a) - b/2) / b，然后将a的符号应用到c。
#1
36
It can be proved that the following is correct:
可以证明以下是正确的:
c = floor((a+b/2)/b)
a = a - c*b
Note that floor means round down, towards negative infinity: not towards 0. (E.g. floor(-3.1)=-4. The floor() library functions will do this; just be sure not to just cast to int, which will usually round towards 0 instead.)
注意地板的意思是向下四舍五入，朝向负无穷:不是朝向0。(如地板(-3.1)= 4。floor()库函数将执行此操作;只是要确保不只是投射到int，它通常会转到0)。
Presumably b is strictly positive, because otherwise neither loop will never terminate: adding b will not make a larger and subtracting b will not make a smaller. With that assumption, we can prove that the above code works. (And paranoidgeek's code is also almost correct, except that it uses a cast to int instead of floor.)
假设b是严格正的，因为否则任何循环都不会终止:加b不会使a变大，减b不会使a变小。有了这个假设，我们可以证明上面的代码是有效的。(而且帕拉纳基克的代码也几乎是正确的，只是它使用了一个转换到int而不是floor。)
Clever way of proving it: The code adds or subtracts multiples of b from a until a is in [-b/2,b/2), which you can view as adding or subtracting integers from a/b until a/b is in [-1/2,1/2), i.e. until (a/b+1/2) (call it x) is in [0,1). As you are only changing it by integers, the value of x does not change mod 1, i.e. it goes to its remainder mod 1, which is x-floor(x). So the effective number of subtractions you make (which is c) is floor(x).
用聪明的方法来证明它:代码增加或减去b的倍数，直到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)是(x)
Tedious way of proving it:
冗长的证明方法:
At the end of the first loop, the value of c is the negative of the number of times the loop runs, i.e.:
在第一个循环结束时，c的值是循环运行次数的负数，即:
- 0 if: a > -b/2 <=> a+b/2 > 0
- 0 if: a > -b/2 <=> a+b/2 > 0
- -1 if: -b/2 ≥ a > -3b/2 <=> 0 ≥ a+b/2 > -b <=> 0 ≥ x > -1
- 1如果:- b / 2≥2 > 3 b / < = > 0≥+ b / 2 > - b < = > 0≥x > 1
- -2 if: -3b/2 ≥ a > -5b/2 <=> -b ≥ a+b/2 > -2b <=> -1 ≥ x > -2 etc.,
- 2如果:3 b / 2≥2 > 5 b / < = > - b≥2 b + b / 2 > < = > 1≥x > 2等等。
where x = (a+b/2)/b, so c is: 0 if x>0 and "ceiling(x)-1" otherwise. If the first loop ran at all, then it was ≤ -b/2 just before the last time the loop was executed, so it is ≤ -b/2+b now, i.e. ≤ b/2. According as whether it is exactly b/2 or not (i.e., whether x when you started was exactly a non-positive integer or not), the second loop runs exactly 1 time or 0, and c is either ceiling(x) or ceiling(x)-1. So that solves it for the case when the first loop did run.
其中x = (a+b/2)/b，则c =:如果x> = 0，则c =:如果第一个循环运行,那么这是≤- b / 2前最后一次循环执行,所以≤- b / 2 + b现在,即≤b / 2。根据它是否恰好是b/2(即。，当你开始的时候x是一个非正整数，第二个循环正好是1或0,c是上限(x)或者是上限(x)-1。这就解决了第一个循环运行时的问题。
If the first loop didn't run, then the value of c at the end of the second loop is:
如果第一个循环没有运行，那么第二个循环结束时c的值为:
- 0 if: a < b/2 <=> a-b/2 < 0
- 0 if: a < b/2 <=> a-b/2 < 0
- 1 if: b/2 ≤ a < 3b/2 <=> 0 ≤ a-b/2 < b <=> 0 ≤ y < 1
- 1如果:b / 2≤< 3 b / 2 b < = > 0≤a - b / 2 < < = > 0≤y < 1
- 2 if: 3b/2 ≤ a < 5b/2 <=> b ≤ a-b/2 < 2b <=> 1 ≤ y < 2, etc.,
- 2如果:3 b / 2≤5 < b / 2 < = > b≤a - b 2 b / 2 < < = > 1≤y < 2等等。
where y = (a-b/2)/b, so c is: 0 if y<0 and 1+floor(y) otherwise. [And a now is certainly < b/2 and ≥ -b/2.]
其中y = (a-b/2)/b, c =: 0，如果y<0, 1+楼层(y)(和现在肯定是< b / 2≥- b / 2。)
So you can write an expression for c as:
所以你可以把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))
Of course, next you notice that (ceiling(x)-1+(x is integer)) is same as floor(x+1)-1 which is floor(x), and that y is actually x-1, so (1+floor(y))=floor(x), and as for the conditionals:
when x≤0, it cannot be that (y≥0), so c is just the first term which is floor(x),
when 0 < x < 1, neither of the conditions holds, so c is 0,
when 1 ≤ x, then only 0≤y, so c is just the second term which is floor(x) again. So c = floor(x) in all cases.
当然,接下来,您注意到(上限(x)1 +(x是整数))一样的地板(x + 1)1楼(x),y是x - 1,所以(1 +地板(y))=地板(x),至于条件:当x≤0时,它不能(y≥0),所以c是第一项地板(x),当0 < x < 1,两个条件成立,所以c = 0,当1≤x,那么只有0≤y,所以c是地板上的第二个任期(x)。c =底(x)
#2
2
c = (int)((a - (b / 2)) / b + 1);
a -= c * b;
Test case at http://pastebin.com/m1034e639
测试用例在http://pastebin.com/m1034e639
#3
1
I think you want something like this:
我想你想要这样的东西:
c = ((int) a + b / 2 * sign(a)) / b
That should match your loops except for certain cases where b is odd because the range from -b/2 to b/2 is smaller than b when b is odd.
它应该与循环相匹配除了某些情况下b是奇数因为从-b/2到b/2的范围小于b是奇数时。
#4
0
Assuming b is positive, abs(c) = floor((abs(a) - b/2) / b). Then, apply sign of a to c.
假设b为正，那么abs(c) =底板(abs(a) - b/2) / b，然后将a的符号应用到c。