整數開方算法

前言 樓主參加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;  
}