把while循环变成数学方程式？

Question

我在我的程序中有两个简单的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).任何帮助,将不胜感激.

Answer 1

可以证明以下是正确的:

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

注意,floor表示向下舍入,向负无穷大:不向0(例如floor(-3.1)= - 4. floor()库函数将执行此操作;只是确保不要仅转换为int,通常将向0舍入为0 .)

大概b是正面的,因为否则两个循环都不会终止:添加b不会a变大,减去b也不会变a小.有了这个假设,我们可以证明上面的代码是有效的.(并且paranoidgeek的代码也几乎是正确的,除了它使用强制转换为int而不是floor.)

证明它的巧妙的方式:代码添加或减去的倍数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如果:-3b /2≥a> -5b/2 <=>-b≥a+ b/2> -2b <=>-1≥x> -2等,

其中x = (a+b/2)/b,所以c为:0如果x> 0,则为"ceiling(x)-1".如果第一个循环完全运行,则在最后一次执行循环之前它是≤-b/2,所以它现在≤-b/2 + b,即≤b/ 2.根据它是否正好是b/2(即,x当你开始时是否恰好是一个非正整数),第二个循环恰好运行1次或0,c是天花板(x)或天花板( X)-1.所以这解决了第一个循环运行时的情况.

如果第一个循环没有运行,那么第二个循环结束时c的值为:

• 0如果:a <b/2 <=> ab/2 <0
• 1如果:b /2≤a<3b/2 <=>0≤ab/ 2 <b <=>0≤y<1
• 2如果:3b /2≤a<5b/2 <=>b≤ab/ 2 <2b <=>1≤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)在所有情况下.