5

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

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. 有人可以解释一下这段代码吗?

4

5 回答 5

8

让我们考虑这个例子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)

于 2013-11-12T08:30:14.730 回答
3

n你用and调用函数i,现在只要i*i小于n * 10000你增加你的i.

如果你的 i*i 大于 n * 10000 你打印 i / 100

例如:您使用 f1(1,1) 调用函数:

 1*10000 >= 1*1 --> f1(1,2);
 1*10000 >= 2*2 --> f1(1,3);
 1*10000 >= 3*3 --> f1(1,4);
 ....
 1*10000 >= 99*99 ->f1(1,100);
 1*10000 <= 100*100 --> printf("%f",i/100.0); which gives: 1

编辑:另一个例子,你寻找 8 的平方根: f1(8,1);

 8*10000 >= 1*1 --> f1(8,2);
 8*10000 >= 2*2 --> f1(8,3);
 1*10000 >= 3*3 --> f1(8,4);
 ....
 8*10000 >= 282*282 ->f1(8,283);
 8*10000 <= 283*283 --> printf("%f",i/100.0); which gives: 2.83

 and 2.83 * 2.83 = 8.0089

编辑:你可能会问为什么 n*10000,这是因为计算误差变小了,例如:如果你在 8 的 sqrt 示例中使用 n*100 和 i/10,你会得到

8*100 <= 29*29 --> 2.9
2.9 * 2.9 = 8.41 which is not good as 2.83 in the other example
于 2013-11-12T08:24:41.530 回答
1

那只是为了增加一些精度。

void f1(int n,int i){
    printf("value of i is=%d \n",i);
    if(n-i*i<=0)
        printf("%f",i);
    else
        f1(n,i+1);
}

此代码仅适用于完美平方数。

void f1(int n,int i){
    printf("value of i is=%d \n",i);
    if((n*100)-(i*i)<=0)
        printf("%f",(double)i/10);
    else
        f1(n,i+1);
}

此代码适用于所有数字,但仅在浮点数后给出一位数字的结果。

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

这是您的代码,它在浮点数后给出 2 位点精度。因此 (n*10000)-(i*i) 根据您的要求是必要的。如果你只想找到完美的,你也可以使用第一个代码。

于 2013-11-12T08:40:34.203 回答
0

考虑这个函数:

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

该函数将递归循环 i 直到 i^2 >=n,这与不递归执行此操作基本相同:

void f1(int n,int i){
    int i = 1;
    while (i*i < n)
        ++i;
    printf("%f",i);
}

现在使用 10000 的技巧只是添加一些由大整数模拟的精度(注​​意它可能会更快地溢出 int) - 你计算 sqrt(100*100*n),即 100*sqrt(n),所以您将结果除以 100。这可以让您获得 2 位精度。

于 2013-11-12T08:33:20.590 回答
0

因为它会将结果四舍五入到小数点后两位。

例如,n=10 结果是 3.17。

如果你想让结果四舍五入到小数点后 3 位,你可以写:

if((n*1000000)-(i*i)<=0) printf("%f",(double)i/1000);

于 2013-11-12T09:07:06.793 回答