C++ 利用二分法求整数平方根
#include <iostream>
#include <>
using namespace std;
// 指定精度与迭代次数
double sqrt(int num, double accuracy, int iteration);
// 指定精确到小数点后多少位
// 该重载函数也能实现求平方根，但是似乎由于计算机浮点计算的近似性
// 没有上述重载函数好用，只做个人娱乐用
double sqrt(int num, int accuracy);
// 利用二分法求整数的平方根
double sqrt(int num)
{
if (num < 0)
return -1.0;
if (num == 0 || num == 1)
return num;
return sqrt(num, 0.0000001, 1000000);
//return sqrt(num, 6);
}
static bool isReachedAccuracy(double actual, double refer, double accuracy)
{
double delta = abs(actual - refer) / refer;
return delta < accuracy;
}
// 指定精度与迭代次数
double sqrt(int num, double accuracy, int iteration)
{
double minValue = 1.0, maxValue = num;
for (int i = 0; i < iteration; i++)
{
double midValue = (minValue + maxValue) / 2.0;
double square = midValue * midValue;
if (isReachedAccuracy(square, num, accuracy))
return midValue;
else if (num > square)
minValue = midValue;
else if (num < square)
maxValue = midValue;
}
return -1.0;
}
// 浮点数相等的精度
static const double delta = 0.0000000000001;
// 判断两个浮点数是否近似相等
inline bool equal(double lhs, double rhs)
{
return abs(lhs - rhs) < delta;
}
// 假设actaul=6.01，则place应为3，该函数找出6.01x，使得(6.01x)*(6.01x)<=refer<(6.01[x+1]))*(6.01[x+1])
// 可采用二分法实现，为了简单姑且采用简单的迭代
static double sqrtForFractionalPart(double actual, double refer, int place)
{
double base = pow(10.0, -place);
for (int i = 0; i <= 9; i++)
{
actual += base;
double square = actual * actual;
if (equal(square, refer))
return actual;
if (square > refer)
break;
}
actual -= base;
return actual;
}
// 指定精确到小数点后多少位
double sqrt(int num, int accuracy)
{
double result = 0.0;
// 整数部分
// 找出整数a，其中a*a <= num < (a+1)*(a+1)
int minValue = 1, maxValue = num;
while (minValue < maxValue)
{
int midValue = minValue + (maxValue - minValue) / 2;
// 避免产生溢出
long long square = (long long)midValue * (long long)midValue;
if (square == num)
// 之所以不把整数部分的计算封装成一个单独的函数
// 就是为了这条语句能够直接返回
return midValue;
else if (num > square)
minValue = midValue + 1;
else if (num < square)
maxValue = midValue;
}
result += minValue - 1;
// 小数部分
for (int i = 1; i <= accuracy; i++)
result = sqrtForFractionalPart(result, num, i);
return result;
}
void testSqrt()
{
int num = 0;
double result = 0.0;
// 设置浮点数显示精度
cout.precision(9);
cout << "input integer num: " << endl;
while (cin >> num)
{
result = sqrt(num);
if (result < 0.0)
cout << "please enter a non negative number. \n" << endl;
else
cout << "the result of sqrt(num) is: \n" << result << "\n" << endl;
cout << "input integer num: " << endl;
}
}
int main()
{
testSqrt();
return 0;
}