马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 zhangjinxuan 于 2023-1-9 14:26 编辑
一：枚举法
思路：设置变量i = 0，如果 i * i > n ,退出循环，否则i++
时间复杂度：O(n ^ 0.5)
代码：int solve(int number) {
int i = 0;
for (; i * i < number; ++i);
if (i * i == number) //完全平方数特殊处理
return i;
return i - 1;
}
优点：适合初学者
二：二分法
思路：使用二分答案求出平方根
时间复杂度： O(log2 n)
代码：int solve1(int number) {
int l = 1, r = number;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (mid * mid <= number)
l = mid;
else
r = mid;
}
return l;
}
优点：时间复杂度低，较推荐
三：小数二分法
思路：在二分答案上做一些改动，使支持小数
时间复杂度：O(log2 n)double solve2(double number) {
double l = 1, r = number;
while (fabs(l * l - number) > 0.00001) {
double mid = (l + r) / 2;
if (mid * mid <= number)
l = mid;
else
r = mid;
}
return l;
}
优点：支持小数，精度较高，较推荐
四：牛顿迭代算法
思路：使用牛顿迭代算法，求出平方根，但因为是大学学的算法，这里不赘述
时间复杂度：O(1)double solve3(double number) {
double x = 1;
for (int i = 1; i <= 30; ++i) //可以自定义，最好在20以上，数字越高精度越高
x = (x + number / x) / 2;
return x;
}
优点：代码简单，精度较高，时间复杂度低，个人推荐
五：牛顿迭代算法+二分（借鉴于CSP-J2022初赛）
思路：牛顿迭代算法加二分，可以减少迭代时循环次数，时间复杂度略显提升
时间复杂度：O(log2 n)
代码：int __sqrt1(int number) {
int l = 1, r = number;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (mid * mid <= number)
l = mid;
else
r = mid;
}
return l;
}
double solve4(double number) {
double x = __sqrt1(number);
for (int i = 1; i <= 10; ++i) //有二分的辅助，循环次数可以适当减少，最好10以上
x = (x + number / x) / 2;
return x;
}
优点：精度高，效率还行，
六：cmath
思路：cmath库 sqrt(n) 一行解决（注，需要导入cmath)
代码：优点：代码短,效率高，懒人福音
缺点：真挑不出毛病... | 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-9-21 19:15:36
置顶卡
千斤顶
显身卡
楼主
发表于 2022-9-21 19:52:10
