C++ 算法分析与判断题：求解平方根并分析时间复杂度

#include <iostream>

using namespace std;

int n, k;

int solve1()
{
    int l = 0, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (mid * mid <= n) l = mid + 1;
        else r = mid - 1;
    }
    return l - 1;
}

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;
    double ans = solve2(solve1());
    cout << ans << ' ' << (ans * ans == n) << endl;
    return 0;
}

假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

该算法最准确的时间复杂度分析结果为（　　）

A. 正确 B. 错误

当输入为'9801 1'时，输出的第一个数为'99'。（　　）

A. 正确 B. 错误

对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成'1'。（　　）

A. 正确 B. 错误

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

A. 正确 B. 错误

当输入为'2 1'时，输出的第一个数最接近（　　）。

A. 1 B. 1.414 C. 1.5 D. 2

当输入为'3 10'时，输出的第一个数最接近（　　）。

A. 1.7 B. 1.732 C. 1.75 D. 2

当输入为'256 11'时，输出的第一个数（　　）。

A. 等于 16 B. 接近但小于 16 C. 接近但大于 16 D. 前三种情况都有可能

答案解析：

B 错误。该算法的时间复杂度是 O(logn)，而不是 O(1)。
A 正确。根据 solve1 函数的实现，当输入为'9801 1'时，solve1 返回的结果是 99，而 solve2 函数对该结果进行处理后返回的结果是 99.0000099004975，输出的第一个数为'99'，与题目描述一致。
A 正确。根据 solve2 函数的实现，无论输入的 n 是多少，只要 k 足够大，solve2 函数最终返回的结果会趋近于 1。
B 错误。该程序没有溢出的缺陷。根据题目给出的条件，n 不超过 47000，而 mid 的取值范围是 0 到 n，所以 mid 的乘积不会超过 32 位整数的表示范围。
B 1.414。当输入为'2 1'时，solve1 返回的结果是 2，solve2 对该结果进行处理后返回的结果是 1.41421356237，最接近 1.414。
B 1.732。当输入为'3 10'时，solve1 返回的结果是 1，solve2 对该结果进行处理后返回的结果是 1.73205080757，最接近 1.732。
C 接近但大于 16。当输入为'256 11'时，solve1 返回的结果是 16，solve2 对该结果进行处理后返回的结果是 16.0000000000001，接近但大于 16。