c - 计算平方根的递归算法

Question

我有一段代码可以通过以下方式计算数字的平方根:

void f1(int,int);

int main(){
    int i=1;
    int n;
    scanf("%d",&n);
    f1(n,i);
    getch();
    return 0;
}

void f1(int n,int i){
    if((n*10000)-(i*i)<=0)
        printf("%f",(double)i/100);
    else
        f1(n,i+1);
}

我不知道为什么要使用 n*10000 - i*i。有人可以解释这段代码吗？

Answer 1

让我们考虑这个例子 n=100 .对于第一组递归，我们有 i=1,2,3,... .因此，对于这些调用，我们有 n*10000 - i*i >= 0 .然后在某个时候我们有 i=999观察 n*10000 - 999*999 >= 0 .下一个递归步骤有 i=1000我们看到 n*10000 - 1000*1000 <= 0 , 所以我们打印 (double)i / 100 , 这就是 10 .如您所见，结果只是 n=100 的平方根.

一般来说，最小的数i/100满意n*10000 - i*i <= 0与 n 的平方根“非常接近” ，因为以下原因:

sqrt(n*10000) = sqrt(n)*sqrt(10000) = sqrt(n)*100

我们有:

n*10000 - i*i <= 0            | +i*i
      n*10000 <= i*i          | sqrt both sides
  sqrt(n)*100 <= i            | /100
      sqrt(n) <= i/100

因此，我们正在寻找最小的数字i/100大于或等于 sqrt(n)并将此数字用作 sqrt(n) 的近似值.