100door 的思考

[63isOK]

最简单的是两层循环 一层是迭代100次开门过程 一层迭代是修改门状态

[63isOK]

第二种 优化循环次数 改为一次循环 判断门被开的次数 奇数次就是open状态

[63isOK]

第三种基于第二种的进一步优化 将问题改为求平方数不超过100的正整数

这里解空间是一致的 但问题转变为简单的数学问题了

[63isOK]

说到这里,有个很有意思的点需要提出来:
第二种优化,偶数次是closed状态,可以只找出奇数次即可,
其实和找公约数个数类似,91的公约数是1和91,翻动了两次,
所以需要找公约数个数是奇数的,只有当这个数是一个数的平方时才会有奇数个公约数.

前提说完了,再说下有意思的地方,求平方有两种常用的:
古时候计算n+1的平方,是 n的平方+n+n+1,用现在的公式是(n+1)(n+1)=n*n+2n+1,
要知道,当时是没有乘法的.

几何是数学证明的工具,n+1长的正方形面积,比n长正方形面积多了两边和一个1.

所以第二种解法,可以用乘法来计算平方,也可以用加法来计算,计算出的结果,就是下一次open状态的门位置

[63isOK]

看问题看到本质,当将一个复杂问题转换成一个简单的数学问题之后,写出的代码就非常简洁了.

当门数足够多时,3种写法的性能差异就拉开了