2022年CSP-J初赛真题及答案解析(阅读程序3)

2022年CSP-J初赛真题及答案解析(阅读程序3)

第 3 题

1#include<iostream>23usingnamespacestd;45intn,k;67intsolve1()8{9intl=0,r=n;10while(l<=r){11intmid=(l+r)/2;12if(mid*mid<=n)l=mid+1;13elser=mid-1;14}15returnl-1;16}1718doublesolve2(doublex)19{20if(x==0)returnx;21for(inti=0;i<k;i++)22x=(x+n/x)/2;23returnx;24}2526intmain()27{28cin>>n>>k;29doubleans=solve2(solve1());30cout<<ans<<' '<<(ans*ans==n)<<endl;31return0;32}

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

判断题

1. 该算法最准确的时间复杂度分析结果为 O(log n + k)。
2. 当输入为 9801 1 时，输出的第一个数为 99。
3. 对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成 1。
4. 该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。
   单选题
5. 当输入为 2 1 时，输出的第一个数最接近（ ）。
   A. 1
   B. 1.414
   C. 1.5
   D. 2
6. 当输入为 3 10 时，输出的第一个数最接近（ ）。
   A. 1.7
   B. 1.732
   C. 1.75
   D. 2
7. 当输入为 256 11 时，输出的第一个数（ ）。
   A. 等于 16
   B. 接近但小于 16
   C. 接近但大于 16
   D. 前三种情况都有可能

答案：

1. A（正确）
2. A（正确）
3. B（错误）
4. B（错误）
5. C（1.5）
6. B（1.732）
7. A（等于 16）

解析：
solve1 是二分求整数平方根（向下取整）。solve2 执行 k 次牛顿迭代求 n 的平方根。时间复杂度为 O(log n)（二分） + O(k)。输入 9801=99²，solve1返回99，迭代一次不变，故输出99。对于非完全平方数，即使无限迭代，ans*ans == n也不会为真（浮点误差），输出第二个数始终为0，不会变成1，所以3错。n≤47000，mid²不会溢出32位，所以4错。输入2,1：初值为1，迭代一次得 (1+2/1)/2=1.5。输入3,10：迭代收敛到√3≈1.732。输入256,11：初值16，迭代后仍为16（完全平方）。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}