不用编程语言自带函数，你会如何实现计算…

内容整理自：极客时间—程序员的数学基础课 03 | 迭代法：不用编程语言自带函数，你会如何计算平方根？

1. 什幺是迭代法：

迭代法，简单来说，就是不断的用旧的变量值，来递推计算新的变量值。

2. 迭代法都有哪些具体应用

1. 求数值的精确或者近似解 ：典型的方法包括二分法和牛顿迭代法。

1. 在一定范围内查找目标值 ：典型的方法包括二分查找。

1. 机器学习算法中的迭代 ：相关的模型和算法有很多，比如K- 均值算法（K-means clustering）、PageRank 的马尔科夫链(Markov chain)、梯度下降法（Gradient descent）等等。 迭代法之所以在机器学习中广泛的使用，是因为很多时候，机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解 。而迭代法可以帮助学习算法逐步搜索，直至发现这种解。

3. 示例 求数值的解和查匹配记录

3.1 求数值的解

? ? ? ? 以求一个大于 1 的正数的平方根为例，如果不适用 Java 自带的 Math 类库，如何手动实现呢？

? ? ? ? 这个时间，我们就可以使用二分法查找最优解。举个例子，假如我们要求 10 的平方根，我们要先看一下 1到10 的中间值，就是 (1+10)/2 = 5.5，5.5的平方是大于10的，这个时候，我们就要看 1到5.5 的中间值，就是(1+5.5)/2 = 3.25，3.25的平方也是大于10的，然后继续，直到找到平方和等于10，或者平方和与10的差值在给定的精度范围内的值。

? ? ? ? 示例代码如下：

package match_programing.lesson3_iterator;
/**
 * @Description 求数值的精确或者近似值
 * @author hjh
 *
 */public class SqureRoot {
/**
 * 计算大于 1 的正整数的平方根
 * @param n
 *        待求平方根的正数数
 * @param deltaThreshold
 *        误差的阈值 
 * @param maxTry
 *        二分查找的最大次数
 * @return double
 *        平方根的解
 */public double getSqureRoot(int n, double deltaThreshold, int maxTry) {

if (n <= 1) {
return -1.0;
}

double min = 1.0, max = (double)n;

for (int i = 0; i < maxTry; i++) {
double middle = min + (max - min)/2;    // (min + max)/2 可能导致溢出
double squre = middle * middle;
double delta = Math.abs(squre/n -1);
if (delta <= deltaThreshold) {
return middle;
}
if (squre > n) {
max = middle;
}else {
min = middle;
}
}

return -2.0;    // 表示在指定的循环内，为找到匹配给定精度的值
}


/**
 * 测试代码
 */public static void main(String[] args) {

SqureRoot squreRoot = new SqureRoot();
int n = 10;
double squre = squreRoot.getSqureRoot(n, 0.0001, 100);
if (squre == -1.0) {
System.out.println("请输入大于 1 的正整数 ");
}else if (squre == -2.0) {
System.out.println("未能找到解 ");
}else {
System.out.println(String.format("%d 的平方根是 %s " , n, squre));    // 10 的平方根是 3.162384033203125
}
}
}

3.2 查找匹配记录

? ? ? ? 使用二分法查找匹配记录，其实现的思想和上面的求正整数的平方根是一样的，区别就是：

1. 判断结束的条件不同：求平方根时，是通过判断 某个数的平方是否和输入相等或者满足给定的精度，查找匹配记录则是判断查找值是否与当前字符串相等。

1. 二分查找需要确保被搜索的空间是有序的。

? ? ? ? 二分查找的过程如下：以 a-g 中7个字符查找 f 的过程为例：

? ? ? ? 示例代码如下：

package match_programing.lesson3_iterator;
import java.util.Arrays;
/**
 * 使用二分法查找匹配的记录
 * 前提： 查找范围必须有序
 * 
 * @author Administrator
 *
 */public class MatchRecord {

/**
 * 使用二分法，在给定的有序数组中，查找指定的字符串
 * 
 * @param dictionary
 *        有序字符串数组
 * @param wordToFind
 *        待查找的字符串
 * @return boolean
 */public static boolean searcg(String[] dictionary, String wordToFind) {

if (dictionary == null || dictionary.length == 0) {
return false;
}

int left = 0, right = dictionary.length - 1;
while (left <= right) {
int middle = left + (right -left)/2;    // (right + left)/2 在right 和 left 都接近极限值时，会导致溢出
if (dictionary[middle].equals(wordToFind)) {
return true;
}
if (dictionary[middle].compareTo(wordToFind) > 0) {
right = middle - 1;
}else {
left = middle + 1;
}
}

return false;
}


/**
 * 测试代码
 */public static void main(String[] args) {
String[] dictionaryString = {"i", "am", "one", "of", "the", "authors", "in", "geekbang"};
Arrays.sort(dictionaryString);    // 二分查找必须在有序集合中使用
String wordToFind = "i";

boolean found = MatchRecord.searcg(dictionaryString, wordToFind);
if (found) {
System.out.println(String.format("找到了单词 %s ", wordToFind));    // 输出：找到了单词 i
}else {
System.out.println(String.format("未能找到单词 %s", wordToFind));
}
}
}

说明：文中使用的图片来自极客时间，版权归极客时间所有。