程序员的数学基础课（三）余数与迭代法

问题：什么是余数 余数的作用？

余数在生活中非常常见，日历，日期，其中包含一个定理 同余定理。

同余定理：余数总是在一个固定的范围内，任意两个整数 a 和 b，如果它们除以正整数 m 得到的余数相等，我们就称 a 和 b 对于模 m 同余。

同余定理主要运用于：数据的均分。

模运算最大的特点就是不可逆，https就是利用这个原理通过非对称加密协商出对称密钥的。

在写代码过程中会用到的同余定理。负载均衡算法，分库分表，消息队列顺序消息，一致性hash，数据分页等等

余数在加密算法，随机存储等领域中有广泛应用

迭代法：

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

下面这张图即表示迭代法的数学函数。

代码实例如下

// 迭代器模式
//  兔子数列
function fib(month) {
    if (month ==1 || month === 2) {
        return 1
    } else {
        return fib(month -1) + fib(month - 2)
    }
}
//  棋盘的复利 等比数列
function iterater(num) {
    let resNum = 0
    let count = 1
    for (let index = 0; index < num; index++) {
        count*= 2
        resNum += count
    }
    return resNum
}

以上这两段代码使用迭代法实现了兔子数列 与棋盘问题的解决。

迭代法具体的应用

• 求数值的精确或者近似解。典型的方法包括二分法（Bisection method）和牛顿迭代法（Newton’s method）。
• 在一定范围内查找目标值。典型的方法包括二分查找。
• 机器学习算法中的迭代。相关的算法或者模型有很多，比如 K- 均值算法（K-means clustering）、PageRank 的马尔科夫链（Markov chain）、梯度下降法（Gradient descent）等等。迭代法之所以在机器学习中有广泛的应用，是因为很多时候机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解。而迭代法可以帮助学习算法逐步搜索，直至发现这种解。

以下以一个面试题为例， 题目：使用迭代法求一个数的算数平方根，给定固定的精度？ 以下是解题思路的图解

在数学中存在二分法进行不同逼近的操作，不停的逼近得数的操作。 以下为代码解题 方法 /** * * @param {*} num 需要计算的数据 * @param {*} deltaThreshold 误差精度 * @param {*} maxCount 计算 */ function getSqureRoot(num,deltaThreshold) { if (num<=1) { return 1 } // 设置最大值 var max = num; // 设置最小值 var min = 1; // 设置中间变量 var mid = 0; // 无限循环 for (; ;) { // 二分法求中间值 mid = (max +min) /2; // 得到平方值 var squre = mid* mid; // 计算精度 detalt = Math.abs((squre/num) -1); if (detalt<= deltaThreshold) { break } else { if (squre > num) { max = mid } else { min = mid } } } return mid }