将while循环转换为数学方程？

Question

将while循环转换为数学方程？

16

我在程序中有两个简单的while循环，感觉它们应该是数学方程式，但我不知道如何将它们转换：

float a = someValue;
int b = someOtherValue;
int c = 0;

while (a <= -b / 2) {
    c--;
    a += b;
}
while (a >= b / 2) {
    c++;
    a -= b;
}

这段代码可以按原样工作，但我觉得可以简化成数学方程式。这里的想法是将一个偏移量（someValue）应用于坐标（c），以最小化距离瓷砖中心（大小为someOtherValue）的距离。如果有任何帮助，将不胜感激。

- Sydius

不错的见解——看到这可以简化为一个简单的公式。 - Pat Notz

有人能请解释一下这两个循环的作用吗？我死活想不出来。 - Johannes Schaub - litb

想象一下一个间隔为'b'的平铺：...|....|....|....|...其中瓷砖被编号，第0个瓷砖位于0的中心（它从-b/2到b/2）。这段代码想要找出'a'在哪个瓷砖中。第一个循环将'a'移动直到它不在中心瓷砖的左侧，第二个循环将其移动直到不在右侧。 - ShreevatsaR

@litb：这可能会有所帮助：想一想如果你只能使用加法和减法，并且不能使用内置的%或除法，如何实现“％”（余数）（比如对于一个正数进行取模）。 - ShreevatsaR

4个回答

2

c = (int)((a - (b / 2)) / b + 1);
a -= c * b;

测试用例请参考http://pastebin.com/m1034e639

。

- paranoidgeek

使用 floor 而不是将其转换为整数并删除小数部分，可以使其适用于负值。 - Sydius

1

我认为你想要这样的东西：

c = ((int) a + b / 2 * sign(a)) / b

这应该与您的循环匹配，除了某些情况下b是奇数，因为当b是奇数时，从-b/2到b/2的范围比b小。

- Dave L.

“sin”不是“sign”，但是你需要一个正弦波函数。 - Ed S.

我认为Dave真正想表达的是sign()函数，其定义如下：int sign(x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }。 - Greg Hewgill

不正确的例子：以a = b = 10为一个简单的例子，那么两个循环都不会执行（因此c=0），但是该答案会说c=1。 - ShreevatsaR

Shreevatsar：这不是真的。如果a = b = 10，则a >= b/2，因此后面的循环将运行一次，c = 1。 - Dave L.

哦，抱歉，我没有想清楚。对于a=b=10，这意味着c=((int) 10+5)/10，实际上是1.5 :-) 但是如果a和b是整数，那么“/”表示整数除法，所以对于正的a，它是floor(a+b/2)/b，所以正确，对于负的a，它是ceil(a-b/2)/b=floor((a+b/2)/b) 除非 b|(a-b/2)。 - ShreevatsaR

显示剩余2条评论

0

假设b为正数，abs(c) = floor((abs(a) - b/2) / b)。然后，将a的符号应用于c。

- buti-oxa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ShreevatsaR · Accepted Answer

可以证明以下内容是正确的：

c = floor((a+b/2)/b)
a = a - c*b

请注意，floor指的是向负无穷方向取整，而不是朝0取整。(例如，floor(-3.1)=-4。库函数floor()可以实现这一点; 只需确保不要将其强制转换为int，因为后者通常会朝0舍入，而不是向下舍入。)

假设b严格为正数，否则两个循环都不会终止: 添加b不会使a变大，减去b也不会使a变小。在此假设的基础上，我们可以证明上述代码是有效的。（paranoidgeek的代码也几乎正确，只是使用了int类型的强制转换，而没有使用floor。）

聪明的证明方法：该代码从a中添加或减去b的倍数，直到a在[-b / 2，b / 2)之间，您可以将其视为从a / b 中添加或减去整数，直到 a / b 在 [-1/2,1/2)之间，即直到（称其为x）在[0,1)之间的值为(a/b+1/2)。因为您只是通过整数更改它，所以x的值不会mod 1，即它会到达其mod 1的余数，即x-floor(x)。因此，您进行的减法操作的有效次数（记为c）是floor(x)。

繁琐的证明方法：第一个循环结束时，c的值是循环运行的次数的负数，即：

如果：a>-b/2 <=> a+b/2>0，那么c=0
如果： -b/2 ≥ a > -3b/2 <=> 0 ≥ a+b/2 > -b <=> 0 ≥ x > -1，那么c=-1
如果：-3b/2 ≥ a > -5b/2 <=> -b ≥ a+b/2 > -2b <=> -1 ≥ x > -2等等，那么c=-2

在这里，x = (a+b/2)/b，因此当x>0时，c为0；否则c为"ceiling(x)-1"。如果第一个循环至少运行了一次，则在最后一次循环执行之前，它将≤-b/2，因此现在它≤b/2。根据其是否完全等于b/2（即开始时x是否完全等于非正整数），第二个循环将执行1次或0次，并且c为ceiling(x)或ceiling(x)-1。因此，这解决了第一个循环运行时的情况。

如果第一个循环未运行，则在第二个循环结束时，c的值为：

如果：a a-b/2<0，那么c=0

如果：b/2≤a<3b/2 <=> 0≤a-b/2 0≤y<1，那么c=1

如果：3b/2≤a<5b/2 <=> b≤a-b/2<2b <=> 1≤y<2等等，那么c=2

在这里，y = (a-b/2)/bx = (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)，当 0c 是 0,
当 1≤x 时，只有 0≤y，所以 c 再次是第二个项，即 floor(x)。因此，在所有情况下，c = floor(x)。