前言
楼主参加2014年创新工厂笔试，几道算法题目，堆排序和杨氏矩阵这种题目就不说了，有一个求整数开方的算法，当时难住了大部分同学，我用的是移位方法，后来想了一下，其实给定了精度，应该用二分逼近算法
题目
求整数N的开方，精度在0.001
思路
这里给出多种实现方案，读者自取
二分法
若N大于1,则从[1, N]开始，low = 1, high = N, mid = low + （high - low） 》 1开始进行数值逼近
若N小于1,则从[N, 1]开始，low = 0, high = N, mid = low + （high - low） 》 1开始进行数值逼近
ac代码
/**
* 创新工厂2014年校招算法题目，求整数N的开方，精度为0.001
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ACCURACY 0.001
double newSqrt（double n）
{
double low, high, mid, tmp;
// 获取上下界
if （n > 1）
{
low = 1;
high = n;
} else {
low = n;
high = 1;
}
// 二分法求开方
while （low <= high） {
mid = （low + high） / 2.000;
tmp = mid * mid;
if （tmp - n <= ACCURACY && tmp -n >= ACCURACY * -1） {
return mid;
} else if （tmp > n） {
high = mid;
} else {
low = mid;
}
}
return -1.000;
}
int main（void）
{
double n, res;
while （scanf（"%lf", &n） != EOF） {
res = newSqrt（n）；
printf（"%lf\n", res）；
}
return 0;
} |