MIT Python 公开课第三课要点-算法是怎样演进的

1.python算法课程

现在有一个很简单的问题，要求用编程来解决：求一个正整数的立方根。猜想和验证求立方根很麻烦，但计算一个数的立方很简单，因此我们可以猜想立方根的值，并且验证自己的猜想对不对。设计的流程图如下：

2.python算法教程这本书怎么样

据此我们可以用代码实现如下：y=27forxinrange(1,y+1):ifx**3==y:print(str(y)+”s cube root is”,x)breakifx**3!=y:print(y

3.python 算法导论

,is not a perfect cube)近似算法上面的算法只能求完全立方数的立方根，如果不是完全立方数就无能为力了，对于非完全立方数，我们能否求一个足够精确的近似解呢？其实稍微改进下上面的方法就行：不要每次都加 1，加一个更小的数，比如 0.00001， 然后算得的立方值跟目标值相差不大时，我们就认为求得了近似解。

4.python算法基础

据此实现的代码如下：y = 26 epsilon = 0.01 step = 0.00001 x = 1 while x < y: if abs(x ** 3 – y) = epsilon: print(Failed on cube root of, y)

5.python算法案例

基本思路与上面的一致，变化的主要有下面两点：for 循环换成了 while 循环，因为 for 中需要用到 range 来生成一个序列， 而 range 只能支持整数的加判断相等变成了判断差的绝对值小于某个范围。

6.python算法原理

上面的算法理论上能求出任何一个正数的近似立方根，对比第一种算法已经有了很大的进步但这种算法有两个特点：步长越小，尝试的次数越多，计算也就越慢，计算花的时间也就越长，但是计算结果的精确度越高要求的数越大，尝试的次数越多，计算越慢。

7.python学算法

我们迫切需要一种方法能加快计算速度二分查找我们可以看到上面方法进行了太多无意义的尝试，如果能把尝试的次数降低，那么算法的效率就能提高上面算法猜测次数之所以那么多，其实是因为每次都是从小往大一个个猜测，每次跨的步子都很小，如果步子跨得大些，那么效率就能有提升。

8.python算法研究

这里就需要二分查找，二分查找跨的步子非常大，查询很快拿求1000的立方根来举例，二分查找如下：猜测立方根为 (1000 + 0) / 2 = 500，计算 500 ** 3 > 1000;猜测立方根为 (500 + 0) / 2 = 250, 计算 250 ** 3 > 1000;

9.算法第一步python

猜测立方根为 (250 + 0) / 2 = 125, 计算 125 ** 3 > 1000;猜测立方根为 (125 + 0) / 2 = 62.5, 计算 62.5 ** 3 > 1000;猜测立方根为 (62.5 + 0) / 2 = 31.25, 计算 31.25 ** 3 > 1000;

10.算法用python

猜测立方根为 (31.25 + 0) / 2 = 15.625, 计算 15.625 ** 3 > 1000;猜测立方根为 (15.625 + 0) / 2 = 7.8125, 计算 7.8125 ** 3 < 1000;