X的平方根
题目描述
给定一个数，写出算法，将其开方，结果保留6位小数。
输入一个数(可以是小数)，输出结果为其平方根，结果保留6位小数
题目分析
采用浮点数二分法，对齐进行找值。假定中值为最终解，给定上下限，然后求中值；比较中值平方和与x的大小，并修改其上下限，依次循环
代码实现
#include<iostream>
using namespace std;
int main(){
double x;
scanf("%lf", &x);
double l = 0, r = x;
while(r - l >= 1e-8)
{
double mid = (l + r) / 2;
if(mid * mid >= x) r = mid;
else l = mid;
}
printf("%lf\n", l);
return 0;
}
|
运行结果
输入
输出
总结
二分法思维固然简单，但是精度需要得以控制，精度控制不当，则容易陷入死循环。
x的平方根2
题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
|
题目分析
题目要求保留整数，此处就得知道，所得出的整数的平方一定会小于等于x，即$n^2<=x$，且$(n+1)^2>x$，满足此条件即可确定为其取整后的平方根。
代码实现
#include<iostream>
using namespace std;
int mySqrt(int x){
int l = 0, r = x / 2;
while(l <= r)
{
int mid = (l + r) / 2;
if(mid * mid <= x && (mid + 1) * (mid + 1) > x) return mid;
else if(mid * mid > x) r = mid - 1;
else l = mid + 1;
}
return l;
}
int main(){
int x;
scanf("%d", &x);
printf("%d", mySqrt(x));
return 0;
}
|
运行结果
输入
输出
