如何将循环提取到恒定时间计算中？

Question

是否可以预先确定变量x并在没有循环的情况下d调用？initialFunction()while(1)

void function( int xc, int yc, int r, int color ){
    int x = 0;
    int y = r;
    int d = 1-2*r;
    while( 1 ){
        x++;
        d += 4*x-2;
        if( d>0 ){
            initialFunction(x,y,d);
            break;
        }
    }
    while( x>=y ){
        x++;
        d += 4*x-2;
        if( d>0 ){
            // some code
        }
    }
}

Answer 1

x该循环执行和的迭代计算d。您要求的是封闭式版本。这个特定的过程恰好适合表达d为有限项之x和，我们可以用数学术语这样写：

d = 1 - 2r + SUM(i = 1, x) [4i - 2]

该公式中的 对应于变量在迭代过程中采用的i各种值，并且是该过程中 的初始值。和是迭代后这些变量的最终值（并且是计算的不变值）。x1 - 2rdxdrr

一点代数就可以让我们

d = 1 - 2r + 4*SUM(i = 1, x) [i] - 2*SUM(i = 1, x) [1]

这两个有限和有众所周知的解。应用它们给我们带来

d = 1 - 2r + 4x(x+1)/2 - 2x

，我们可以进一步简化为

d = 1 - 2r + 2x^2

x我们想要使严格为正的最小正值d，所以我们解决

1 - 2r + 2x^2 > 0

或者，等价地，

x^2 > r - 1/2

如果r小于或等于1，则x满足该方程的最小正整数为1。否则，两边取正平方根，得到

x > sqrt(r - 1/2)

我们进一步观察到，因为r是一个正整数，

• 平方根是明确定义的，并且
• 平方根不是整数。

因此，满足方程的最小值x是r - 1/2 的平方根的整数上限。我们可以将其代入上面的方程之一以获得 的相应值d。

回到C，我们可以将其表示为

if (r <= 1) {
    x = 1;
} else {   
    x = ceil(sqrt(r - 0.5));
}
d = 1 - 2*r + 2*x*x;

Answer 2

基于此代码

while(1) {
    x++;
    d += 4*x-2;
    if( d>0 ){
        initialFunction(x,y,d);
        break;
    }
}

您可以写出d第 n 次迭代后的公式：

 d_n = d_0 + 4-2 + 8-2 + 12-2 + 14-2 + ....
     = d_0 +  2  +  6  +  10  +  12  + ...

添加的内容呈线性增加，即二阶多项式：

 d_n = d_0 + a + b*n + c*n*n

我将把它留给您来确定系数（您只需要插入一些您已经知道的值，例如在n=1第 st 迭代之后，该值d0+2必须等于d_0+a+b+c）。一旦你得到它们，你就解决了

 d_0 + a + b*n + c*n*n == 0 

为了n。这里描述了如何做到这一点： https: //en.wikipedia.org/wiki/Quadratic_equation