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 表示范围的自然数，完成下面的判断题和单选题：

判断题

该算法最准确的时间复杂度分析结果为 O(log n + k)。
当输入为 9801 1 时，输出的第一个数为 99。
对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成 1。
该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。
单选题
当输入为 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. 前三种情况都有可能

答案：

A（正确）
A（正确）
B（错误）
B（错误）
C（1.5）
B（1.732）
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;}

日记详情

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