阅读程序3解析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**************************************************************** 
 * Description: 2022_J_3
 * Author: Alex Li
 * Date: 2023-08-15 22:39:41
 * LastEditTime: 2023-08-23 23:17:11
****************************************************************/
#include <iostream>
using namespace std;
  
  int n,k;
  //solve1采用二分法,找到最接近小于或等于n的平方根的整数
  int solve1(){
      int l = 0, r = n;
    while(l <= r){
         int mid = (l + r) / 2;   //每次二分,mid逐渐接近我们要找的数。
         if (mid * mid <= n) l = mid + 1; //用mid^2<=n 做判断
         else r = mid - 1;
     }
     return l - 1;
 }
 //牛顿迭代求平方根。取x<n  对 x=(x+n/x)/2 不断循环计算,x会逐渐接近n的平方根
 double solve2(double x){
         if (x == 0) return x;
         for (int i = 0; i < k; i++)  //
             x = (x + n / x) / 2;
     return x;
 }

 int main(){
     cin >> n >> k;
     //solve1得到一个最接近的小于或等于n的平方根的数,把这个数再给到solve2进行计算。
     double ans = solve2(solve1());
     //如果n的平方根是整数,哪么ans是整数,ans*ans==n成立。
     cout << ans << ' ' << (ans * ans == n) << endl;
     return 0;
 }

该程序求n的平方根。
solve1是利用二分法找到小于或等于sqrt(n)的最大正整数。
sovle2是利用牛顿迭代法求平方根。


问题一:该算法最准确的时间复杂度分析结果为 O(logn+k)。
对,solve1是二分,复杂度是logn,sovle2是循环k次,两函数虽然是嵌套,但算法叠加,O(logn+k)


问题二:当输入为“9801 1”时,输出的第一个数为“99”。
对,模拟带入即可,因为99^2等于9801,所以solve1结果就是99,sovle2结果也是99。


问题三:对于任意输入的 n,随着所输入 k 的增大,输出的第二个数会变成“1”。

错,输出的第二个数变成“1”是指 ans*ans=n这个表达式为值,因为ans是solve2的返回值,而solve2返回值是double类型(8个字节),小数点精度有限,最后会有误差。


问题四:该程序有存在缺陷。当输入的 n 过大时,第 12 行的乘法有可能溢出,因此应当将 mid 强制转换为 64 位整数再计算。

错,输入的 n 是不超过47000的自然数,所以mid最大值也就是23500。不会溢出。


问题五:当输入为“2 1”时,输出的第一个数最接近( )。
1.5,solve1运行后是1,sovle2运行for循环一次后是x=(1+2/1)/2=1.5。


问题六:当输入为“3 10”时,输出的第一个数最接近( )。

1.732
n=3, x=1, k=10
i=0 (1+3/1)2=2
i=1 (2+3/2)2=1.75
i=2 (1.75+3/1.75)/2=1.732


问题七:当输入为 “256 11” 时,输出的第一个数( )。

等于16,256开根号正好就是16,所以solve1结果是16,solve2结果也是16

Scroll to Top