算法-人类思维&数学思维

算法-人类思维&数学思维

Posted by limantang on November 26, 2019

算法-人类思维&数学思维

算法与编程语言无关 平时工作当中很少遇到手写算法, 一般的算法都被封装好了, 例如排序sort算法 学习算法多想多写 开始吧

首先看一个问题

const testcase = [999, 222, 333, 555, 777];
function max(arr){
	//code
}
max(testcase) // 999

写出一个返回数组中最大值的函数 这个问题应该是很好解决的, 今天探究的不是这个问题的答案是什么 而是通过一步一步分析得到答案的过程, 重要的是思考的过程

站在自己和计算机之外第三视角

我们可以把自己放在脱离自己和计算机的第三视角来思考上面的问题

普通人类思维

首先看看人类如果遇到这个问题是如果思考的 人类一眼就可以看出999是最大的, 人类可能通过位数, 相同位数的首位大小等几种方法来确定大小 如果需要判断的数字个数很多的时候, 可以通过两两比较选出较大值, 然后循环往复, 一直对比到最后一个, 选出最大值

用代码实现思考的过程

const testcase = [111, 0, 333, 222, 111, 777, 999];

function max(arr) {
  let currentMax = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > currentMax) {
      currentMax = arr[i];
    }
  }
  return currentMax;
}

console.log(max(testcase));

总结一下人类思维

  • 比较难使用数学方法证明方法是对的
  • 只能通过大量的测试来证明算法是否可行
  • 无法给出反例证明算法可行
  • 符合人的常规逻辑和经验

数学思维

用数学方法求最大值可以通过下面的公式

  • 当k =1 的时候说明数组只有一个数, 最大值自然是第一个数
  • 当k > 1的时候如果nk大于n1, n2, …nk-1的最大值那么nk就是最大值, 否则最大值就在n1, n2, …nk-1当中, 那么就继续求值

代码实现过程


/**
 * ES5语法
 * @param {数组} arr 
 */

// function max(arr) {
//   if (arr.length === 1) return arr[0];
//   const remainMax = max(arr.slice(1));
//   return arr[0] > remainMax ? arr[0] : remainMax
// }


/**
 * 帮助函数, 两值取最大
 * @param {*} a 
 * @param {*} b 
 */
const maxOfTwo = (a, b) => a > b ? a : b
/**
 * ES6语法, 使用帮助函数
 * @param {*} arr 
 */
const max = arr => 
  arr.length === 1 ? arr[0] : 
  maxOfTwo(arr[0], max(arr.slice(1)))

const testcase = [111, 0, 333, 222, 111, 777, 999];
console.log(max(testcase));

使用两种方式实现, 没有太大区别, ES6更简洁一些 这个代码第一眼看上去感觉并没有在求最大值, 只不过是把公式实现了 我的第一感觉也是这样, 但其实是包含求最大值的过程, 并且运用到了递归

简单总结一下数学思维

  • 用公式表示求解过程
  • 只要公式是对的, 结果就是对的
  • 可以用公式证明
  • 总结公式的过程就是求解的过程

上面又一次涉及到了递归的使用了, 一定要很好的理解递归, 因为数学思维解决问题用到了大量的递归

分析一下上面代码执行的递归过程 使用m代替maxOfTwo函数

max(111, 0, 333, 222, 111, 777, 999)
m(111, max(0, 333, 222, 111, 777, 999))
m(111, m(0, max(333, 222, 111, 777, 999)))
m(111, m(0, m(333, max(222, 111, 777, 999))))
m(111, m(0, m(333,m(222, max(111, 777, 999)))))
m(111, m(0, m(333,m(222, m(111, max(777, 999))))))
m(111, m(0, m(333,m(222, m(111, m(777, max(999)))))))
//	 这里的上面部分就是不停地递进, 函数压栈
// 下面的部分就是不停地回归, 执行上面压进栈的函数然后出栈
m(111, m(0, m(333,m(222, m(111, m(777, 999))))))
m(111, m(0, m(333,m(222, m(111, 999)))))
m(111, m(0, m(333,m(222, 999))))
m(111, m(0, m(333, 999)))
m(111, m(0, 999))
m(111, 999)
999

上面就是完整的一次一次带入后得到的递归过程结果 递归就是分为 两个过程 就是递进, 也是不停地带入数值到函数中去,函数层层压栈, 知道符合出口条件(arr.length === 1) 就是回归, 也是从出口开始不停地计算递进过程压进栈的函数, 然后出栈, 最终的到结果

两种方法孰优孰劣?

  • 各有优势吧
  • 数学思维代码优雅, 可证明, 效率不高(可优化), 不够直观(对于数学知识较少的人)
  • 人类思维易于理解(相对而言), 代码没有数学思维优雅, 效率较高
  • 数学思维难点在于如何得到公式

汉诺塔问题

汉诺塔 - 维基百科,自由的百科全书

不了解的可以点击这个链接了解一下 如果用人类思维解决汉诺塔问题就没那么简单了, 因为人类思维是线性的, 大脑没办法一下记住那么多的步骤, 汉诺塔的数量少的话还可以理清楚, 如果多的话就不容易理清楚

如果通过数学思维来解决就会方便很多 一起来分析一下如何通过数学思维来解决这个问题

假设三个塔定义为A, B, C

  • A顶部的盘子移到B, 记为: AB
  • AB + AC 表示先把A顶部的盘子移到B(AB), 然后再把A新的顶部盘子移到C(AC)
  • h(n, A, B, C)表示有n个盘子在A, 需要移动到C, B可以认为是中转用
  • h(1, A, B, C) ==> AC A只有一个盘子, 那么直接移动到C就可以了
  • h(2, A, B, C) ==> h(1, A, C, B) + AC + h(1, B, A, C) A有两个盘子, 那么就把A的第一个盘子移动到B, 然后把A的另一个盘子移动到C, 再把B的盘子移动到C
  • h(3, A, B, C) ==> h(2, A, C, B) + AC + h(2, B, A, C) A有三个盘子, 那么就利用上一步A中有两个盘子的思路, 先把A上的两个盘子移动到B, 再把A的第三个盘子移动到C, 再把B上的两个盘子移动到C
  • h(n, A, B, C) ==> h(n-1, A, C, B) + AC + h(n-1, B, A, C) 这个就是总结上面的规律归纳得出的公式

数学归纳法

  • 证明n = 1时命题成立
  • 证明当n = k时命题成了, n = k + 1时命题也成立(k = 1 , 2 , 3 …)

变形

  • 不一定每次都从1开始
  • 不一定每次都要加1
  • 也可以倒着开始, 每次减1 具体情况具体分析

将上面的公式转化为代码

const h = (n, from, cache, to) =>
  n === 1 ? `${console.log(from, to)}\n` :
  h(n - 1, from, to, cache) + `${console.log(from, to)}\n` + h(n - 1, cache, from, to)

  h(3, 'A', 'B', 'C');

A C A B C B A C B A B C A C 这个就是移动的过程, 可以动手按照这个过程移动一下

斐波那契数列

数学思维

/**
 * 数学思维
 */

 const f = n => 
  n === 1 ? 0 :
  n === 2 ? 1 :
    f(n - 1) + f(n - 2)

人类思维

/**
 * 人类思维
 */

 function f(n) {
   const arr = [0, 1];
   for(let i = 2; i <= n; i++) {
     arr[i] = arr[i-1] + arr[i-2];
   }
   return arr[n-1];
 }

数学思维

  • 更加优雅, 简单
  • 注重形式
  • 可能会重复计算, 浪费性能 人类思维
  • 更容易理解执行
  • 对人脑负担重
  • 会被经验所限, 如果问题一次都没遇到过

递归&迭代

举例: 阶乘函数


/**
 * 递归版阶乘函数
 */

 const f = n => 
  n === 1 ? 1 :
    n * f(n - 1)

如果计算n的数值很大存在大量的函数压栈操作 callStack就是函数的调用栈, 其存在的意义是保留每次函数的执行环境, 以便当前函数环境中下一次执行的函数使用 对于各个编程语言都会存在函数调用栈爆掉的可能性

所以说如何减少压栈呢

  • 不用递归(使用循环代替递归)
  • 用尾递归 + 尾递归优化

尾递归就是不用回到函数现场的递归调用

循环代替递归

/**
 * 循环代替递归版阶乘函数
 */

 const f = n => {
   let result = 1;
   for (let i = 1; i <= n; i++) {
     result *= i;
   }
   return result
 }

使用迭代(while)代替递归

/**
 * 迭代(while)代替递归版阶乘函数
 */

 const f = n => {
   let result = 1, i = 1, next_result, next_i;
   while(i <= n - 1) {
    next_i = i+1;
    next_result = next_i * result;
    i = next_i;
    result = next_result;
   }
   return result;
 }

迭代(尾递归)代替递归


/**
 * 迭代(尾递归)代替递归版阶乘函数
 */

 const f = n => {
  const diedai = (i, n, result) => {
    return i === n ? result : diedai(i+1, n, result * (i + 1))
  }
  return diedai(1, n, 1)
 }

到底什么是尾递归?

  • 递归只出现在return语句的后面
  • return语句的后面只有递归函数 如何理解这两个条件呢 看上面的例子 例子中diedai这个函数只出现在了return语句的后面 return后面只有diedai这个函数执行, 只有diedai函数执行的意思是 不包括任何除了diedai执行以外的操作, 比如3 * diedai(1, n, 1)因为如果这样的话, 就会出现diedai这个函数使用了3这个变量, 那么就必须将函数入栈, 来保存函数的执行环境, 所以说这两个条件必须严格符合才是, 尾递归

总结

  • 递归需要压栈, 栈的长度有限
  • 可以使用循环代替递归
  • 可以使用迭代代替递归
  • 迭代是使用循环实现的, 也可以用递归
  • 迭代理论上是不需要压栈操作的
  • 尾递归是迭代的一种表现
  • 尾调用优化可以消除不必要的压栈
  • JS引擎没有完全普及尾调用优化
  • 递归缺点: 重复计算, 栈溢出

使用记忆化消除递归中的重复计算

代码如下


/**
 * 记忆化函数
 */

const memo = fn => {
  const cache = {};
  return function () {
    const fnKey = JSON.stringify({
      name: fn.name,
      arguments
    });
    console.log('计算了');
    if (!cache[fnKey]) {
     console.log('没有缓存');
     return cache[fnKey] = fn.apply(undefined, arguments)
    } else {
     console.log('有缓存');
     return cache[fnKey];
    }
    
  }
}
/**
 * 递归
 */
// const f = n => 
//   n === 1 ? 0 :
//   n === 2 ? 1 :
//     memoFn(n - 1) + memoFn(n - 2)

// const memoFn = memo(f);
// console.log(memoFn(3))
// console.log(memoFn(6))

// console.log(memoFn(46))


/**
 * 换一种写法
 */

const f = memo(
  function(n) {
    return n === 1 ? 0 :
            n === 2 ? 1 :
            f(n - 1) + f(n - 2)
  }
)
console.log(f(3))
console.log(f(6))
console.log(f(46))
console.log(f(100))

记忆化的函数原理之前讨论过, 这里就不在讨论了

可以明确的是记忆化对于递归的优化是极其有帮助的

源码地址

math-blog-code/introduction at master · echoheart/math-blog-code · GitHub